Many real-life dynamical systems change abruptly followed by almost stationary periods. In this paper, we consider streams of data with such abrupt behavior and investigate the problem of tracking their statistical properties in an online manner. We devise a tracking procedure where an estimator that is suitable for a stationary environment is combined together with an event detection method such that the estimator rapidly can jump to a more suitable value if an event is detected. Combining an estimation procedure with detection procedure is commonly known idea in the literature. However, our contribution lies in building the detection procedure based on the difference between the stationary estimator and a Stochastic Learning Weak Estimator (SLWE). The SLWE estimator is known to be the state-of-the art approach to tracking properties of non-stationary environments and thus should be a better choice to detect changes in abruptly changing environments than the far more common sliding window based approaches. To the best of our knowledge, the event detection procedure suggested by (2012) is the only procedure in the literature taking advantage of the powerful tracking properties of the SLWE estimator. The procedure in is however quite complex and not well founded theoretically compared to the procedures in this paper. In this paper, we focus on estimation procedure for the binomial and multinomial distributions, but our approach can be easily generalized to cover other distributions as well. Extensive simulation results based on both synthetic and real-life data related to news classification demonstrate that our estimation procedure is easy to tune and performs well.
When it comes to extensions of the sliding window, Koychev . proposed a new paradigm called Gradual Forgetting (GF) @cite_2 @cite_8 @cite_30 . According to the principles of GF, observations in the same window are treated unequally when computing the estimates based on weight assignment. Recent observations receive more weights than distant ones. Different forgetting functions were proposed ranging from linear @cite_32 to exponential @cite_5 .
@cite_30 @cite_8 @cite_32 @cite_2 @cite_5
1545292741 1501483081 1481458213 2133088989
In recent years, many systems have been developed which aim at helping users to find pieces of information or other objects that are in accordance with their personal interests. In these systems, machine learning methods are often used to acquire the user interest profile. Frequently user interests drift with time. The ability to adapt fast to the current user's interests is an important feature for recommender systems. This paper presents a method for dealing with drifting interests by introducing the notion of gradual forgetting. Thus, the last observations should be more "important" for the learning algorithm than the old ones and the importance of an observation should decrease with time. The conducted experiments with a recommender system show that the gradual forgetting improves the ability to adapt to drifting user's interests. Experiments with the STAGGER problem provide additional evidences that gradual forgetting is able to improve the prediction accuracy on drifting concepts (incl. drifting user's interests). This paper addresses the task of learning concept descriptions from streams of data. As new data are obtained the concept description has to be updated regularly to include the new data. In this case we can face the problem that the concept changes over time. Hence the old data become irrelevant to the current concept and have to be removed from the training dataset. This problem is known in the area of machine learning as concept drift. We develop a mechanism that tracks changing concepts using an adaptive time window. The method uses a significance test to detect concept drift and then optimizes the size of the time window, aiming to maximise the classification accuracy on recent data. The method presented is general in nature and can be used with any learning algorithm. The method is tested with three standard learning algorithms (kNN, ID3 and NBC). Three datasets have been used in these experiments. The experimental results provide evidence that the suggested forgetting mechanism is able significantly to improve predictive accuracy on changing concepts. The paper presents a method for gradual forgetting, which is applied for learning drifting concepts. The approach suggests the introduction of a time-based forgetting function, which makes the last observations more significant for the learning algorithms than the old ones. The importance of examples decreases with time. Namely, the forgetting function provides each training example with a weight, according its appearance over time. The used learning algorithms are modified to be able to deal with weighted examples. Experiments are conducted with the STAGGER problem using NBC and ID3 algorithms. The results provide evidences that the utilization of gradual forgetting is able to improve the predictive accuracy on drifting concepts. The method was also implemented for a recommender system, which learns about user from observations. The results from experiments with this application show that the method is able to improve the system’s adaptability to drifting user’s interest. 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. Since they do not require complicated parameterization, they are simpler to use and more robust than comparable heuristics. Experiments with simulated concept drift scenarios based on real-world text data compare the new methods with other window management approaches. We show that they can effectively select an appropriate window size, example selection, and example weighting, respectively, in a robust way. We also explain how the proposed example selection and weighting approaches can be turned into incremental approaches. Since most evaluation methods for machine learning, like e.g. cross-validation, assume that the examples are independent and identically distributed, which is clearly unrealistic in the case of concept drift, alternative evaluation schemes are used to estimate and optimize the performance of each learning step within the concept drift handling frameworks as well as to evaluate and compare the different frameworks.