The Robustness of the p-Norm Algorithms

We consider two on-line learning frameworks: binary classification through linear threshold functions and linear regression. We study a family of on-line algorithms, called p-norm algorithms, introduced by Grove, Littlestone and Schuurmans in the context of deterministic binary classification. We show how to adapt these algorithms for use in the regression setting, and prove worst-case bounds on the square loss, using a technique from Kivinen and Warmuth. As pointed out by Grove, et al., these algorithms can be made to approach a version of the classification algorithm Winnow as p goes to infinity; similarly they can be made to approach the corresponding regression algorithm EG in the limit. Winnow and EG are notable for having loss bounds that grow only logarithmically in the dimension of the instance space. Here we describe another way to use the p-norm algorithms to achieve this logarithmic behavior. With the way to use them that we propose, it is less critical than with Winnow and EG to retune the parameters of the algorithm as the learning task changes. Since the correct setting of the parameters depends on characteristics of the learning task that are not typically known a priori by the learner, this gives the p-norm algorithms a desireable robustness. Our elaborations yield various new loss bounds in these on-line settings. Some of these bounds improve or generalize known results. Others are incomparable.     

General Convergence Results for Linear Discriminant Updates

The problem of learning linear-discriminant concepts can be solved by various mistake-driven update procedures, including the Winnow family of algorithms and the well-known Perceptron algorithm. In this paper we define the general class of quasi-additive algorithms, which includes Perceptron and Winnow as special cases. We give a single proof of convergence that covers a broad subset of algorithms in this class, including both Perceptron and Winnow, but also many new algorithms. Our proof hinges on analyzing a generic measure of progress construction that gives insight as to when and how such algorithms converge.Our measure of progress construction also permits us to obtain good mistake bounds for individual algorithms. We apply our unified analysis to new algorithms as well as existing algorithms. When applied to known algorithms, our method automatically produces close variants of existing proofs (recovering similar bounds)—thus showing that, in a certain sense, these seemingly diverse results are fundamentally isomorphic. However, we also demonstrate that the unifying principles are more broadly applicable, and analyze a new class of algorithms that smoothly interpolate between the additive-update behavior of Perceptron and the multiplicative-update behavior of Winnow.     

基于Winnow算法的垃圾邮件过滤器研究

实现了基本的Winnow算法、Balanced Winnow算法和带反馈学习功能的Winnow算法,并将其成功地应用于大规模垃圾邮件过滤,分别在SEWM2007和SEWM2008数据集上对上述三个算法进行了对比实验.实验结果表明,Winnow算法及其变体在分类效果和效率上都优于Logiisfic算法.     

Direct and indirect algorithms for on-line learning of disjunctions

It is easy to design on-line learning algorithms for learning k out of n variable monotone disjunctions by simply keeping one weight per disjunction. Such algorithms use roughly O(n^k) weights which can be prohibitively expensive. Surprisingly, algorithms like Winnow require only n weights (one per variable or attribute) and the mistake bound of these algorithms is not too much worse than the mistake bound of the more costly algorithms. The purpose of this paper is to investigate how exponentially many weights can be collapsed into only O(n) weights. In particular, we consider probabilistic assumptions that enable the Bayes optimal algorithm's posterior over the disjunctions to be encoded with only O(n) weights. This results in a new O(n) algorithm for learning disjunctions which is related to the Bylander's BEG algorithm originally introduced for linear regression. Besides providing a Bayesian interpretation for this new algorithm, we are also able to obtain mistake bounds for the noise free case resembling those that have been derived for the Winnow algorithm. The same techniques used to derive this new algorithm also provide a Bayesian interpretation for a normalized version of Winnow.     

Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning

A Markov chain Monte Carlo method has previously been introduced to estimate weighted sums in multiplicative weight update algorithms when the number of inputs is exponential. However, the original algorithm still required extensive simulation of the Markov chain in order to get accurate estimates of the weighted sums. We propose an optimized version of the original algorithm that produces exactly the same classifications while often using fewer Markov chain simulations. We also apply three other sampling techniques and empirically compare them with the original Metropolis sampler to determine how effective each is in drawing good samples in the least amount of time, in terms of accuracy of weighted sum estimates and in terms of Winnow’s prediction accuracy. We found that two other samplers (Gibbs and Metropolized Gibbs) were slightly better than Metropolis in their estimates of the weighted sums. For prediction errors, there is little difference between any pair of MCMC techniques we tested. Also, on the data sets we tested, we discovered that all approximations of Winnow have no disadvantage when compared to brute force Winnow (where weighted sums are exactly computed), so generalization accuracy is not compromised by our approximation. This is true even when very small sample sizes and mixing times are used. An early version of this paper appeared as Tao and Scott (2003).     

An online framework for catching top spreaders and scanners

Flow level information is important for many applications in network measurement and analysis. In this work, we tackle the “Top Spreaders” and “Top Scanners” problems, where hosts that are spreading the largest numbers of flows, especially small flows, must be efficiently and accurately identified. The identification of these top users can be very helpful in network management, traffic engineering, application behavior analysis, and anomaly detection.We propose novel streaming algorithms and a “Filter-Tracker-Digester” framework to catch the top spreaders and scanners online. Our framework combines sampling and streaming algorithms, as well as deterministic and randomized algorithms, in such a way that they can effectively help each other to improve accuracy while reducing memory usage and processing time. To our knowledge, we are the first to tackle the “Top Scanners” problem in a streaming way. We address several challenges, namely: traffic scale, skewness, speed, memory usage, and result accuracy. The performance bounds of our algorithms are derived analytically, and are also evaluated by both real and synthetic traces, where we show our algorithm can achieve accuracy and speed of at least an order of magnitude higher than existing approaches.     

A Winnow-Based Approach to Context-Sensitive Spelling Correction

A large class of machine-learning problems in natural language require the characterization of linguistic context. Two characteristic properties of such problems are that their feature space is of very high dimensionality, and their target concepts depend on only a small subset of the features in the space. Under such conditions, multiplicative weight-update algorithms such as Winnow have been shown to have exceptionally good theoretical properties. In the work reported here, we present an algorithm combining variants of Winnow and weighted-majority voting, and apply it to a problem in the aforementioned class: context-sensitive spelling correction. This is the task of fixing spelling errors that happen to result in valid words, such as substituting to for too, casual for causal, and so on. We evaluate our algorithm, WinSpell, by comparing it against BaySpell, a statistics-based method representing the state of the art for this task. We find: (1) When run with a full (unpruned) set of features, WinSpell achieves accuracies significantly higher than BaySpell was able to achieve in either the pruned or unpruned condition; (2) When compared with other systems in the literature, WinSpell exhibits the highest performance; (3) While several aspects of WinSpell's architecture contribute to its superiority over BaySpell, the primary factor is that it is able to learn a better linear separator than BaySpell learns; (4) When run on a test set drawn from a different corpus than the training set was drawn from, WinSpell is better able than BaySpell to adapt, using a strategy we will present that combines supervised learning on the training set with unsupervised learning on the (noisy) test set.     

数字图像配准快速算法：阈值序列的自适应生成研究

本文基于配准点的误差特点，指出初始阈值序列的合理形式是直线；基于后验信息（匹配过程），提出了两种自适应阈值序列算法，理论分析与实验结果均表明所提出的算法是有效的。     

实体关系自动抽取

实体关系抽取是信息抽取领域中的重要研究课题。本文使用两种基于特征向量的机器学习算法,Winnow 和支持向量机(SVM) ,在2004 年ACE(Automatic Content Extraction) 评测的训练数据上进行实体关系抽取实验。两种算法都进行适当的特征选择,当选择每个实体的左右两个词为特征时,达到最好的抽取效果,Winnow和SVM算法的加权平均F-Score 分别为73108 %和73127 %。可见在使用相同的特征集,不同的学习算法进行实体关系的识别时,最终性能差别不大。因此使用自动的方法进行实体关系抽取时,应当集中精力寻找好的特征。     

Comments on “Accelerated learning algorithm for multilayerperceptrons: optimization layer by layer”

In the above paper by Ergezinger and Thomsen (ibid. vol.6 (1991)), a new method for training multilayer perceptron, called optimization layer by layer (OLL), was introduced. The present paper analyzes the performance of OLL. We show, from theoretical considerations, that the amount of work required with OLL-learning scales as the third power of the network size, compared with the square of the network size for commonly used conjugate gradient (CG) training algorithms. This theoretical estimate is confirmed through a practical example. Thus, although OLL is shown to function very well for small neural networks (less than about 500 weights per layer), it is slower than CG for large neural networks. Next, we show that OLL does not always improve on the accuracy that can be obtained with CG. It seems that the final accuracy that can be obtained depends strongly on the initial network weights.     

基于PP-PicoDet技术的智能垃圾分类

目前在垃圾分类目标检测上大多采用YOLOv5系列算法,该算法在相同参数量的情况下,检测精度和检测速度都相对不太高,难以满足实际应用需求。论文对基于PP-PicoDet技术的垃圾分类目标检测应用进行了研究,并将其与几种常见的垃圾分类目标检测算法进行实验对比分析;结果表明,PP-PicoDet算法能够在使用更少的参数量的情况下,实现较高的检测精度和速度,能够满足移动端部署需求。     

Dynamic processing allocation in video

Large stores of digital video pose severe computational challenges to existing video analysis algorithms. In applying these algorithms, users must often trade off processing speed for accuracy, as many sophisticated and effective algorithms require large computational resources that make it impractical to apply them throughout long videos. One can save considerable effort by applying these expensive algorithms sparingly, directing their application using the results of more limited processing. We show how to do this for retrospective video analysis by modeling a video using a chain graphical model and performing inference both to analyze the video and to direct processing. We apply our method to problems in background subtraction and face detection, and show in experiments that this leads to significant improvements over baseline algorithms.     

PAC Analogues of Perceptron and Winnow Via Boosting the Margin

We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit sample complexity bounds remarkably similar to those of known online algorithms such as Perceptron and Winnow, thus suggesting that these well-studied online algorithms in some sense correspond to instances of boosting. We show that the new algorithms can be viewed as natural PAC analogues of the online p-norm algorithms which have recently been studied by Grove, Littlestone, and Schuurmans (1997, Proceedings of the Tenth Annual Conference on Computational Learning Theory (pp. 171–183) and Gentile and Littlestone (1999, Proceedings of the Twelfth Annual Conference on Computational Learning Theory (pp. 1–11). As special cases of the algorithm, by taking p = 2 and p = we obtain natural boosting-based PAC analogues of Perceptron and Winnow respectively. The p = case of our algorithm can also be viewed as a generalization (with an improved sample complexity bound) of Jackson and Craven's PAC-model boosting-based algorithm for learning sparse perceptrons (Jackson & Craven, 1996, Advances in neural information processing systems 8, MIT Press). The analysis of the generalization error of the new algorithms relies on techniques from the theory of large margin classification.     

Applying genetic algorithms to game search trees

 Computer game playing is an important artificial intelligence research field in that the results can usually be applied to other related fields. One of the key computer-game-playing issues is designing effective search algorithms. Traditional search algorithms incur great temporal and spatial complexities when exploring deeply into search trees to find good next moves. Searches are thus usually not deep enough to derive good playing strategies. In this paper, we focus on one-player game search trees, and propose a genetic-algorithm-based approach to enhancing the speed and accuracy of game tree searches. Experiments show that our algorithm can improve solution accuracy and search speed.     

基于内容的垃圾邮件过滤技术综述

垃圾邮件问题日益严重,受到研究人员的广泛关注。基于内容的过滤是当前解决垃圾邮件问题的主流技术之一。目前基于内容的垃圾邮件过滤主要包括基于规则的方法和基于概率统计的方法。本文综述了目前用于垃圾邮件过滤研究的各种语料和评价方法,并总结了目前使用的垃圾邮件过滤技术以及它们之间的对比实验,包括Ripper、决策树、Rough Set 、Rocchio 、Boosting、Bayes、kNN、SVM、Winnow 等等。实验结果表明,Boosting、Flexible Bayes、SVM、Winnow 方法是目前较好的垃圾邮件过滤方法,它们在评测语料上的结果已经达到很高水平,但是,要走向真正实用化,还有很多的工作要做。     

A Multi-Frame Structure-from-Motion Algorithm under Perspective Projection

We present a fast, robust algorithm for multi-frame structure from motion from point features which works for general motion and large perspective effects. The algorithm is for point features but easily extends to a direct method based on image intensities. Experiments on synthetic and real sequences show that the algorithm gives results nearly as accurate as the maximum likelihood estimate in a couple of seconds on an IRIS 10000. The results are significantly better than those of an optimal two-image estimate. When the camera projection is close to scaled orthographic, the accuracy is comparable to that of the Tomasi/Kanade algorithm, and the algorithms are comparably fast. The algorithm incorporates a quantitative theoretical analysis of the bas-relief ambiguity and exemplifies how such an analysis can be exploited to improve reconstruction. Also, we demonstrate a structure-from-motion algorithm for partially calibrated cameras, with unknown focal length varying from image to image. Unlike the projective approach, this algorithm fully exploits the partial knowledge of the calibration. It is given by a simple modification of our algorithm for calibrated sequences and is insensitive to errors in calibrating the camera center. Theoretically, we show that unknown focal-length variations strengthen the effects of the bas-relief ambiguity. This paper includes extensive experimental studies of two-frame reconstruction and the Tomasi/Kanade approach in comparison to our algorithm. We find that two-frame algorithms are surprisingly robust and accurate, despite some problems with local minima. We demonstrate experimentally that a nearly optimal two-frame reconstruction can be computed quickly, by a minimization in the motion parameters alone. Lastly, we show that a well known problem with the Tomasi/Kanade algorithm is often not a significant one.     

Collective decision with 100 Kilobots: speed versus accuracy in binary discrimination problems

Achieving fast and accurate collective decisions with a large number of simple agents without relying on a central planning unit or on global communication is essential for developing complex collective behaviors. In this paper, we investigate the speed versus accuracy trade-off in collective decision-making in the context of a binary discrimination problem—i.e., how a swarm can collectively determine the best of two options. We describe a novel, fully distributed collective decision-making strategy that only requires agents with minimal capabilities and is faster than previous approaches. We evaluate our strategy experimentally, using a swarm of 100 Kilobots, and we study it theoretically, using both continuum and finite-size models. We find that the main factor affecting the speed versus accuracy trade-off of our strategy is the agents’ neighborhood size—i.e., the number of agents with whom the current opinion of each agent is shared. The proposed strategy and the associated theoretical framework can be used to design swarms that take collective decisions at a given level of speed and/or accuracy.     

An information-theoretic analysis on the interactions of variables in combinatorial optimization problems

In optimization problems, the contribution of a variable to fitness often depends on the states of other variables. This phenomenon is referred to as epistasis or linkage. In this paper, we show that a new theory of epistasis can be established on the basis of Shannon's information theory. From this, we derive a new epistasis measure called entropic epistasis and some theoretical results. We also provide experimental results verifying the measure and showing how it can be used for designing efficient evolutionary algorithms.     

一种新的主题网络爬虫爬行策略

为了解决传统主题网络爬虫准确度低或者爬行速度慢的问题,提出一种新的主题网络爬虫爬行策略,主要针对二次爬行过程进行改进。在传统的主题网络爬虫流程中增加一份经验树,将基于内容分析和基于链接分析两种不同的相关度分析算法相结合,并且可以保存爬虫爬行过程中所得到的经验,实现对后续爬行的指导。实验结果表明通过改进后的策略实现的主题网络爬虫在性能上有较大提升。     

An analysis of diversity measures

Diversity among the base classifiers is deemed to be important when constructing a classifier ensemble. Numerous algorithms have been proposed to construct a good classifier ensemble by seeking both the accuracy of the base classifiers and the diversity among them. However, there is no generally accepted definition of diversity, and measuring the diversity explicitly is very difficult. Although researchers have designed several experimental studies to compare different diversity measures, usually confusing results were observed. In this paper, we present a theoretical analysis on six existing diversity measures (namely disagreement measure, double fault measure, KW variance, inter-rater agreement, generalized diversity and measure of difficulty), show underlying relationships between them, and relate them to the concept of margin, which is more explicitly related to the success of ensemble learning algorithms. We illustrate why confusing experimental results were observed and show that the discussed diversity measures are naturally ineffective. Our analysis provides a deeper understanding of the concept of diversity, and hence can help design better ensemble learning algorithms. Editor: Tom Fawcett