Search

We state and analyze the first active learning algorithm that finds an @e-optimal hypothesis in any hypothesis class, when the underlying distribution has arbitrary forms of noise. The algorithm, A^2 (for Agnostic Active), relies only upon the assumption that it has access to a stream of unlabeled examples drawn i.i.d. from a fixed distribution. We show that A^2 achieves an exponential improvement (i.e., requires only O([email protected]) samples to find an @e-optimal classifier) over the usual sample complexity of supervised learning, for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere.

We show that one cannot rule out even a single possibility for the value of an arithmetic circuit on a given input using an NC algorithm, unless P collapses to NC (i.e., unless all problems with polynomial-time sequential solutions can be efficiently parallelized). In other words, excluding any possible solution in this case is as hard as actually finding the solution. The result is robust with respect to NC algorithms that err (i.e., exclude the correct value) with small probability. We also show that P collapses all the way down to NC1 when the characteristic of the field that the problem is over is sufficiently large (but in this case under a stronger elimination hypothesis that depends on the characteristic).

An important property of networked systems is their robustness against removal of network nodes, through either random node failure or targeted attack. Although design methods have been proposed for creating, ab initio, a network that has optimal robustness according to a given measure, one is often instead faced with an existing network that cannot feasibly be substantially modified or redesigned, yet whose robustness can be improved by a lesser degree of modification. We present empirical results that show how robustness, as measured either by the size of the largest connected component or by the shortest path length between pairs of nodes, is affected by several different strategies that alter the network by rewiring a fraction of the edges or by adding new edges. We find that a modest alteration of an initially ‘scale-free’ network can usefully improve robustness against attack, particularly when the fraction of attacked nodes is small, and we identify modification schemes that are most effective for this purpose.

We investigate the complexity of enumerative approximation of two fundamental problems in linear algebra, computing the rank and the determinant of a matrix. We show that both are as hard to approximate (in the enumerative sense) as to compute exactly. In particular, if there exists an enumerator that, given a matrix over some finite field, outputs a list of constantly many numbers, one of which is guaranteed to be the rank of the matrix, then it can be determined in AC 0 (with oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the enumerator is an FL function, then the problem of computing the rank is in FL. For the determinant function we establish the following two results: (1) If the determinant is poly-enumerable in logspace, then it can be computed exactly in FL. (2) For any prime p , if computing the determinant modulo p is (p-1) -enumerable in FL (i.e., if one could eliminate a single possible value for the determinant modulo p ), then the determinant modulo p can be computed in FL. Because there is a close connection between these two functions and logspace counting classes, we hope that our results can give a better understanding of the power of counting in logspace, and the relationships among the complexity classes sandwiched between NL and uniform TC 1 .

Given a set of n points in general position in the plane, where n is even, a halving line is a line going through two of the points and cutting the remaining set of n−2 points in half. Let h(n) denote the maximum number of halving lines that can be realized by a planar set of n points. The problem naturally generalizes to pseudoconfigurations; denote the maximum number of halving pseudolines over all pseudoconfigurations of size n by ĥ(n). We prove that ĥ(12)=18 and that the pseudoconfiguration on 12 points with the largest number of halving pseudolines is unique up to isomorphism; this pseudoconfiguration is realizable, implying h(12)=18. We show several structural results that substantially reduce the computational effort needed to obtain the exact value of ĥ(n) for larger n. Using these techniques, we enumerate all topologically distinct, simple arrangements of 10 pseudolines with a marked cell. We also prove that h(14)=22 using certain properties of degree sequences of halving edges graphs.

An important issue in visualizing categorical data is how to order categorical values -- non-numeric values that do not have a natural ordering, which makes it difficult to map them to visual coordinates. The focus of this paper is on constructing categorical orderings efficiently without compromising their visual quality. In order to avoid the inherent intractability of previous discrete formulations, we consider a continuous relaxation of the problem solvable exactly using the spectral method. The latter is based on computing certain algebraic information about the similarity matrix of the dataset. However, even computing the similarity matrix itself is prohibitive for large datasets. In order to achieve greater efficiency, we propose a new multi-level scheme based on an approximate representation of the matrix. We show that it sufficient to compute only a small portion of the matrix of size linear in the number of objects, as opposed to quadratic, to guarantee a small probability of approximation error. Thus an effective ordering can be constructed without actually having to compute {\it most} pairwise similarities of values. Experiments have been conducted to qualitatively verify the effectiveness of resulting visualizations.

We present a family of pairwise tournaments reducing k-class classification to binary classification. These reductions are provably robust against a constant fraction of binary errors, and match the best possible computation and regret up to a constant.

We present an algorithm, called the Offset Tree, for learning to make decisions in situations where the payoff of only one choice is observed, rather than all choices. The algorithm reduces this setting to binary classification, allowing one to reuse of any existing, fully supervised binary classification algorithm in this partial information setting. We show that the Offset Tree is an optimal reduction to binary classification. In particular, it has regret at most $(k-1)$ times the regret of the binary classifier it uses (where $k$ is the number of choices), and no reduction to binary classification can do better. This reduction is also computationally optimal, both at training and test time, requiring just $O(\log_2 k)$ work to train on an example or make a prediction. Experiments with the Offset Tree show that it generally performs better than several alternative approaches.

We present a tree data structure for fast nearest neighbor operations in general n-point metric spaces (where the data set consists of n points). The data structure requires O(n) space regardless of the metric's structure yet maintains all performance properties of a navigating net (Krauthgamer & Lee, 2004b). If the point set has a bounded expansion constant c, which is a measure of the intrinsic dimensionality, as defined in (Karger & Ruhl, 2002), the cover tree data structure can be constructed in O (c6n log n) time. Furthermore, nearest neighbor queries require time only logarithmic in n, in particular O (c12 log n) time. Our experimental results show speedups over the brute force search varying between one and several orders of magnitude on natural machine learning datasets.

We present a reduction from cost-sensitive classification to binary classification based on (a modification of) error correcting output codes. The reduction satisfies the property that e regret for binary classification implies l2-regret of at most 2e for cost estimation. This has several implications: Any regret-minimizing online algorithm for 0/1 loss is (via the reduction) a regret-minimizing online cost-sensitive algorithm. In particular, this means that online learning can be made to work for arbitrary (i.e., totally unstructured) loss functions. The output of the reduction can be thresholded so that e regret for binary classification implies at most 4${\sqrt{\epsilon Z}}$ regret for cost-sensitive classification where Z is the expected sum of costs. For multiclass problems, e binary regret translates into l2-regret of at most 4e in the estimation of class probabilities. For classification, this implies at most 4${\sqrt{\epsilon}}$ multiclass regret.

We investigate the complexity of enumerative approximation of two elementary problems in linear algebra, computing the rank and the determinant of a matrix. In particular, we show that if there exists an enumerator that, given a matrix, outputs a list of constantly many numbers, one of which is guaranteed to be the rank of the matrix, then it can be determined in AC0 (with oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the enumerator is an FL function, then the problem of computing the rank is in FL. The result holds for matrices over any commutative ring whose size grows at most polynomially with the size of the matrix. The existence of such an enumerator also implies a slightly stronger collapse of the exact counting logspace hierarchy. For the determinant function we establish the following two results: (1) If the determinant is poly-enumerable in logspace, then it can be computed exactly in FL. (2) For any prime p, if computing the determinant modulo p is (p-1)-enumerable in FL, then computing the determinant modulo p can be done in FL. This gives a new perspective on the approximability of many elementary linear algebra problems equivalent to computing the rank or the determinant.