17510008
Applying Machine Learning to Text Segmentation for Information Retrieval
We propose a self-supervised word segmentation technique for text segmentation in Chinese information retrieval. This method combines the advantages of traditional dictionary based, character based and mutual information based approaches, while overcoming many of their shortcomings. Experiments on TREC data show this method is promising. Our method is completely language independent and unsupervised, which provides a promising avenue for constructing accurate multi-lingual or cross-lingual information retrieval systems that are flexible and adaptive. We find that although the segmentation accuracy of self-supervised segmentation is not as high as some other segmentation methods, it is enough to give good retrieval performance. It is commonly believed that word segmentation accuracy is monotonically related to retrieval performance in Chinese information retrieval. However, for Chinese, we find that the relationship between segmentation and retrieval performance is in fact nonmonotonic; that is, at around 70% word segmentation accuracy an over-segmentation phenomenon begins to occur which leads to a reduction in information retrieval performance. We demonstrate this effect by presenting an empirical investigation of information retrieval on Chinese TREC data, using a wide variety of word segmentation algorithms with word segmentation accuracies ranging from 44% to 95%, including 70% word segmentation accuracy from our self-supervised word-segmentation approach. It appears that the main reason for the drop in retrieval performance is that correct compounds and collocations are preserved by accurate segmenters, while they are broken up by less accurate (but reasonable) segmenters, to a surprising advantage. This suggests that words themselves might be too broad a notion to conveniently capture the general semantic meaning of Chinese text. Our research suggests machine learning techniques can play an important role in building adaptable information retrieval systems and different evaluation standards for word segmentation should be given to different applications.
921552
Dynamic Web log session identification with statistical language models
We present a novel session identification method based on statistical language modeling. Unlike standard time-out methods, which use fixed time thresholds for session identification, we use an information theoretic approach that yields more robust results for identifying session boundaries. We evaluate our new approach by learning interesting association rules from the segmented session files. We then compare the performance of our approach to three standard session identification method--the standard timeout method, the reference length method, and the maximal forward reference method--and find that our statistical language modeling approach generally yields superior results. However, as with every method, the performance of our technique varies with changing parameter settings. Therefore, we also analyze the influence of the two key factors in our language-modeling-based approach: the choice of smoothing technique and the language model order. We find that all standard smoothing techniques, save one, perform well, and that performance is robust to language model order.
27390518
Session Boundary Detection for Association Rule Learning Using n-Gram Language Models
We present a statistical method using n-gram language models to identify session boundaries in a large collection of Livelink log data. The identified sessions are then used for association rule learning. Unlike the traditional ad hoc timeout method, which uses fixed time thresholds for session identification, our method uses an information theoretic approach that provides a natural technique for performing dynamic session identification. The effectiveness of our approach is evaluated with respect to 4 different interestingness measures. We find that we obtain a significant improvement in each interestingness measure, ranging from a 26.6% to 39% improvement on average over the best results obtained with standard timeout methods.
9414412
Concept-based biomedical text retrieval
One challenging problem for biomedical text retrieval is to find accurate synonyms or name variants for biomedical entities. In this paper, we propose a new concept-based approach to tackle this problem. In this approach, a set of concepts instead of keywords will be extracted from a query first. Then these concepts will be used for retrieval purpose. The experiment results show that the proposed approach can boost the retrieval performance and it generates very good results on 2005 TREC Genomics data sets.
9602783
Discovery of interesting association rules from Livelink web log data
We present our experience in mining web usage patterns from a large collection of Livelink log data. Livelink is a web-based product of Open Text, which provides automatic management and retrieval of different types of information objects over an intranet or extranet. We report our experience in preprocessing raw log data and post-processing the mining results for finding interesting rules. In particular we compare and evaluate a number of rule interestingness measures and find that two of the measures that have not been used in association rule learning work very well.
668000
Applying language modeling to session identification from database trace logs
A database session is a sequence of requests presented to the database system by a user or an application to achieve a certain task. Session identification is an important step in discovering useful patterns from database trace logs. The discovered patterns can be used to improve the performance of database systems by prefetching predicted queries, rewriting the current query or conducting effective cache replacement.In this paper, we present an application of a new session identification method based on statistical language modeling to database trace logs. Several problems of the language modeling based method are revealed in the application, which include how to select values for the parameters of the language model, how to evaluate the accuracy of the session identification result and how to learn a language model without well-labeled training data. All of these issues are important in the successful application of the language modeling based method for session identification. We propose solutions to these open issues. In particular, new methods for determining an entropy threshold and the order of the language model are proposed. New performance measures are presented to better evaluate the accuracy of the identified sessions. Furthermore, three types of learning methods, namely, learning from labeled data, learning from semi-labeled data and learning from unlabeled data, are introduced to learn language models from different types of training data. Finally, we report experimental results that show the effectiveness of the language model based method for identifying sessions from the trace logs of an OLTP database application and the TPC-C Benchmark.
13555130
Deformable-Model Based Textured Object Segmentation
In this paper, we present a deformable-model based solution for segmenting objects with complex texture patterns of all scales. The external image forces in traditional deformable models come primarily from edges or gradient information and it becomes problematic when the object surfaces have complex large-scale texture patterns that generate many local edges within a same region. We introduce a new textured object segmentation algorithm that has both the robustness of model-based approaches and the ability to deal with non-uniform textures of both small and large scales. The main contributions include an information-theoretical approach for computing the natural scale of a “texon” based on model-interior texture, a nonparametric texture statistics comparison technique and the determination of object belongingness through belief propagation. Another important property of the proposed algorithm is in that the texture statistics of an object of interest are learned online from evolving model interiors, requiring no other a priori information. We demonstrate the potential of this model-based framework for texture learning and segmentation using both natural and medical images with various textures of all scales and patterns.
12511265
A Scalable Algorithm for Adjusting Node-Node Overlaps
The node-node overlaps, which occur in drawing of labeled graphs, and more importantly, in the dynamic drawing, have been a problem in graph visualization. Several approaches have recently been proposed to solve such a problem. These approaches, however, lack the scalabilities of dealing with large number of overlapping nodes. Providing a formal description of the problem, this paper presents a scalable version of our previous approach called the force-transfer algorithm. Compared to other methods, our new algorithm is able to achieve the compact adjusted layout of a large graph
2218327
Strong computational lower bounds via parameterized complexity
We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(n^k) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)n^o^(^k^) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order @Q(@m(n)) for any reasonable function @m, no algorithm of running time n^o^(^k^) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/@e)n^o^(^1^/^@e^) for any function f unless an unlikely collapse occurs in parameterized complexity theory.
33920606
Hot-Spot Passage Retrieval in Question Answering
Question Answering has been the recent focus of information retrieval research; many systems just incorporate a search engine as a black box and most effort has been devoted to the question analyzer and the answer identifier. In the context of QA, however, passage provides an ideal medium between the document collection and an exact answer. And passage retrieval is a finer-grain approach than the traditional document retrieval both for the answer identifier and a human reader. In this paper, distinctions are first made between document retrieval and passage retrieval. And the Hot-Spot Passage Retrieval algorithm, which takes into account the measures of blurred BM25, coverage and height, is examined in detail. For evaluation, an isolated test is conducted and the algorithm gains 18.3% better answer redundancy and 4.8% better coverage rate than Okapi's original passage retrieval algorithm.
30724966
Motivational System for Human-Robot Interaction
Human-Robot Interaction (HRI) has recently drawn increased attention. Robots can not only passively receive information but also actively emit actions. We present a motivational system for human-robot interaction. The motivational system signals the occurrence of salient sensory inputs, modulates the mapping from sensory inputs to action outputs, and evaluates candidate actions. No salient feature is predefined in the motivational system but instead novelty based on experience, which is applicable to any task. Novelty is defined as an innate drive. Reinforcer is integrated with novelty. Thus, the motivational system of a robot can be developed through interactions with trainers. We treat vision-based neck action selection as a behavior guided by the motivational system. The experimental results are consistent with the attention mechanism in human infants.