Shai Fine

TCS Journal 2008 Journal Article

A probabilistic alternative to regression suites

• Shady Copty
• Shai Fine
• Shmuel Ur
• Elad Yom-Tov
• Avi Ziv

Automated regression suites are essential in developing large applications, while maintaining reasonable quality and timetables. The main argument against the automation of regression suites, in addition to the cost of creation and maintenance, is the observation that if you run the same test many times, it becomes increasingly less likely to find bugs. To alleviate such problems, a new regression suite practice, using random test generators to create regression suites on-the-fly, is becoming more common. In this practice, instead of maintaining tests, we generate test suites on-the-fly by choosing several specifications and generating a number of tests from each specification. We describe techniques for optimizing random generated test suites. We first show how the set cover greedy algorithms, commonly used for selecting tests for regression suites, may be adapted to selecting specifications for randomly generated regression suites. We then introduce a new class of greedy algorithms, referred to as future-aware greedy algorithms. The algorithms are computationally efficient and generate more effective regression suites.

ICML Conference 2002 Conference Paper

Discriminative Feature Selection via Multiclass Variable Memory Markov Model

• Noam Slonim
• Gill Bejerano
• Shai Fine
• Naftali Tishby

TCS Journal 2002 Journal Article

Query by committee, linear separation and random walks

• Shai Fine
• Ran Gilad-Bachrach
• Eli Shamir

A long-standing goal in the realm of Machine Learning is to minimize sample-complexity, i. e. to reduce as much as possible the number of examples used in the course of learning. The Active Learning paradigm is one such method aimed at achieving this goal by transforming the learner from a passive participant in the information gathering process to an active one. Vaguely speaking, the learner tries to minimize the number of labeled instances used in the course of learning, relaying also on unlabelled instances in order to acquire the needed information whenever possible. The reasoning comes from many real-life problems where the teacher's activity is an expensive resource (e. g. text categorization, part of speech tagging). The Query By Committee (QBC) (Seung et al. , Query by committee, Proceedings of the Fifth Workshop on Computational Learning theory, Morgan Kaufman, San Mateo, CA, 1992, pp. 287–294) is an Active Learning algorithm acting in the Bayesian model of concept learning, (Haussler et al. , Mach. Learning 14 (1994) 83) i. e. it assumes that the concept to be learned is chosen according to some fixed and known distribution. Trying to apply the QBC algorithm for learning the class of linear separators, one faces the problem of implementing the mechanism of sampling hypotheses (the Gibbs oracle). The major problem is computational-complexity, since the straightforward Monte Carlo method takes exponential time. In this paper we address the problems involved in the implementation of such a mechanism. We show how to convert them to questions about sampling from convex bodies or approximating the volume of such bodies. Similar problems have recently been solved in the field of computational geometry based on random walks. These techniques enable us to device efficient implementations of the QBC algorithm. We also give few improvements and corrections to the QBC algorithm, the most important one is dropping the Bayes assumption when the concept classes possess a sort of symmetry property (which holds for linear separators). We draw attention to a useful geometric lemma which bounds the maximal radius of a ball contained in a convex body. Finally, this paper exhibits a connection between random walks and certain Machine Learning notions such as ε-net and support vector machines.

JMLR Journal 2001 Journal Article

Efficient SVM Training Using Low-Rank Kernel Representations (Kernel Machines Section)

• Shai Fine
• Katya Scheinberg

SVM training is a convex optimization problem which scales with the training set size rather than the feature space dimension. While this is usually considered to be a desired quality, in large scale problems it may cause training to be impractical. The common techniques to handle this difficulty basically build a solution by solving a sequence of small scale subproblems. Our current effort is concentrated on the rank of the kernel matrix as a source for further enhancement of the training procedure. We first show that for a low rank kernel matrix it is possible to design a better interior point method (IPM) in terms of storage requirements as well as computational complexity. We then suggest an efficient use of a known factorization technique to approximate a given kernel matrix by a low rank matrix, which in turn will be used to feed the optimizer. Finally, we derive an upper bound on the change in the objective function value based on the approximation error and the number of active constraints (support vectors). This bound is general in the sense that it holds regardless of the approximation method.

NeurIPS Conference 2001 Conference Paper

Incremental Learning and Selective Sampling via Parametric Optimization Framework for SVM

• Shai Fine
• Katya Scheinberg

We propose a framework based on a parametric quadratic program(cid: 173) ming (QP) technique to solve the support vector machine (SVM) training problem. This framework, can be specialized to obtain two SVM optimization methods. The first solves the fixed bias prob(cid: 173) lem, while the second starts with an optimal solution for a fixed bias problem and adjusts the bias until the optimal value is found. The later method can be applied in conjunction with any other ex(cid: 173) isting technique which obtains a fixed bias solution. Moreover, the second method can also be used independently to solve the com(cid: 173) plete SVM training problem. A combination of these two methods is more flexible than each individual method and, among other things, produces an incremental algorithm which exactly solve the 1-Norm Soft Margin SVM optimization problem. Applying Selec(cid: 173) tive Sampling techniques may further boost convergence.

NeurIPS Conference 1997 Conference Paper

Agnostic Classification of Markovian Sequences

• Ran El-Yaniv
• Shai Fine
• Naftali Tishby

Classification of finite sequences without explicit knowledge of their statistical nature is a fundamental problem with many important applications. We propose a new information theoretic approach to this problem which is based on the following ingredients: (i) se(cid: 173) quences are similar when they are likely to be generated by the same source; (ii) cross entropies can be estimated via "universal compres(cid: 173) sion"; (iii) Markovian sequences can be asymptotically-optimally merged. With these ingredients we design a method for the classification of discrete sequences whenever they can be compressed. We introduce the method and illustrate its application for hierarchical clustering of languages and for estimating similarities of protein sequences. 1