Minimax classifiers based on neural networks

The problem of designing a classifier when prior probabilities are not known or are not representative of the underlying data distribution is discussed in this paper. Traditional learning approaches based on the assumption that class priors are stationary lead to sub-optimal solutions if there is a mismatch between training and future (real) priors. To protect against this uncertainty, a minimax approach may be desirable. We address the problem of designing a neural-based minimax classifier and propose two different algorithms: a learning rate scaling algorithm and a gradient-based algorithm. Experimental results show that both succeed in finding the minimax solution and it is also pointed out the differences between common approaches to cope with this uncertainty in priors and the minimax classifier.     

Asynchronous broadcast-based decentralized learning in sensor networks

Abstract

In this paper, we study the problem of decentralized learning in sensor networks in which local learners estimate and reach consensus to the quantity of interest inferred globally while communicating only with their immediate neighbours. The main challenge lies in reducing the communication cost in the network, which involves inter-node synchronisation and data exchange. To address this issue, a novel asynchronous broadcast-based decentralized learning algorithm is proposed. Furthermore, we prove that the iterates generated by the developed decentralized method converge to a consensual optimal solution (model). Numerical results demonstrate that it is a promising approach for decentralized learning in sensor networks.     

The Strength of Weak Learnability

This paper addresses the problem of improving the accuracy of an hypothesis output by a learning algorithm in the distribution-free (PAC) learning model. A concept class is learnable (or strongly learnable) if, given access to a source of examples of the unknown concept, the learner with high probability is able to output an hypothesis that is correct on all but an arbitrarily small fraction of the instances. The concept class is weakly learnable if the learner can produce an hypothesis that performs only slightly better than random guessing. In this paper, it is shown that these two notions of learnability are equivalent.A method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy. This construction may have practical applications as a tool for efficiently converting a mediocre learning algorithm into one that performs extremely well. In addition, the construction has some interesting theoretical consequences, including a set of general upper bounds on the complexity of any strong learning algorithm as a function of the allowed error .     

Belief revision via Lamarckian evolution

We present a system for performing belief revision in a multi-agent environment. The system is called GBR (Genetic Belief Revisor) and it is based on a genetic algorithm. In this setting, different individuals are exposed to different experiences. This may happen because the world surrounding an agent changes over time or because we allow agents exploring different parts of the world. The algorithm permits the exchange of chromosomes from different agents and combines two different evolution strategies, one based on Darwin’s and the other on Lamarck’s evolutionary theory. The algorithm therefore includes also a Lamarckian operator that changes the memes of an agent in order to improve their fitness. The operator is implemented by means of a belief revision procedure that, by tracing logical derivations, identifies the memes leading to contradiction. Moreover, the algorithm comprises a special crossover mechanism for memes in which a meme can be acquired from another agent only if the other agent has “accessed” the meme, i.e. if an application of the Lamarckian operator has read or modified the meme. Experiments have been performed on the η-queen problem and on a problem of digital circuit diagnosis. In the case of the η-queen problem, the addition of the Lamarckian operator in the single agent case improves the fitness of the best solution. In both cases the experiments show that the distribution of constraints, even if it may lead to a reduction of the fitness of the best solution, does not produce a significant reduction. Evelina Lamma, Ph.D.: She is Full Professor at the University of Ferrara. She got her degree in Electrical Engineering at the University of Bologna in 1985, and her Ph.D. in Computer Science in 1990. Her research activity centers on extensions of logic programming languages and artificial intelligence. She was coorganizers of the 3rd International Workshop on Extensions of Logic Programming ELP92, held in Bologna in February 1992, and of the 6th Italian Congress on Artificial Intelligence, held in Bologna in September 1999. Currently, she teaches Artificial Intelligence and Fondations of Computer Science. Fabrizio Riguzzi, Ph.D.: He is Assistant Professor at the Department of Engineering of the University of Ferrara, Italy. He received his Laurea from the University of Bologna in 1995 and his Ph.D. from the University of Bologna in 1999. He joined the Department of Engineering of the University of Ferrara in 1999. He has been a visiting researcher at the University of Cyprus and at the New University of Lisbon. His research interests include: data mining (and in particular methods for learning from multirelational data), machine learning, belief revision, genetic algorithms and software engineering. Luís Moniz Pereira, Ph.D.: He is Full Professor of Computer Science at Departamento de Informática, Universidade Nova de Lisboa, Portugal. He received his Ph.D. in Artificial Intelligence from Brunel University in 1974. He is the director of the Artificial Intelligence Centre (CENTRIA) at Universidade Nova de Lisboa. He has been elected Fellow of the European Coordinating Committee for Artificial Intelligence in 2001. He has been a visiting Professor at the U. California at Riverside, USA, the State U. NY at Stony Brook, USA and the U. Bologna, Italy. His research interests include: knowledge representation, reasoning, learning, rational agents and logic programming.     

An analysis of four missing data treatment methods for supervised learning

One relevant problem in data quality is missing data. Despite the frequent occurrence and the relevance of the missing data problem, many machine learning algorithms handle missing data in a rather naive way. However, missing data treatment should be carefully treated, otherwise bias might be introduced into the knowledge induced. In this work, we analyze the use of the k-nearest neighbor as an imputation method. Imputation is a term that denotes a procedure that replaces the missing values in a data set with some plausible values. One advantage of this approach is that the missing data treatment is independent of the learning algorithm used. This allows the user to select the most suitable imputation method for each situation. Our analysis indicates that missing data imputation based on the k-nearest neighbor algorithm can outperform the internal methods used by C4.5 and CN2 to treat missing data, and can also outperform the mean or mode imputation method, which is a method broadly used to treat missing values.     

Complexity theoretic hardness results for query learning

We investigate the complexity of learning for the well-studied model in which the learning algorithm may ask membership and equivalence queries. While complexity theoretic techniques have previously been used to prove hardness results in various learning models, these techniques typically are not strong enough to use when a learning algorithm may make membership queries. We develop a general technique for proving hardness results for learning with membership and equivalence queries (and for more general query models). We apply the technique to show that, assuming , no polynomial-time membership and (proper) equivalence query algorithms exist for exactly learning read-thrice DNF formulas, unions of halfspaces over the Boolean domain, or some other related classes. Our hardness results are representation dependent, and do not preclude the existence of representation independent algorithms.?The general technique introduces the representation problem for a class F of representations (e.g., formulas), which is naturally associated with the learning problem for F. This problem is related to the structural question of how to characterize functions representable by formulas in F, and is a generalization of standard complexity problems such as Satisfiability. While in general the representation problem is in , we present a theorem demonstrating that for "reasonable" classes F, the existence of a polynomial-time membership and equivalence query algorithm for exactly learning F implies that the representation problem for F is in fact in co-NP. The theorem is applied to prove hardness results such as the ones mentioned above, by showing that the representation problem for specific classes of formulas is NP-hard. Received: December 6, 1994     

Combined method of genetic programming and association rule algorithm

Genetic programming (GP) usually has a wide search space and a high flexibility. Therefore, GP may search for global optimum solution. But, in general, GPs learning speed is not so fast. An apriori algorithm is one of association rule algorithms. It can be applied to a large database. But it is difficult to define its parameters without experience. We propose a rule generation technique from a database using GP combined with an association rule algorithm. It takes rules generated by the association rule algorithm as initial individual of GP. The learning speed of GP is improved by the combined algorithm. To verify the effectiveness of the proposed method, we apply it to the decision tree construction problem from the University of California at Irvine (UCI) machine-learning repository, and rule discovery problem from the occurrence of the hypertension database. We compare the results of the proposed method with prior ones.     

Relational IBL in classical music

It is well known that many hard tasks considered in machine learning and data mining can be solved in a rather simple and robust way with an instance- and distance-based approach. In this work we present another difficult task: learning, from large numbers of complex performances by concert pianists, to play music expressively. We model the problem as a multi-level decomposition and prediction task. We show that this is a fundamentally relational learning problem and propose a new similarity measure for structured objects, which is built into a relational instance-based learning algorithm named DISTALL. Experiments with data derived from a substantial number of Mozart piano sonata recordings by a skilled concert pianist demonstrate that the approach is viable. We show that the instance-based learner operating on structured, relational data outperforms a propositional k-NN algorithm. In qualitative terms, some of the piano performances produced by DISTALL after learning from the human artist are of substantial musical quality; one even won a prize in an international ‘computer music performance’ contest. The experiments thus provide evidence of the capabilities of ILP in a highly complex domain such as music. Editors: Tamás Horváth and Akihiro Yamamoto     

Can Finite Samples Detect Singularities of Real-Valued Functions?

Commonly, in learning theory, the task of the learner is to identify an unknown target object. We consider a variant of this basic task in which the learner is required only to decide whether the unknown target has a certain property. We allow an infinite learning process in which the learner is required to eventually arrive at the correct answer. We say that a problem for which such a learning algorithm exists is Decidable In the Limit (DIL). We analyze the class of DIL problems and provide a necessary and sufficient condition for the membership of a decision problem in this class. We offer an algorithm for any DIL problem, and apply it to several types of learning tasks. We introduce an extension of the usual Inductive Inference learning model—Inductive Inference with a Cheating Teacher. In this model the teacher may choose to present to the learner, not only a language belonging to the agreed-upon family of languages, but also an arbitrary language outside this family. In such a case we require that the learner will be able to eventually detect the faulty choice made by the teacher. We show that such a strong type of learning is possible, and there exist learning algorithms that will fail only on arbitrarily small sets of faulty languages. Furthermore, if an a priori probability distribution P , according to which f is being chosen, is available to the algorithm, then it can be strengthened into a finite algorithm. More precisely, for many distributions P , there exists a polynomial function, l , such that, for every 0 < δ < 1 , there is an algorithm using at most l(log(δ)) many probes that succeeds on more than (1-δ) of the f 's (as measured by P ). We believe that the new approach presented here will be found useful for many further applications. Received February 14, 1997; revised July 6, 1997, and July 18, 1997.     

针对非平衡警情数据改进的K-Means-Boosting-BP模型

目的 掌握警情的时空分布规律,通过机器学习算法建立警情时空预测模型,制定科学的警务防控方案,有效抑制犯罪的发生,是犯罪地理研究的重点。已有研究表明,警情时空分布多集中在中心城区或居民密集区,在时空上属于非平衡数据,这种数据的非平衡性通常导致在该数据上训练的模型成为弱学习器,预测精度较低。为解决这种非平衡数据的回归问题,提出一种基于KMeans均值聚类的Boosting算法。方法 该算法以Boosting集成学习算法为基础,应用GA-BP神经网络生成基分类器,借助KMeans均值聚类算法进行基分类器的集成,从而实现将弱学习器提升为强学习器的目标。结果 与常用的解决非平衡数据回归问题的Synthetic Minority Oversampling Technique Boosting算法,简称SMOTEBoosting算法相比,该算法具有两方面的优势：1）在降低非平衡数据中少数类均方误差的同时也降低了数据的整体均方误差,SMOTEBoosting算法的整体均方误差为2.14E-04,KMeans-Boosting算法的整体均方误差达到9.85E-05;2）更好地平衡了少数类样本识别的准确率和召回率,KMeans-Boosting算法的召回率约等于52%,SMOTEBoosting算法的召回率约等于91%;但KMeans-Boosting算法的准确率等于85%,远高于SMOTEBoosting算法的19%。结论 KMeans-Boosting算法能够显著的降低非平衡数据的整体均方误差,提高少数类样本识别的准确率和召回率,是一种有效地解决非平衡数据回归问题和分类问题的算法,可以推广至其他需要处理非平衡数据的领域中。     

Multi-Class Learning by Smoothed Boosting

AdaBoost.OC has been shown to be an effective method in boosting “weak” binary classifiers for multi-class learning. It employs the Error-Correcting Output Code (ECOC) method to convert a multi-class learning problem into a set of binary classification problems, and applies the AdaBoost algorithm to solve them efficiently. One of the main drawbacks with the AdaBoost.OC algorithm is that it is sensitive to the noisy examples and tends to overfit training examples when they are noisy. In this paper, we propose a new boosting algorithm, named “MSmoothBoost”, which introduces a smoothing mechanism into the boosting procedure to explicitly address the overfitting problem with AdaBoost.OC. We proved the bounds for both the empirical training error and the marginal training error of the proposed boosting algorithm. Empirical studies with seven UCI datasets and one real-world application have indicated that the proposed boosting algorithm is more robust and effective than the AdaBoost.OC algorithm for multi-class learning. Editor: Nicolo Cesa-Bianchi     

A new approach to the learning effect: Beyond the learning curve restrictions

In this paper, we bring into the scheduling field a new model of the learning effect, where in two ways the existing approach is generalized. First we relax one of the rigorous constraints, and thus in our model each job can provide different experience to the processor. Second we formulate the job processing time as a non-increasing k-stepwise function, that, in general, is not restricted to a certain learning curve, thereby it can accurately fit every possible shape of a learning function. Furthermore, we prove that the problem of makespan minimization with the considered model is polynomially solvable if every job provides the same experience to the processor, and it becomes NP-hard if the experiences are diversified. The most essential result is a pseudopolynomial time algorithm that solves optimally the makespan minimization problem with any function of an experience-based learning model reduced into the form of the k-stepwise function.     

Learning from positive and unlabeled examples

In many machine learning settings, labeled examples are difficult to collect while unlabeled data are abundant. Also, for some binary classification problems, positive examples which are elements of the target concept are available. Can these additional data be used to improve accuracy of supervised learning algorithms? We investigate in this paper the design of learning algorithms from positive and unlabeled data only. Many machine learning and data mining algorithms, such as decision tree induction algorithms and naive Bayes algorithms, use examples only to evaluate statistical queries (SQ-like algorithms). Kearns designed the statistical query learning model in order to describe these algorithms. Here, we design an algorithm scheme which transforms any SQ-like algorithm into an algorithm based on positive statistical queries (estimate for probabilities over the set of positive instances) and instance statistical queries (estimate for probabilities over the instance space). We prove that any class learnable in the statistical query learning model is learnable from positive statistical queries and instance statistical queries only if a lower bound on the weight of any target concept f can be estimated in polynomial time. Then, we design a decision tree induction algorithm POSC4.5, based on C4.5, that uses only positive and unlabeled examples and we give experimental results for this algorithm. In the case of imbalanced classes in the sense that one of the two classes (say the positive class) is heavily underrepresented compared to the other class, the learning problem remains open. This problem is challenging because it is encountered in many real-world applications.     

Destriping multiple sensor imagery by improved histogram matching

Abstract

Sensor stripes evident in multisensor imagery can cause subsequent image classification to fail, if not removed properly. Of the destriping algorithms investigated, the one published by Horn and Woodham seemed to be the most promising, although, due to an inherent conceptual flaw, it can produce unexpected results. The problem with the original algorithm of Horn and Woodham arises from the fact that under certain circumstances it is extremely sensitive to statistically insignificant differences in the image data recorded by the individual sensors. This problem can be overcome by acquiring image statistics from homogeneous sub-images only.     

An event-based model for continuous media data on heterogeneous disk servers

Over the last few years, there has been intense work on the problem of retrieval of continuous media (CM) data from disk. However, no single unified framework exists within which such retrieval problems can be studied. In this paper, we first propose a formal model for CM data retrieval from heterogeneous disk servers. This model can be used to characterize CM data retrieval problems independently of how data is laid out on disk, and what objectives (e.g., minimize client delay, maximize buffer utilization, etc.) the system manager is interested in. We then show how using this formal model, we can neatly define what it means to optimally handle events that occur in movie-on-demand (MOD) systems. Examples of such events include new clients entering the system, old clients leaving the system, continuing clients doing pause, rewind and fast-forward operations. Multiple events may occur simultaneously and we show how such events trigger state transitions in the system. We then develop an algorithm called the QuickSOL algorithm that handles events occurring in MOD systems. This algorithm works in two phases: in the first phase, it quickly finds a way of handling as many of the events occurring at time t as possible. In the second phase, it optimizes the solution found in the first phase. The advantage is that the algorithm can be interrupted anytime after the first phase is completed. We report on experiments showing that QuickSOL works well in practice.     

An adaptive heuristic to the bounded-diameter minimum spanning tree problem

Given a graph G and a bound d?≥?2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight subject to the constraint that its diameter does not exceed d. This problem is NP-hard; several heuristics have been proposed to find near-optimal solutions to it in reasonable times. A decentralized learning automata-based algorithm creates spanning trees that honor the diameter constraint. The algorithm rewards a tree if it has the smallest weight found so far and penalizes it otherwise. As the algorithm proceeds, the choice probability of the tree converges to one; and the algorithm halts when this probability exceeds a predefined value. Experiments confirm the superiority of the algorithm over other heuristics in terms of both speed and solution quality.     

A novel discrete particle swarm optimization algorithm for solving bayesian network structures learning problem

ABSTRACT

Bayesian network is an effective representation tool to describe the uncertainty of the knowledge in artificial intelligence. One important method to learning Bayesian network from data is to employ a search procedure to explore the space of networks and a scoring metric to evaluate each candidate structure. In this paper, a novel discrete particle swarm optimization algorithm has been designed to solve the problem of Bayesian network structures learning. The proposed algorithm not only maintains the search advantages of the classical particle swarm optimization but also matches the characteristics of Bayesian networks. Meanwhile, mutation and neighbor searching operators have been used to overcome the drawback of premature convergence and balance the exploration and exploitation abilities of the particle swarm optimization. The experimental results on benchmark networks illustrate the feasibility and effectiveness of the proposed algorithm, and the comparative experiments indicate that our algorithm is highly competitive compared to other algorithms.     

深度学习辅助的多行人跟踪算法

目的 目标的长距离跟踪一直是视频监控中最具挑战性的任务之一。现有的目标跟踪方法在存在遮挡、目标消失再出现等情况下往往会丢失目标,无法进行持续有效的跟踪。一方面目标消失后再次出现时,将其作为新的目标进行跟踪的做法显然不符合实际需求;另一方面,在跟踪过程中当相似的目标出现时,也很容易误导跟踪器把该相似对象当成跟踪目标,从而导致跟踪失败。为此,提出一种基于目标识别辅助的跟踪算法来解决这个问题。方法 将跟踪问题转化为寻找帧间检测到的目标之间对应关系问题,从而在目标消失再现后,采用深度学习网络实现有效的轨迹恢复,改善长距离跟踪效果,并在一定程度上避免相似目标的干扰。结果 通过在标准数据集上与同类算法进行对比实验,本文算法在目标受到遮挡、交叉运动、消失再现的情况下能够有效地恢复其跟踪轨迹,改善跟踪效果,从而可以对多个目标进行持续有效的跟踪。结论 本文创新性地提出了一种结合基于深度学习的目标识别辅助的跟踪算法,实验结果证明了该方法对遮挡重现后的目标能够有效的恢复跟踪轨迹,适用在监控视频中对多个目标进行持续跟踪。     

矩阵低秩表示的目标跟踪算法

目的 目标跟踪中,遮挡、强烈光照及运动模糊等干扰对跟踪精度的影响较大,其为目标外观的观测建模精度带来一定的困难。此外,很多现有算法在观测建模中都以向量形式表示样本数据,使得样本数据原有结构及其各像素的潜在关系被有意改变,从而导致观测模型数据维度及计算复杂度的提高。方法 本文通过深入研究跟踪框架的观测建模问题,提出一种新颖的基于矩阵低秩表示的观测建模方法及其相应的似然度测度函数,使得跟踪算法能够充分挖掘样本数据的潜在特征结构,从而更加精确探测目标在遮挡或强烈光照等各种复杂干扰下的外观变化。同时,以矩阵形式表述样本信号的数据格式,使得其视觉特征的空间分布保留完好,并有效降低数据维度和计算复杂度。结果 本文跟踪算法在富有挑战性干扰因素的跟踪环境中体现出更为鲁棒的跟踪性能,能够较好地解决跟踪中遮挡或强烈光照所引起的模型退化和漂移等问题。在10个经典测试视频中,本文跟踪算法的平均中心点误差为5.29像素,平均跟踪重叠率为78%,平均跟踪成功率为98.28%,均优于其他同类算法。结论 本文以2维矩阵数据原型为载体,提出了一种新的多任务观测建模框架和最大似然度估计模型。实验数据的定性与定量分析结果表明,本文算法与一些优秀的同类算法相比,其跟踪建模精度达到相同甚至更高的水平。     

Bin Packing with Rejection Revisited

We consider the following generalization of bin packing. Each item has a size in (0,1] associated with it, as well as a rejection cost, that an algorithm must pay if it chooses not to pack this item. The cost of an algorithm is the sum of all rejection costs of rejected items plus the number of unit sized bins used for packing all other items. We first study the offline version of the problem and design an APTAS for it. This is a non-trivial generalization of the APTAS given by Fernandez de la Vega and Lueker for the standard bin packing problem. We further give an approximation algorithm of an absolute approximation ratio 3/2, where this value is best possible unless P=NP.