Cw Wong

(2007), pp. 54-89. The amount of information available online is increasing exponentially. While this information is a valuable resource, its sheer volume limits its value. Many research projects and companies are exploring the use of personalized applications that manage this deluge by tailoring the information presented to individual users. These applications all need to gather, and exploit, some information about individuals in order to be effective. This area is broadly called user profiling. This chapter surveys some of the most popular techniques for collecting information about users, representing, and building user profiles. In particular, explicit information techniques are contrasted with implicitly collected user information using browser caches, proxy servers, browser agents, desktop agents, and search logs. We discuss in detail user profiles represented as weighted keywords, semantic networks, and weighted concepts. We review how each of these profiles is constructed and... - Cw Wong

(11 Dec 1997) As more information becomes available electronically, tools for finding information of interest to users becomes increasingly important. The goal of the research described here is to build a system for generating comprehensible user profiles that accurately capture user interest with minimum user interaction. The research described here focuses on the importance of a suitable generalization hierarchy and representation for learning profiles which are predictively accurate and comprehensible. In our experiments we evaluated both traditional features based on weighted term vectors as well as subject features corresponding to categories which could be drawn from a thesaurus. Our experiments, conducted in the context of a content-based profiling system for on-line newspapers on the World Wide Web (the IDD News Browser), demonstrate the importance of a generalization hierarchy and the promise of combining natural language processing techniques with machine learning (ML) to... - Cw Wong

(1996) Introduction With the growing availability of information sources, especially non-homogeneous, distributed sources like the World Wide Web, there is also a growing interest in tools that can help in making a good and quick selection of information we are interested in. Recent work that arises at the intersection of Information Retrieval and Machine Learning offers some novel solutions to this problem, as well as work in Intelligent Agents. For example, Armstrong et al. [2] developed WebWatcher, a system that assists user in locating information on the World Wide Web taking keywords from the user, suggesting hyperlinks and receiving evaluation. Balabanovic et al. [3] developed "a system which learns to browse the Internet on behalf of a user". It searches the World Wide Web taking bounded amount of time, selects the best pages and receives an evaluation from the user. The evaluation is used to update the search and selection heuristics. Pazzani et al. [26] collect ratings of th... - Cw Wong

Commun. ACM, Vol. 40, No. 3. (March 1997), pp. 77-87. An abstract is not available. Joseph Konstan, Bradley Miller, David Maltz, Jonathan Herlocker, Lee Gordon, John Riedl - Cw Wong

In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001), pp. 257-262. In this paper, we present PVA, an adaptive personal view information agent system to track, learn and manage, user's interests in Internet documents. When user's interests change, PVA, in not only the contents, but also in the structure of user profile, is modified to adapt to the changes. Experimental results show that modulating the structure of user profile does increase the accuracy of personalization systems. Chien Chen, Meng Chen, Yeali Sun - Cw Wong

In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval (2005), pp. 449-456. We formulate and study search algorithms that consider a user's prior interactions with a wide variety of content to personalize that user's current Web search. Rather than relying on the unrealistic assumption that people will precisely specify their intent when searching, we pursue techniques that leverage implicit information about the user's interests. This information is used to re-rank Web search results within a relevance feedback framework. We explore rich models of user interests, built from both search-related information, such as previously issued queries and previously visited Web pages, and other information about the user such as documents and email the user has read and created. Our research suggests that rich representations of the user and the corpus are important for personalization, but that it is possible to approximate... - Cw Wong

In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (2003), pp. 226-235. Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Beyesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the... - Cw Wong

In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001), pp. 97-106. Most statistical and machine-learning algorithms assume that the data is a random sample drawn from a stationary distribution. Unfortunately, most of the large databases available for mining today violate this assumption. They were gathered over months or years, and the underlying processes generating them changed during this time, sometimes radically. Although a number of algorithms have been proposed for learning time-changing concepts, they generally do not scale well to very large databases. In this paper we propose an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner. This algorithm, called CVFDT, stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new... - Cw Wong

Artif. Intell. Rev., Vol. 11 (February 1997), pp. 133-155. In their unmodified form, lazy-learning algorithms may have difficulty learning and tracking time-varying input/output function maps such as those that occur in concept shift. Extensions of these algorithms, such as Time-Windowed forgetting (TWF), can permit learning of time-varying mappings by deleting older exemplars, but have decreased classification accuracy when the input-space sampling distribution of the learning set is time-varying. Additionally, TWF suffers from lower asymptotic classification accuracy than equivalent non-forgetting algorithms when the input sampling distributions are stationary. Other shift-sensitive algorithms, such as Locally-Weighted forgetting (LWF) avoid the negative effects of time-varying sampling distributions, but still have lower asymptotic classification in non-varying cases. We introduce Prediction Error Context Switching (PECS) which allows lazy-learning algorithms to have good... - Cw Wong

In Proceedings of the 1990 conference on Advances in neural information processing systems 3 (1990), pp. 183-189. An abstract is not available. Anthony Kuh, Thomas Petsche, Ronald Rivest - Cw Wong

(1995) Miroslav Kubat, Gerhard Widmer - Cw Wong

In Proceedings of the eighth international conference on Information and knowledge management (1999), pp. 538-544. The task of information filtering is to classify documents from a stream as either relevant or non-relevant according to a particular user interest with the objective to reduce information load. When using an information filter in an environment that is changing with time, methods for adapting the filter should be considered in order to retain classification accuracy. We favor a methodology that attempts to detect changes and adapts the information filter only if inevitable in order to minimize the amount of user feedback for providing new training data. Yet, detecting changes may require costly user feedback as well. This paper describes two methods for detecting changes without user feedback. The first method is based on evaluating an expected error rate, while the second one observes the fraction of classification decisions made with a confidence below a given... - Cw Wong

Machine Learning, Vol. 32, No. 2. (21 August 1998), pp. 101-126. Concept drift due to hidden changes in context complicates learning in many domains including financial prediction, medical diagnosis, and communication network performance. Existing machine learning approaches to this problem use an incremental learning, on-line paradigm. Batch, off-line learners tend to be ineffective in domains with hidden changes in context as they assume that the training set is homogeneous. An off-line, meta-learning approach for the identification of hidden context is presented. The new approach uses an existing batch learner and the process of contextual clustering to identify stable hidden contexts and the associated context specific, locally stable concepts. The approach is broadly applicable to the extraction of context reflected in time and spatial attributes. Several algorithms for the approach are presented and evaluated. A successful application of the approach to a complex flight... - Cw Wong

Mach. Learn., Vol. 23 (April 1996), pp. 69-101. An abstract is not available. Gerhard Widmer, Miroslav Kubat - Cw Wong

In In The ICCBR’03 Workshop on Long-Lived CBR Systems (2003), pp. 03-2003. There are a few key benefits of a case-based approach to spam filtering. First, the many different sub-types of spam suggest that a local leamer, such as Case-Based Reasoning (CBR) will perform well. Second, the lazy approach to learning in CBR allows for easy updating as new types of spam arrive. Third, the case-based approach to spam filtering allows for the sharing of cases and thus a sharing of the effort of labeling email as spam. In this paper we introduce a case-based approach to spam filtering and present preliminary evidence of the first two of these advantages. Pádraig Cunningham, Niamh Nowlan, Sarah Delany, Mads Haahr - Cw Wong

pp. 123-130. Algorithms for tracking concept drift are important for many applications. We present a general method based on the weighted majority algorithm for using any online learner for concept drift. Dynamic weighted majority (DWM) maintains an ensemble of base learners, predicts using a weighted-majority vote of these "experts", and dynamically creates and deletes experts in response to changes in performance. We empirically evaluated two experimental systems based on the method using incremental naive Bayes and incremental tree inducer [ITI] as experts. For the sake of comparison, we also included Blum's implementation of weighted majority. On the STAGGER concepts and on the SEA concepts, results suggest that the ensemble method learns drifting concepts almost as well as the base algorithms learn each concept individually. Indeed, we report the best overall results for these problems to date. JZ Kolter, MA Maloof - Cw Wong

In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001), pp. 377-382. Ensemble methods have recently garnered a great deal of attention in the machine learning community. Techniques such as Boosting and Bagging have proven to be highly effective but require repeated resampling of the training data, making them inappropriate in a data mining context. The methods presented in this paper take advantage of plentiful data, building separate classifiers on sequential chunks of training points. These classifiers are combined into a fixed-size ensemble using a heuristic replacement strategy. The result is a fast algorithm for large-scale or streaming data that classifies as well as a single decision tree built on all the data, requires approximately constant memory, and adjusts quickly to concept drift. Nick Street, YongSeog Kim - Cw Wong

Mach. Learn., Vol. 1, No. 3. (March 1986), pp. 317-354. Induction of a concept description given noisy instances is difficult and is further exacerbated when the concepts may change over time. This paper presents a solution which has been guided by psychological and mathematical results. The method is based on a distributed concept description which is composed of a set of weighted, symbolic characterizations. Two learning processes incrementally modify this description. One adjusts the characterization weights and another creates new characterizations. The latter process is described in terms of a search through the space of possibilities and is shown to require linear space with respect to the number of attribute-value pairs in the description language. The method utilizes previously acquired concept definitions in subsequent learning by adding an attribute for each learned concept to instance descriptions. A program called STAGGER fully embodies this method, and this paper reports... - Cw Wong

Mach. Learn., Vol. 14 (January 1994), pp. 27-45. In this paper we consider the problem of tracking a subset of a domain (called the target) which changes gradually over time. A single (unknown) probability distribution over the domain is used to generate random examples for the learning algorithm and measure the speed at which the target changes. Clearly, the more rapidly the target moves, the harder it is for the algorithm to maintain a good approximation of the target. Therefore we evaluate algorithms based on how much movement of the target can be tolerated between examples while predicting with accuracy ε Furthermore, the complexity of the class \CAL H of possible targets, as measured by d, its VC-dimension, also effects the difficulty of tracking the target concept. We show that if the problem of minimizing the number of disagreements with a sample from among concepts in a class \CAL H can be approximated to within a factor k, then there is a simple tracking algorithm for... - Cw Wong

In Case-Based Reasoning Research and Development, Vol. 1650 (29 October 1999), pp. 720-720. Case-based problem-solving systems reason and learn from experiences, building up case libraries of problems and solutions to guide future reasoning. The expected benefits of this learning process depend on two types of regularity: (1) problem-solution regularity, the relationship between problem-to-problem and solution-to-solution similarity measures that assures that solutions to similar prior problems are a useful starting point for solving similar current problems, and (2) problem-distribution regularity, the relationship between old and new problems that assures that the case library will contain cases similar to the new problems it encounters. Unfortunately, these types of regularity are not assured. Even in contexts for which initial regularity is sufficient, problems may arise if a system’s users, tasks, or external environment change over time. This paper defines criteria for assessing... - Cw Wong

Machine Learning, Vol. 6, No. 1. (1 January 1991), pp. 37-66. Storing and using specific instances improves the performance of several supervised learning algorithms. These include algorithms that learn decision trees, classification rules, and distributed networks. However, no investigation has analyzed algorithms that use only specific instances to solve incremental learning tasks. In this paper, we describe a framework and methodology, called instance-based learning, that generates classification predictions using only specific instances. Instance-based learning algorithms do not maintain a set of abstractions derived from specific instances. This approach extends the nearest neighbor algorithm, which has large storage requirements. We describe how storage requirements can be significantly reduced with, at most, minor sacrifices in learning rate and classification accuracy. While the storage-reducing algorithm performs well on several real-world databases, its performance degrades... - Cw Wong

Intell. Data Anal., Vol. 8, No. 3. (August 2004), pp. 281-300. For many learning tasks where data is collected over an extended period of time, its underlying distribution is likely to change. A typical example is information filtering, i.e. the adaptive classification of documents with respect to a particular user interest. Both the interest of the user and the document content change over time. A filtering system should be able to adapt to such concept changes. This paper proposes several methods to handle such concept drifts with support vector machines. The methods either maintain an adaptive time window on the training data [13], select representative training examples, or weight the training examples [15]. The key idea is to automatically adjust the window size, the example selection, and the example weighting, respectively, so that the estimated generalization error is minimized. The approaches are both theoretically well-founded as well as effective and efficient in practice.... - Cw Wong

Concept drift occurs when a target concept changes over time. I present a new method for learning shifting target concepts during concept drift. The method, called Concept Drift Committee (CDC), uses a weighted committee of hypotheses that votes on the current classification. When a committee member's voting record drops below a minimal threshold, the member is forced to retire. A new committee member then takes the open place on the committee. The algorithm is compared to a leading algorithm on a number of concept drift problems. The results show that using a committee to track drift has several advantages over more customary window-based approaches. Kenneth Stanley - Cw Wong

In Proceedings of the European Conference on Machine Learning (1993), pp. 227-243. An abstract is not available. Gerhard Widmer, Miroslav Kubat - Cw Wong

In In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (pp. 645--650 (1991), pp. 645-650. In this paper we describe a method for hybridizing a genetic algorithm and a k nearest neighbors classification algorithm. We use the genetic algorithm and a training data set to learn real-valued weights associated with individual attributes in the data set. We use the k nearest neighbors algorithm to classify new data records based on their weighted distance from the members of the training set. We applied our hybrid algorithm to three test cases. Classification results obtained with the hybrid algorithm exceed the performance of the k nearest neighbors algorithm in all three cases. 1 James Kelly - Cw Wong

IEEE Internet Computing, Vol. 7, No. 1. (January 2003), pp. 76-80. By comparing similar items rather than similar customers, item-to-item collaborative filtering scales to very large data sets and produces high-quality recommendations. Greg Linden, Brent Smith, Jeremy York - Cw Wong