Estimating Basic Characteristics of Arrival Processes in Telecommunication Networks by Empirical Data

Considering the realistic teletraffic analysis in advanced telecommunication networks, the estimation of basic characteristics of arrival processes by empirical data is an important subject of current research. Using independent observations of the interarrival times between events and the mean numbers of events in intervals of fixed length, we propose methods to estimate the intensity of a nonhomogeneous arrival stream, particularly a Poisson process, and the renewal function of a renewal process. We formulate the estimation task as stochastically ill-posed problem and apply procedures for the stabilization of the estimates.     

Selective Sampling for Nearest Neighbor Classifiers

Most existing inductive learning algorithms work under the assumption that their training examples are already tagged. There are domains, however, where the tagging procedure requires significant computation resources or manual labor. In such cases, it may be beneficial for the learner to be active, intelligently selecting the examples for labeling with the goal of reducing the labeling cost. In this paper we present LSS—a lookahead algorithm for selective sampling of examples for nearest neighbor classifiers. The algorithm is looking for the example with the highest utility, taking its effect on the resulting classifier into account. Computing the expected utility of an example requires estimating the probability of its possible labels. We propose to use the random field model for this estimation. The LSS algorithm was evaluated empirically on seven real and artificial data sets, and its performance was compared to other selective sampling algorithms. The experiments show that the proposed algorithm outperforms other methods in terms of average error rate and stability.     

Anytime learning of anycost classifiers

The classification of new cases using a predictive model incurs two types of costs—testing costs and misclassification costs. Recent research efforts have resulted in several novel algorithms that attempt to produce learners that simultaneously minimize both types. In many real life scenarios, however, we cannot afford to conduct all the tests required by the predictive model. For example, a medical center might have a fixed predetermined budget for diagnosing each patient. For cost bounded classification, decision trees are considered attractive as they measure only the tests along a single path. In this work we present an anytime framework for producing decision-tree based classifiers that can make accurate decisions within a strict bound on testing costs. These bounds can be known to the learner, known to the classifier but not to the learner, or not predetermined. Extensive experiments with a variety of datasets show that our proposed framework produces trees with lower misclassification costs along a wide range of testing cost bounds.     

An advanced theory for multi-wave open path optical absorption spectroscopy measurements

A new version of the multi-wave open path optical absorption spectroscopy method is herewith presented for continuous measurements of multiple airborne pollutants along an open light path. It involves a standard least squares procedure that minimizes deviations of the calculated optical thickness of the monitoring path from the measured thickness. A novel feature of the proposed method consists of interpreting the influence of error sources as a discrepancy between sounding spectra, emitting to the reference and working paths, produced by these very errors. It is shown that this discrepancy results in a systematic error in the calculated trace gas concentrations, and its elimination transforms the optical open path meter into an absolute meter.

The advantages of the proposed approach are revealed when estimating the role of inaccuracies in signal measurements, wavelength scale lock-in, working wavelength setting, stability of the source of radiation, and inaccuracies in the parameters of the calculating method. The special benefit of the proposed multi-wave optical absorption spectroscopy method lies in using an excess of working wavelengths for reducing the influence of various error sources.     

Information Filtering: Selection Mechanisms in Learning Systems

Knowledge has traditionally been considered to have a beneficial effect on the performance of problem solvers but recent studies indicate that knowledge acquisition is not necessarily a monotonically beneficial process, because additional knowledge sometimes leads to a deterioration in system performance. This paper is concerned with the problem of harmful knowledge: that is, knowledge whose removal would improve a system's performance. In the first part of the paper a unifying framework, called theinformation filtering model, is developed to define the various alternative methods for eliminating such knowledge from a learning system where selection processes, called filters, may be inserted to remove potentially harmful knowledge. These filters are termed selective experience, selective attention, selective acquisition, selective retention, and selective utilization. The framework can be used by developers of learning systems as a guide for selecting an appropriate filter to reduce or eliminate harmful knowledge.In the second part of the paper, the framework is used to identify a suitable filter for solving a problem caused by the acquisition of harmful knowledge in a learning system calledLassy.Lassy is a system that improves the performance of a PROLOG interpreter by utilizing acquired domain specific knowledge in the form of lemmas stating previously proved results. It is shown that the particular kind of problems that arise with this system are best solved using a novel utilization filter that blocks the use of lemmas in attempts to prove subgoals that have a high probability of failing.     

Experience Selection and Problem Choice in an Exploratory Learning System

A fully autonomous exploratory learning system must perform two tasks that are not required of supervised learning systems: experience selection and problem choice. Experience selection is the process of choosing informative training examples from the space of all possible examples. Problem choice is the process of identifying defects in the domain theory and determining which should be remedied next. These processes are closely related because the degree to which a specific experience is informative depends on the particular defects in the domain theory that the system is attempting to remedy. In this article we propose a general control structure for exploratory learning in which problem choice by an information-theoretic curiosity heuristic: the problem chosen then guides the selection of training examples. An implementation of an exploratory learning system based on this control structure is described, and a series of experimental results are presented.     

Exploration Strategies for Model-based Learning in Multi-agent Systems: Exploration Strategies

An agent that interacts with other agents in multi-agent systems can benefit significantly from adapting to the others. When performing active learning, every agent's action affects the interaction process in two ways: The effect on the expected reward according to the current knowledge held by the agent, and the effect on the acquired knowledge, and hence, on future rewards expected to be received. The agent must therefore make a tradeoff between the wish to exploit its current knowledge, and the wish to explore other alternatives, to improve its knowledge for better decisions in the future. The goal of this work is to develop exploration strategies for a model-based learning agent to handle its encounters with other agents in a common environment. We first show how to incorporate exploration methods usually used in reinforcement learning into model-based learning. We then demonstrate the risk involved in exploration—an exploratory action taken by the agent can yield a better model of the other agent but also carries the risk of putting the agent into a much worse position.We present the lookahead-based exploration strategy that evaluates actions according to their expected utility, their expected contribution to the acquired knowledge, and the risk they carry. Instead of holding one model, the agent maintains a mixed opponent model, a belief distribution over a set of models that reflects its uncertainty about the opponent's strategy. Every action is evaluated according to its long run contribution to the expected utility and to the knowledge regarding the opponent's strategy. Risky actions are more likely to be detected by considering their expected outcome according to the alternative models of the opponent's behavior. We present an efficient algorithm that returns an almost optimal exploration plan against the mixed model and provide a proof of its correctness and an analysis of its complexity.We report experimental results in the Iterated Prisoner's Dilemma domain, comparing the capabilities of the different exploration strategies. The experiments demonstrate the superiority of lookahead-based exploration over other exploration methods.     

Feature Generation Using General Constructor Functions

Most classification algorithms receive as input a set of attributes of the classified objects. In many cases, however, the supplied set of attributes is not sufficient for creating an accurate, succinct and comprehensible representation of the target concept. To overcome this problem, researchers have proposed algorithms for automatic construction of features. The majority of these algorithms use a limited predefined set of operators for building new features. In this paper we propose a generalized and flexible framework that is capable of generating features from any given set of constructor functions. These can be domain-independent functions such as arithmetic and logic operators, or domain-dependent operators that rely on partial knowledge on the part of the user. The paper describes an algorithm which receives as input a set of classified objects, a set of attributes, and a specification for a set of constructor functions that contains their domains, ranges and properties. The algorithm produces as output a set of generated features that can be used by standard concept learners to create improved classifiers. The algorithm maintains a set of its best generated features and improves this set iteratively. During each iteration, the algorithm performs a beam search over its defined feature space and constructs new features by applying constructor functions to the members of its current feature set. The search is guided by general heuristic measures that are not confined to a specific feature representation. The algorithm was applied to a variety of classification problems and was able to generate features that were strongly related to the underlying target concepts. These features also significantly improved the accuracy achieved by standard concept learners, for a variety of classification problems.     

Learning to bid in bridge

Bridge bidding is considered to be one of the most difficult problems for game-playing programs. It involves four agents rather than two, including a cooperative agent. In addition, the partial observability of the game makes it impossible to predict the outcome of each action. In this paper we present a new decision-making algorithm that is capable of overcoming these problems. The algorithm allows models to be used for both opponent agents and partners, while utilizing a novel model-based Monte Carlo sampling method to overcome the problem of hidden information. The paper also presents a learning framework that uses the above decision-making algorithm for co-training of partners. The agents refine their selection strategies during training and continuously exchange their refined strategies. The refinement is based on inductive learning applied to examples accumulated for classes of states with conflicting actions. The algorithm was empirically evaluated on a set of bridge deals. The pair of agents that co-trained significantly improved their bidding performance to a level surpassing that of the current state-of-the-art bidding algorithm. Editors: Michael Bowling, Johannes Fürnkranz, Thore Graepel, Ron Musick