37611527
The Importance of Convexity in Learning with Squared Loss
We show that if the closure of a function class F under the metric induced by some probability distribution is not convex, then the sample complexity for agnostically learning F with squared loss (using only hypotheses in F) is /spl Omega/(ln(1//spl delta/)//spl epsiv//sup 2/) where 1-/spl delta/ is the probability of success and /spl epsiv/ is the required accuracy. In comparison, if the class F is convex and has finite pseudodimension, then the sample complexity is O(1//spl epsiv/(ln(1//spl epsiv/)+ln(1/b)). If a nonconvex class F has finite pseudodimension, then the sample complexity for agnostically learning the closure of the convex hull of F, is O(1//spl epsiv/(1//spl epsiv/(ln(1//spl epsiv/)+ln(1//spl delta/)). Hence, for agnostic learning, learning the convex hull provides better approximation capabilities with little sample complexity penalty.
573509
Boosting the margin: A new explanation for the effectiveness of voting methods
One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and often is observed to decrease even after the training error reaches zero. In this paper, we show that this phenomenon is related to the distribution of margins of the training examples with respect to the generated voting classification rule, where the margin of an example is simply the difference between the number of correct votes and the maximum number of votes received by any incorrect label. We show that techniques used in the analysis of Vapnik's support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error. We also show theoretically and experimentally that boosting is especially effective at increasing the margins of the training examples. Finally, we compare our explanation to those based on the bias-variance
361066
Efficient agnostic learning of neural networks with bounded fan-in
We show that the class of two-layer neural networks with bounded fan-in is efficiently learnable in a realistic extension to the probably approximately correct (PAC) learning model. In this model, a joint probability distribution is assumed to exist on the observations and the learner is required to approximate the neural network which minimizes the expected quadratic error. As special cases, the model allows learning real-valued functions with bounded noise, learning probabilistic concepts, and learning the best approximation to a target function that cannot be well approximated by the neural network. The networks we consider have real-valued inputs and outputs, an unlimited number of threshold hidden units with bounded fan-in, and a bound on the sum of the absolute values of the output weights. The number of computation steps of the learning algorithm is bounded by a polynomial in 1//spl epsiv/, 1//spl delta/, n and B where /spl epsiv/ is the desired accuracy, /spl delta/ is the probability that the algorithm fails, n is the input dimension, and B is the bound on both the absolute value of the target (which may be a random variable) and the sum of the absolute values of the output weights. In obtaining the result, we also extended some results on iterative approximation of functions in the closure of the convex hull of a function class and on the sample complexity of agnostic learning with the quadratic loss function.
37770250
A Theoretical Analysis of Query Selection for Collaborative Filtering
We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple and fast algorithm for a theoretical model of this problem with a provable approximation guarantee, and prove that solving the problem exactly is NP-Hard.
2748729
Partially Supervised Classification of Text Documents
We investigate the following problem: Given a set of documents of a particular topic or class P , and a large set M of mixed documents that contains documents from class P and other types of documents, identify the documents from class P in M . The key feature of this problem is that there is no labeled nonP document, which makes traditional machine learning techniques inapplicable, as they all need labeled documents of both classes. We call this problem partially supervised classification. In this paper, we show that this problem can be posed as a constrained optimization problem and that under appropriate conditions, solutions to the constrained optimization problem will give good solutions to the partially supervised classification problem. We present a novel technique to solve the problem and demonstrate the effectiveness of the technique through extensive experimentation.
1176859
RankCut - A Domain Independent Forward Pruning Method for Games
Forward pruning, also known as selective search, is now employed in many strong game-playing programs. In this paper, we introduce RankCut – a domain independent forward pruning technique which makes use of move ordering, and prunes once no better move is likely to be available. Since gameplaying programs already perform move ordering to improve the performance of αβ search, this information is available at no extra cost. As RankCut uses additional information untapped by current forward pruning techniques, RankCut is a complementary forward pruning method that can be used with existing methods, and is able to achieve improvements even when conventional pruning techniques are simultaneously employed. We implemented RankCut in a modern open-source chess program, CRAFTY. RankCut reduces the game-tree size by approximately 10%-40% for search depths 8-12 while retaining tactical reliability, when implemented alongside CRAFTY’s existing forward pruning techniques.
2807949
Search K Nearest Neighbors on Air
While the K-Nearest-Neighbor (KNN) problem is well studied in the traditional wired, disk-based client-server environment, it has not been tackled in a wireless broadcast environment. In this paper, the problem of organizing location dependent data and answering KNN queries on air are investigated. The linear property of wireless broadcast media and power conserving requirement of mobile devices make this problem particularly interesting and challenging. An efficient data organization, called sorted list, and the corresponding search algorithm are proposed and compared with the well-known spatial index, R-Tree. In addition, we develop an approximate search scope to guide the search at the very beginning of the search process and a learning algorithm to adapt the search scope during the search to improve energy and access efficiency. Simulation based performance evaluation is conducted to compare sorted list and R-Tree. The results show that the utilization of search scope and learning algorithm improves search efficiency of both index mechanisms significantly. While R-Tree is more power efficient when a large number of nearest neighbors is requested, the sorted list has better access efficiency and less power consumption when the number of nearest neighbors is small.
9445139
JAM: Java Agents for Meta-Learning over Distributed Databases
In this paper, we describe the JAM system, a distributed, scalable and portable agent-based data mining system that employs a general approach to scaling data mining applications that we call meta-learning. JAM provides a set of learning programs, implemented either as JAVA applets or applications, that compute models over data stored locally at a site. JAM also provides a set of meta-learning agents for combining multiple models that were learned (perhaps) at different sites. It employs a special distribution mechanism which allows the migration of the derived models or classifier agents to other remote sites. We describe the overall architecture of the JAM system and the specific implementation currently under development at Columbia University. One of JAM's target applications is fraud and intrusion detection in financial information systems. A brief description of this learning task and JAM's applicability are also described. Interested users may download JAM from http://www.cs.columbia.edu/~sal/JAM/PROJECT.
86127
Symbolic-numeric sparse interpolation of multivariate polynomials
We consider the problem of sparse interpolation of an approximate multivariate black-box polynomial in floating-point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust solutions. We note the similarity between the exact Ben-Or/Tiwari sparse interpolation algorithm and the classical Prony's method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony's method. We analyze the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications.
15482443
Applying data mining to intrusion detection: the quest for automation, efficiency, and credibility
Intrusion detection is an essential component of the layered computer security mechanisms. It requires accurate and efficient models for analyzing a large amount of system and network audit data. This paper is an overview of our research in applying data mining techniques to build intrusion detection models. We describe a framework for mining patterns from system and network audit data, and constructing features according to analysis of intrusion patterns. We discuss approaches for improving the run-time efficiency as well as the credibility of detection models. We report the ideas, algorithms, and prototype systems we have developed, and discuss open research problems.
22742444
Distributed scalable location data management system based on the GALIS architecture
A challenging task in the LBS system engineering is to implement a highly scalable system architecture which can manage moderate-size configurations handling thousands of moving items as well as upper-end configurations handling millions of moving items. The architecture named the GALIS is a cluster-based distributed computing system architecture that consists of multiple data processors, each dedicated to keeping records relevant to a different geographical zone and a different time zone. In this paper, we explain a prototype location data management system structuring major components of GALIS by employing the TMO programming scheme, including the execution engine middleware developed to support real-time distributed object programming and real-time distributed computing system design. We present how to generate realistic location sensing reports and how to process such location reports and location-related queries. Some experimental results showing performance factors regarding distributed query processing are also explained.