Search

Given a set of clusters, we consider an optimization problem which seeks a subset of clusters that maximizes the microaverage F-measure. This optimal value can be used as an evaluation measure of the goodness of clustering. For arbitrarily overlapping clusters, finding the optimal value is NP-hard. We claim that a greedy approximation algorithm yields the global optimal solution for clusters that overlap only by nesting. We present a mathematical proof of this claim by induction. For a family of n clusters containing a total of N objects, this algorithm has an {\rm O}(n;{2}) time complexity and O(N) space complexity.

This paper presents an investigation about how to automatically formulate effective queries using full or partial relevance information (i.e., the terms that are in relevant documents) in the context of relevance feedback (RF). The effects of adding relevance information in the RF environment are studied via controlled experiments. The conditions of these controlled experiments are formalized into a set of assumptions that form the framework of our study. This framework is called idealized relevance feedback (IRF) framework. In our IRF settings, we confirm the previous findings of relevance feedback studies. In addition, our experiments show that better retrieval effectiveness can be obtained when (i) we normalize the term weights by their ranks, (ii) we select weighted terms in the top K retrieved documents, (iii) we include terms in the initial title queries, and (iv) we use the best query sizes for each topic instead of the average best query size where they produce at most five percentage points improvement in the mean average precision (MAP) value. We have also achieved a new level of retrieval effectiveness which is about 55-60% MAP instead of 40+% in the previous findings. This new level of retrieval effectiveness was found to be similar to a level using a TREC ad hoc test collection that is about double the number of documents in the TREC-3 test collection used in previous works.

Electronic financial news available on the Internet contains a wealth of information useful for business decision-making. However, as this information is both qualitative and existent in huge volumes, it is very inefficient to digest manually. This paper presents a prototype system called FNDS, which automatically digests financial news by extracting important information from the articles and using this information to fill in pre-defined templates. A unique feature of FNDS is that users can access the extracted information through an interactive dialogue-based interface. This has the advantage that if users do not know exactly what information is required, the system will provide feedback to help them to formulate the information requirement incrementally.

Workflow is an important class of applications in the daily business. A number of web-based workflow systems have been de veloped recently as a natural extension to traditional workflow systems to exploit the growing popularity of the Internet. However, most of them are designed based on the specific application at hand. In this paper, we distill out the fundamental elements of a workflow system into a general workflow framework. The framework provides appropriate application programming interfaces for programmers to fill in the application specific requirements of a workflow system at hand. This is realized through two object-wrappers: the Task interface and the Resource interface, which support the specification of the tasks involved in the workflow schedule and the resources accessed re spectively. A major characteristic of the framework is that the particular workflow schedule under execution is fluid, in the sense that the tasks involved as well as their precedence relationships can be modified dynamically. Consistency constraints will be examined in this paper which determine when such modifications are allowed. To maximize flexibility, we adhere our design to the CORBA architecture, which has been becoming highly popular in recent years, thus allowing tasks and resources of different types to interoperate in our framework. We demonstrate the feasibility of our framework with a small prototype that allows tasks in a workflow system to be sched uled and executed.

In this paper, we present a system called FIDS (Financial Information Digest System), which can digest online financial news automatically. Compared to previous approaches, FIDS is unique in the way that it can understand news articles in different domains simultaneously. These domains are all concerned with financial news. The system is able to integrate the information from different articles by conducting automatic content-based classification and information item extraction. Moreover, it allows one to perform cross-validation on their contents. As a result, users can have access to more complete information which otherwise would be scattered in different articles.

A load balancing scheme is presented which allows HTTP requests to be dynamically migrated between clustered back-end Web servers based on the loading condition of the system. We adopt a nearest neighborhood clustering algorithm whereby an adaptive number of requests are migrated as determined by the real-time distribution of load among the servers. Experiment results demonstrate that our proposed algorithm yields the best performance when compared with several other common approaches.

With the rapidly increasing reliance to distributed systems following the prosperity of low cost networking and the Internet, development of effective techniques for task distribution becomes one of the important issues in distributed computing. During the past few years, most of the load balancing algorithms in practical use employed migration policy with a fixed number of tasks in each step. This paper proposes a task transfer scheme with an adaptive number of tasks transferred between the participating servers for load balancing. The adaptation is achieved by a data mining technique, namely, clustering, via employing the distance-weighted nearest neighborhood algorithm. Experiment results show that our proposed algorithm yields the best performance when compared with several other common approaches.

In this paper, semantic role labeling is addressed. We formulate the problem as a classification task, in which the words of a sentence are assigned to semantic role classes using a classifier. The maximum entropy approach is applied to train the classifier, by using a large real corpus annotated with argument structures.

We present a prototype of a collaborative word processing system. The prototype allows multiple co-authors to edit the same document simultaneously while maintaining a consistent and updated version of the document. The prototype is built on a CORBA-based workflow framework in which the flow of the document components among the co-authors is governed by a workflow schedule that can, be adapted dynamically during execution. To facilitate resource locking and sharing, in the workflow framework, different types of resources are represented homogeneously as XML trees. This allows resources of different types and granularities to be combined and enables individual resources to be shared and manipulated at different levels of details.

Previously, the Object Management Group (OMG) has published a standard for a common object service, called the event service, to support decoupled and asynchronous communication between distributed CORBA object components. However, the service, albeit flexible, still suffers from a number of limitations. Among others, it has poor scalability, and it is not totally reliable. In view of these drawbacks, we propose a generic framework which extends the event service with built-in support for load balancing (both static and dynamic) and fault tolerance. These functions are achieved transparently without the intervention of the application objects.

Holistic parsers offer a viable alternative to traditional algorithmic parsers. They have good generalization performance and are robust inherently. In a holistic parser, parsing is achieved by mapping the connectionist representation of the input sentence to the connectionist representation of the target parse tree directly. Little prior knowledge of the underlying parsing mechanism thus needs to be assumed. However, it also makes holistic parsing difficult to understand. In this article, an analysis is presented for studying the operations of the confluent pre-order parser (CPP). In the analysis, the CPP is viewed as a dynamical system, and holistic parsing is perceived as a sequence of state transitions through its state-space. The seemingly one-shot parsing mechanism can thus be elucidated as a step-by-step inference process, with the intermediate parsing decisions being reflected by the states visited during parsing. The study serves two purposes. First, it improves our understanding of how grammatical errors are corrected by the CPP. The occurrence of an error in a sentence will cause the CPP to deviate from the normal track that is followed when the original sentence is parsed. But as the remaining terminals are read, the two trajectories will gradually converge until finally the correct parse tree is produced. Second, it reveals that having systematic parse tree representations alone cannot guarantee good generalization performance in holistic parsing. More important, they need to be distributed in certain useful locations of the representational space. Sentences with similar trailing terminals should have their corresponding parse tree representations mapped to nearby locations in the representational space. The study provides concrete evidence that encoding the linearized parse trees as obtained via preorder traversal can satisfy such a requirement.