Online Learning of Complex Prediction Problems Using Simultaneous Projections (2009)
Yonatan Amit, Shai Shalev-shwartz, Yoram Singer, K. Warmuth
We describe and analyze an algorithmic framework for online classification where each online trial consists of multiple prediction tasks that are tied together. We tackle the problem of updating the...
Shai Shalev-shwartz, Yoram Singer, Goal Low Regret
We don’t know in advance the best performing expert We’d like to find the best expert in an online manner We’d like to make as few filtering errors as possible This setting is called ”regret...
Robert E. Schapire, Yoram Singer
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
Shai Shalev-shwartz, Yoram Singer
Boosting algorithms build highly accurate prediction mechanisms from a collection of lowaccuracy predictors. To do so, they employ the notion of weak-learnability. The starting point of this paper is...
Efficient Projections onto the ℓ1-Ball for Learning in High Dimensions (2009)
John Duchi, Yoram Singer, Tushar Chandra
We describe efficient algorithms for projecting a vector onto the ℓ1-ball. We present two methods for projection. The first performs exact projection in O(n) expected time, where n is the dimension...
Smooth ε-Insensitive Regression by Loss (2009)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
Abstract. We describe a framework for solving regression problems by reduction to classification. Our reduction is based on symmetrization of margin-based loss functions commonly used in boosting...
THE FORGETRON: A KERNEL-BASED PERCEPTRON ON A BUDGET (2009)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
Abstract. The Perceptron algorithm, despite its simplicity, often performs well in online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernel...
Individual Sequence Prediction using Memory-efficient Context Trees (2009)
Dekel, Ofer, Shalev-Shwartz, Shai, Singer, Yoram
Context trees are a popular and effective tool for tasks such as compression, sequential prediction, and language modeling. We present an algebraic perspective of context trees for the task of...
Lavi Shpigelman, Yoram Singer, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this letter is the construction of...
INTERSPEECH 2006 Discriminative Kernel-Based Phoneme Sequence Recognition (2008)
Joseph Keshet, Shai Shalev-shwartz, Samy Bengio, Yoram Singer, Dan Chazan
We describe a new method for phoneme sequence recognition given a speech utterance, which is not based on the HMM. In contrast to HMM-based approaches, our method uses a discriminative kernel-based...
A Unified Algorithmic Approach for Efficient Online Label Ranking (2008)
Shai Shalev-shwartz, Yoram Singer
Label ranking is the task of ordering labels with respect to their relevance to an input instance. We describe a unified approach for the online label ranking task. We do so by casting the online...
Online Learning of Multiple Tasks with a Shared Loss (2008)
Ofer Dekel, Philip M. Long, Yoram Singer
We study the problem of learning multiple tasks in parallel within the online learning framework. On each online round, the algorithm receives an instance for each of the parallel tasks and responds...
Lavi Shpigelman, Rony Paz, Yoram Singer, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this paper is the construction of...
Andrea Frome, Fei Sha, Yoram Singer, Jitendra Malik
We address the problem of visual category recognition by learning an image-to-image distance function that attempts to satisfy the following property: the distance between images from the same...
A Large Margin Algorithm for Speech-to-Phoneme and Music-to-Score Alignment (2008)
Joseph Keshet, Shai Shalev-shwartz, Yoram Singer, Dan Chazan
Abstract — We describe and analyze a discriminative algorithm for learning to align an audio signal with a given sequence of events that tag the signal. We demonstrate the applicability of our...
THE FORGETRON: A KERNEL-BASED PERCEPTRON ON A BUDGET ∗ (2008)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
Abstract. The Perceptron algorithm, despite its simplicity, often performs well in online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernel...
Ofer Dekel, Christopher D. Manning, Yoram Singer
Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions from...
A Primal-Dual Perspective of Online Learning Algorithms ⋆ (2008)
Shai Shalev-shwartz, Yoram Singer
Abstract. We describe a novel framework for the design and analysis of online learning algorithms based on the notion of duality in constrained optimization. We cast a sub-family of universal online...
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm that achieves almost the same wealth as the best constantrebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm employs...
In this paper we examine the problem of estimating the parameters of a multinomial distribution over a large number of discrete outcomes, most of which do not appear in the training data. We analyze...
Aldebaro Klautau, Nikola Jevtić, Alon Orlitsky, Yoram Singer
A common way of constructing a multiclass classifier is by combining the outputs of several binary ones, according to an error-correcting output code (ECOC) scheme. The combination is typically done...
Eleazar Eskin, Yoram Singer, William Stafford Noble
substitution matrices to estimate probability distributions for
A Temporal Kernel-Based Model for TrackingHand-Movements from Neural Activities (2008)
Lavi Shpigelman, Koby Crammer, Rony Paz, Eilon Vaadia, Yoram Singer
In this paper we examine the problem of estimating the parameters of a multinomial distribution over a large number of discrete outcomes,most of which do not appear in the training data. We analyze...
Lavi Shpigelman, Yoram Singer, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this letter is the construction of...
Koby Crammer, Jaz Kandola, Yoram Singer
Online algorithms for classification often require vast amounts of memory and computation time when employed in conjunction with kernel functions. In this paper we describe and analyze a simple...
Ofer Dekel, Christopher D. Manning, Yoram Singer
Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions from...
Andrea Frome, Jitendra Malik, Yoram Singer
In this paper we introduce and experiment with a framework for learning local perceptual distance functions for visual recognition. We learn a distance function for each training image as a...
Koby Crammer, Jaz Kandola, Yoram Singer
Online algorithms for classification often require vast amounts of memory and computation time when employed in conjunction with kernel functions. In this paper we describe and analyze a simple...
Ofer Dekel, Christopher D. Manning, Yoram Singer
Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions from...
Online Classification for Complex Problems Using Simultaneous Projections (2008)
Amit, Yonatan, Shalev-Shwartz, Shai, Singer, Yoram
We describe and analyze an algorithmic framework for online classification where each online trial consists of {\em multiple} prediction tasks that are tied together. We tackle the problem of...
Efficient projections onto the ℓ1-ball for learning in high dimensions (2008)
John Duchi, Shai Shalev-shwartz, Yoram Singer, Tushar Chandra
We describe efficient algorithms for projecting a vector onto the ℓ1-ball. We present two methods for projection. The first performs exact projection in O(n) expected time, where n is the dimension...
Theory, 2000. Logistic Regression, AdaBoost and Bregman Distances (2007)
Michael Collins, Robert E. Schapire, Yoram Singer
An extended abstract of this journal submission
Robert E. Schapire, Yoram Singer
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
Raj D. Iyer, David D. Lewis, Robert E. Schapire, Yoram Singer, Amit Singhal
RankBoost is a recently proposed algorithm for learning ranking functions. It is simple to implement and has strong justifications from computational learning theory. We describe the algorithm and...
Yoram Singer, Prof Naftali Tishby, Peter Dayan, Shlomo Dubnov, Shai Fine, Yoav Freund, ...
2 1 Introduction 4 2 Dynamical Encoding of Cursive Handwriting 14 2.1 Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 2.2 The Cycloidal Model : : : :...
Theory and Applications of Predictors That Specialize (2007)
Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called "experts." These simple algorithms belong to...
A Markovian Lattice Model for the Acquisition of Morphological Structure (2007)
Leonid Kontorovich, Dana Ron, Yoram Singer
We describe a new formalism for word morphology. Our model views word generation as a random walk on a lattice of units where each unit is a set of (short) strings. The model naturally incorporates...
A Markov Model for the Acquisition of Morphological Structure (2007)
Leonid Kontorovich, Dana Ron, Yoram Singer
We describe a new formalism for word morphology. Our model views word generation as a random walk on a trellis of units where each unit is a set of (short) strings. The model naturally incorporates...
pere ira©research, att. tom Beyond Word N-Grams (2007)
Fernando C. Pereira, Yoram Singer, Naftali Tishby
s inger©cs, huj i. ac. il
Lavi Shpigelman, Yoram Singer, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this paper is the construction of...
PrFQ: Probabilistic Fair Queuing (2007)
Tal Anker, Roi Cohen, Danny Dolev, Yoram Singer
Abstract---Packet scheduling constitutes the core problem in efficient fair allocation of bandwidth to competing flows. To date, numerous algorithms for packet scheduling have been suggested and...
Embedding Spiking Neurons, Lavi Shpigelman, Yoram Singer, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this paper is the construction of...
Aldebaro Klautau, Alon Orlitsky, Yoram Singer
A common way of constructing a multiclass classifier is by combining the outputs of several binary ones, according to an error-correcting output code (ECOC) scheme. The combination is typically done...
A Primal-Dual Perspective of Online Learning Algorithms (2007)
Shalev-Shwartz, Shai, Singer, Yoram
We describe a novel framework for the design and analysis of online learning algorithms based on the notion of duality in constrained optimization. We cast a sub-family of universal online bounds as...
Pegasos: Primal Estimated sub-GrAdient SOlver for SVM (2007)
Shalev-Shwartz, Shai, Singer, Yoram, Srebro, Nathan
We describe and analyze a simple and effective iterative algorithm for solving the optimization problem cast by Support Vector Machines (SVM). Our method alternates between stochastic gradient...
A Unified Algorithmic Approach for Efficient Online Label Ranking (2007)
Shalev-Shwartz, Shai, Singer, Yoram
Label ranking is the task of ordering labels with respect to their relevance to an input instance. We describe a unified approach for the online label ranking task. We do so by casting the online...
Logarithmic regret algorithms for strongly convex repeated games (2007)
Shai Shalev-shwartz, Yoram Singer
Many problems arising in machine learning can be cast as a convex optimization problem, in which a sum of a loss term and a regularization term is minimized. For example, in Support Vector Machines...
Pegasos: Primal estimated sub-gradient solver for SVM (2007)
We describe and analyze a simple and effective iterative algorithm for solving the optimization problem cast by Support Vector Machines (SVM). Our method alternates between stochastic gradient...
Online Classification for Complex Problems Using Simultaneous Projections (2006)
Amit, Yonatan, Shalev-Shwartz, Shai, Singer, Yoram
We describe and analyze an algorithmic framework for online classification where each online trial consists of {\em multiple} prediction tasks that are tied together. We tackle the problem by...
Online multitask learning (2006)
Dekel, Ofer, Singer, Yoram, Long, Philip
We study the problem of online learning of multiple tasks in parallel. On each online round, the algorithm receives an instance and makes a prediction for each one of the parallel tasks. We consider...
Discriminative Kernel-Based Phoneme Sequence Recognition (2006)
Keshet, Joseph, Shalev-Shwartz, Shai, Bengio, Samy, Singer, Yoram, Chazan, Dan
We describe a new method for phoneme sequence recognition given a speech utterance. In contrast to HMM-based approaches, our method uses a kernel-based discriminative training procedure in which the...
Convex Repeated Games and Fenchel Duality (2006)
Shalev-Shwartz, Shai, Singer, Yoram
We describe and analyze an algorithmic framework for playing convex repeated games. In each trial of the repeated game, the first player predicts a vector and then the second player responds with a...
Convex Repeated Games and Fenchel Duality (2006)
Shalev-Shwartz, Shai, Singer, Yoram
We describe and analyze an algorithmic framework for playing convex repeated games. In each trial of the repeated game, the first player predicts a vector and then the second player responds with a...
Convex Repeated Games and Fenchel Duality (2006)
Shalev-Shwartz, Shai, Singer, Yoram
We describe and analyze an algorithmic framework for playing convex repeated games. In each trial of the repeated game, the first player predicts a vector and then the second player responds with a...
Discriminative Kernel-Based Phoneme Sequence Recognition (2006)
Keshet, Joseph, Shalev-Shwartz, Shai, Bengio, Samy, Singer, Yoram, Chazan, Dan
We describe a new method for phoneme sequence recognition given a speech utterance. In contrast to HMM-based approaches, our method uses a kernel-based discriminative training procedure in which the...
Online Passive-Aggressive Algorithms (2006)
Crammer, Koby, Dekel, Ofer, Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram
We present a family of margin based online learning algorithms for various prediction tasks. In particular we derive and analyze algorithms for binary and multiclass categorization, regression,...
A Large Margin Algorithm for Speech and Audio Segmentation (2006)
Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram, Chazan, Dan
We describe and analyze a discriminative algorithm for learning to segment an audio signal given a sequence of events that tags the signal. We demonstrate the applicability of our method through the...
Online Learning meets Optimization in the Dual (2006)
Shalev-Shwartz, Shai, Singer, Yoram
We describe a novel framework for the design and analysis of online learning algorithms based on the notion of duality in constrained optimization. We cast a sub-family of universal online bounds as...
Online Multiclass Learning by Interclass Hypothesis Sharing (2006)
Fink, Michael, Shalev-Shwartz, Shai, Singer, Yoram, Ullman, Shimon
We describe a general framework for online multiclass learning based on the notion of hypothesis sharing. In our framework sets of classes are associated with hypotheses. Thus, all classes within a...
The Forgetron: A Kernel-Based Perceptron on a Fixed Budget (2006)
Dekel, Ofer, Shalev-Shwartz, Shai, Singer, Yoram
The Perceptron algorithm, despite its simplicity, often performs well on online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernels. However,...
Online Passive-Aggressive Algorithms (2006)
Crammer, Koby, Dekel, Ofer, Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram
We present a family of margin based online learning algorithms for various prediction tasks. In particular we derive and analyze algorithms for binary and multiclass categorization, regression,...
Discriminative Kernel-Based Phoneme Sequence Recognition (2006)
Keshet, Joseph, Bengio, Samy, Chazan, Dan, Shalev-Shwartz, Shai, Singer, Yoram
We describe a new method for phoneme sequence recognition given a speech utterance. In contrast to HMM-based approaches, our method uses a kernel-based discriminative training procedure in which the...
Online classification for complex problems using simultaneous projections (2006)
Yonatan Amit, Shai Shalev-shwartz, Yoram Singer
We describe and analyze an algorithmic framework for online classification where each online trial consists of multiple prediction tasks that are tied together. We tackle the problem by defining an...
Discriminative kernel-based phoneme sequence recognition (2006)
Joseph Keshet, Samy Bengio, Dan Chazan, Shai Shalev-shwartz, Yoram Singer, Joseph Keshet, ...
Abstract. We describe a new method for phoneme sequence recognition given a speech utterance. In contrast to HMM-based approaches, our method uses a kernel-based discriminative training procedure in...
Online learning meets optimization in the dual (2006)
Shai Shalev-shwartz, Yoram Singer
Abstract. We describe a novel framework for the design and analysis of online learning algorithms based on the notion of duality in constrained optimization. We cast a sub-family of universal online...
Convex repeated games and Fenchel duality (2006)
Shai Shalev-shwartz, Yoram Singer
We describe an algorithmic framework for an abstract game which we term a convex repeated game. We show that various online learning and boosting algorithms can be all derived as special cases of our...
Online classification for complex problems using simultaneous projections (2006)
Yonatan Amit, Shai Shalev-shwartz, Yoram Singer
We describe and analyze an algorithmic framework for online classification where each online trial consists of multiple prediction tasks that are tied together. We tackle the problem of updating the...
Discriminative kernel-based phoneme sequence recognition (2006)
Joseph Keshet, Shai Shalev-shwartz, Samy Bengio, Yoram Singer, Dan Chazan
We describe a new method for phoneme sequence recognition given a speech utterance, which is not based on the HMM. In contrast to HMM-based approaches, our method uses a discriminative kernel-based...
Efficient Learning of Label Ranking by Soft Projections onto Polyhedra (2006)
Shai Shalev-Shwartz, Yoram Singer, P. Bennett, Emilio Parrado-hernández
We discuss the problem of learning to rank labels from a real valued feedback associated with each label. We cast the feedback as a preferences graph where the nodes of the graph are the labels and...
Online Passive-Aggressive Algorithms (2006)
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, Yoram Singer
We present a family of margin based online learning algorithms for various prediction tasks. In particular we derive and analyze algorithms for binary and multiclass categorization, regression,...
Peter Bühlmann, Bin Yu, Yoram Singer, Larry Wasserman
We propose Sparse Boosting (the SparseL 2 Boost algorithm), a variant on boosting with the squared error loss. SparseL 2 Boost yields sparser solutions than the previously proposed L 2 Boosting by...
Support vector machines on a budget (2006)
The standard Support Vector Machine formulation does not provide its user with the ability to explicitly control the number of support vectors used to define the generated classifier. We present a...
Convex repeated games and Fenchel duality (2006)
Shai Shalev-shwartz, Yoram Singer
We describe an algorithmic framework for an abstract game which we term a convex repeated game. We show that various online learning and boosting algorithms can be all derived as special cases of our...
Online classification for complex problems using simultaneous projections (2006)
Yonatan Amit, Shai Shalev-shwartz, Yoram Singer
We describe and analyze an algorithmic framework for online classification where each online trial consists of multiple prediction tasks that are tied together. We tackle the problem of updating the...
Online passive-aggressive algorithms (2006)
Koby Crammer, Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
We present a unified view for online classification, regression, and uniclass problems. This view leads to a single algorithmic framework for the three problems. We prove worst case loss bounds for...
Online multiclass learning by interclass hypothesis sharing (2006)
We describe a general framework for online multiclass learning based on the notion of hypothesis sharing. In our framework sets of classes are associated with hypotheses. Thus, all classes within a...
Online multiclass learning by interclass hypothesis sharing (2006)
Michael Fink, Yoram Singer, Shimon Ullman
We describe a general framework for online multiclass learning based on the notion of hypothesis sharing. In our framework sets of classes are associated with hypotheses. Thus, all classes within a...
Discriminative kernel-based phoneme sequence recognition (2006)
Joseph Keshet, Samy Bengio, Dan Chazan, Shai Shalev-shwartz, Yoram Singer, Joseph Keshet, ...
Abstract. We describe a new method for phoneme sequence recognition given a speech utterance. In contrast to HMM-based approaches, our method uses a kernel-based discriminative training procedure in...
Convex repeated games and Fenchel duality (2006)
Shai Shalev-shwartz, Yoram Singer
We describe and analyze an algorithmic framework for playing convex repeated games. In each trial of the repeated game, the first player predicts a vector and then the second player responds with a...
Efficient learning of label ranking by soft projections onto polyhedra (2006)
Yoram Singer, Kristin Bennett, Emilio Parrado-hern
We discuss the problem of learning to rank labels from a real valued feedback associated with each label. We cast the feedback as a preferences graph where the nodes of the graph are the labels and...
Online learning meets optimization in the dual (2006)
Shai Shalev-shwartz, Yoram Singer
Abstract. We describe a novel framework for the design and analysis of online learning algorithms based on the notion of duality in constrained optimization. We cast a sub-family of universal online...
Online multiclass learning by interclass hypothesis sharing (2006)
Michael Fink, Yoram Singer, Shimon Ullman
We describe a general framework for online multiclass learning based on the notion of hypothesis sharing. In our framework sets of classes are associated with hypotheses. Thus, all classes within a...
Tracking Hand Movements from Neuronal Activity with a Dynamic Kernel-Based Model (2005)
Shpigelman, Lavi, Crammer, Koby, Paz, Rony, Vaadia, Eilon, Singer, Yoram
It is well known that population activity in motor cortex can predict movement direction. This allows for development of brain machine interfaces (BMI) that read brain activity and produce movements....
Phoneme Alignment using Large Margin Techniques (2005)
Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram
Phoneme alignment is concerned with proper positioning of a sequence of phonemes in relation to continuous speech utterances. This problem is also referred to as phoneme segmentation. An accurate and...
Learning Preferences Graphs by Soft Projections onto Polyhedra (2005)
Shalev-Shwartz, Shai, Singer, Yoram
We discuss the problem of learning to predict the order of nodes in a graph from a real valued feedback associated with each node. This setting includes as special cases binary classification,...
Phoneme Alignment Based on Discriminative Learning (2005)
Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram
We propose a novel paradigm for aligning a phoneme sequence of a speech utterance with its acoustical signal counterpart. Unlike the traditional HMM-based approaches, our method utilizes a...
Data Driven Online to Batch Conversions (2005)
Online learning algorithms are typically fast, memory efficient, and simple to implement. However, many common learning problems fit more naturally in the batch learning setting. The power of online...
A New Perspective on an Old Perceptron Algorithm (2005)
Shalev-Shwartz, Shai, Singer, Yoram
We present a generalization of the Perceptron algorithm. The new algorithm performs a Perceptron-style update whenever the margin of an example is smaller than a predefined value. We derive worst...
Online Passive-Aggressive Algorithms (2005)
Crammer, Koby, Dekel, Ofer, Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram
We present a family of online learning, margin based, algorithms for various prediction tasks. In particular we derive and analyze algorithms for binary and multiclass categorization, regression,...
The Forgetron: A Kernel-Based Perceptron on a Fixed Budget (2005)
Dekel, Ofer, Shalev-Shwartz, Shai, Singer, Yoram
The Perceptron algorithm, despite its simplicity, often performs well on online classification problems. The Perceptron becomes especially effective when it is used in conjunction with kernels....
Shpigelman, Lavi, Singer, Yoram, Paz, Rony, Vaadia, Eilon
Inner-product operators, often referred to as {\em kernels} in statistical learning, define a mapping from some input space into a feature space. The focus of this paper is the construction of...
A temporal kernel-based model for tracking hand-movements from neural activities (2005)
Lavi Shpigelman, Koby Crammer, Rony Paz, Eilon Vaadia, Yoram Singer
We devise and experiment with a dynamical kernel-based system for tracking hand movements from neural activity. The state of the system corresponds to the hand location, velocity, and acceleration,...
Phoneme alignment using large margin techniques (2005)
Joseph Keshet, Shai Shalev-shwartz, Yoram Singer
Phoneme alignment is the task of proper positioning of a sequence of phonemes in relation to a corresponding continuous speech signal. This problem is also referred to as phoneme segmentation. An...
Online multitask learning (2005)
Ofer Dekel, Philip M. Long, Yoram Singer
Abstract. We study the problem of online learning of multiple tasks in parallel. On each online round, the algorithm receives an instance and makes a prediction for each one of the parallel tasks. We...
Smooth ε-insensitive regression by loss symmetrization (2005)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer, P. Bennett, Nicolò Cesa-bianchi
We describe new loss functions for regression problems along with an accompanying algorithmic framework which utilizes these functions. These loss functions are derived by symmetrization of...
The Forgetron: A kernel-based perceptron on a fixed budget (2005)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
The Perceptron algorithm, despite its simplicity, often performs well on online classification problems. The Perceptron becomes especially effective when it is used in conjunction with kernels....
Multiclass Classification with Multi-Prototype Support Vector Machines (2005)
Fabio Aiolli, Alessandro Sperduti, Yoram Singer
Winner-take-all multiclass classifiers are built on the top of a set of prototypes each representing one of the available classes. A pattern is then classified with the label associated to the most...
The Forgetron: A kernel-based perceptron on a fixed budget (2005)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
The Perceptron algorithm, despite its simplicity, often performs well in online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernels. However,...
Data driven online to batch conversions (2005)
Online learning algorithms are typically fast, memory efficient, and simple to implement. However, many common learning problems fit more naturally in the batch learning setting. The power of online...
The Forgetron: A kernel-based perceptron on a fixed budget (2005)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
The Perceptron algorithm, despite its simplicity, often performs well on online classification tasks. The Perceptron becomes especially effective when it is used in conjunction with kernels. However,...
Data driven online to batch conversions (2005)
Online learning algorithms are typically fast, memory efficient, and simple to implement. However, many common learning problems fit more naturally in the batch learning setting. The power of online...
Loss bounds for online category ranking (2005)
Abstract. Category ranking is the task of ordering labels with respect to their relevance to an input instance. In this paper we describe and analyze several algorithms for online category ranking...
A new perspective on an old perceptron algorithm (2005)
Shai Shalev-shwartz, Yoram Singer
Abstract. We present a generalization of the Perceptron algorithm. The new algorithm performs a Perceptron-style update whenever the margin of an example is smaller than a predefined value. We derive...
Large margin methods for structured and interdependent output variables (2005)
Ioannis Tsochantaridis, Google Inc, Thorsten Joachims, Thomas Hofmann, Yasemin Altun, Yoram Singer
Learning general functional dependencies between arbitrary input and output spaces is one of the key challenges in computational intelligence. While recent progress in machine learning has mainly...
Matrix exponentiated gradient updates for on-line learning and Bregman projections (2005)
Koji Tsuda, Manfred K. Warmuth, Yoram Singer
We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von...
The Forgetron: A kernel-based perceptron on a fixed budget (2005)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
The Perceptron algorithm, despite its simplicity, often performs well on online classification problems. The Perceptron becomes especially effective when it is used in conjunction with kernels....
Loss bounds for online category ranking (2005)
Abstract. Category ranking is the task of ordering labels with respect to their relevance to an input instance. In this paper we describe and analyze several algorithms for online category ranking...
Data driven online to batch conversions (2005)
Online learning algorithms are typically fast, memory efficient, and simple to implement. However, many common learning problems fit more naturally in the batch learning setting. The power of online...
Matrix exponentiated gradient updates for on-line learning and Bregman projections (2005)
Koji Tsuda, Manfred K. Warmuth, Yoram Singer
We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von...
Loss bounds for online category ranking (2005)
Abstract. Category ranking is the task of ordering labels with respect to their relevance to an input instance. In this paper we describe and analyze several algorithms for online category ranking...
Learning to Align Polyphonic Music (2004)
Shalev-Shwartz, Shai, Keshet, Joseph, Singer, Yoram
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Large Margin Hierarchical Classification (2004)
Dekel, Ofer, Keshet, Joseph, Singer, Yoram
We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree...
Leveraging the Margin More Carefully (2004)
Boosting is a popular approach for building accurate classifiers. Despite the initial popular belief, boosting algorithms do exhibit overfitting and are sensitive to label noise. Part of the...
An Online Algorithm for Hierarchical Phoneme Classification (2004)
Dekel, Ofer, Keshet, Joseph, Singer, Yoram
We present an algorithmic framework for phoneme classification where the set of phonemes is organized in a predefined hierarchical structure. This structure is encoded via a rooted tree which induces...
An Online Algorithm for Hierarchical Phoneme Classification (2004)
Dekel, Ofer, Keshet, Joseph, Singer, Yoram
We present an algorithmic framework for phoneme classification where the set of phonemes is organized in a predefined hierarchical structure. This structure is encoded via a rooted tree which induces...
The Power of Selective Memory: Self-Bounded Learning of Prediction Suffix Trees (2004)
Dekel, Ofer, Shalev-Shwartz, Shai, Singer, Yoram
Prediction suffix trees (PST) provide a popular and effective tool for tasks such as compression, classification, and language modeling. In this paper we take a decision theoretic view of PSTs....
Smooth $\eps$-Insensitive Regression by Loss ymmetrization (2004)
Dekel, Ofer, Shalev-Shwartz, Shai, Singer, Yoram
We describe new loss functions for regression problems along with an accompanying algorithmic framework which utilizes these functions. These loss functions are derived by symmetrization of...
Online and Batch Learning of Pseudo-Metrics (2004)
Shalev-Shwartz, Shai, Ng, Andrew Y., Singer, Yoram
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The...
A temporal kernel-based model for tracking hand movements fron neural activities (2004)
Shpigelman, Lavi, Crammer, Koby, Paz, Rony, Vaadia, Eilon, Singer, Yoram
We devise and experiment with a dynamical kernel-based system for tracking hand movements from neural activity. The state of the system corresponds to the hand location, velocity, and acceleration,...
Online and Batch Learning of Pseudo-Metrics (2004)
Shalev-Shwartz, Shai, Ng, Andrew Y., Singer, Yoram
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The...
Large margin hierarchical classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree...
Leveraging the margin more carefully (2004)
Boosting is a popular approach for building accurate classifiers. Despite the initial popular belief, boosting algorithms do exhibit overfitting and are sensitive to label noise. Part of the...
Research on large margin algorithms in conjunctions with kernels methods has been both exciting and successful. While there have been quite a few preliminary successes in applying kernel methods for...
Large margin hierarchical classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree...
Online algorithm for hierarchical phoneme classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
Abstract. We present an algorithmic framework for phoneme classification where the set of phonemes is organized in a predefined hierarchical structure. This structure is encoded via a rooted tree...
Online algorithm for hierarchical phoneme classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
Abstract. We present an algorithmic framework for phoneme classification where the set of phonemes is organized in a predefined hierarchical structure. This structure is encoded via a rooted tree...
Learning to align polyphonic music (2004)
Shai Shalev-shwartz, Joseph Keshet, Yoram Singer
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Online and batch learning of pseudo-metrics (2004)
Shai Shalev-shwartz, Yoram Singer, Andrew Y. Ng
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The...
Learning to align polyphonic music (2004)
Shai Shalev-shwartz, Joseph Keshet, Yoram Singer
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Learning to align polyphonic music (2004)
Shai Shalev-shwartz, Joseph Keshet, Yoram Singer
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Large margin hierarchical classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree...
The power of selective memory: selfbounded learning of prediction suffix trees (2004)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
Prediction suffix trees (PST) provide a popular and effective tool for tasks such as compression, classification, and language modeling. In this paper we take a decision theoretic view of PSTs for...
Learning to align polyphonic music (2004)
Shai Shalev-shwartz, Joseph Keshet, Yoram Singer
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Online and batch learning of pseudo-metrics (2004)
Shai Shalev-shwartz, Yoram Singer, Andrew Y. Ng
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The...
Online and Batch Learning of Pseudo-Metrics (2004)
Shai Shalev-shwartz, Yoram Singer, Andrew Y. Ng
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric.
Large margin hierarchical classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree...
Learning to align polyphonic music (2004)
Shai Shalev-shwartz, Joseph Keshet, Yoram Singer
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Online and batch learning of pseudo-metrics (2004)
Shai Shalev-shwartz, Yoram Singer, Andrew Y. Ng
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The...
Learning to align polyphonic music (2004)
Shai Shalev-shwartz, Joseph Keshet, Yoram Singer
We describe an efficient learning algorithm for aligning a symbolic representation of a musical piece with its acoustic counterpart. Our method employs a supervised learning approach by using a...
Online and batch learning of pseudo-metrics (2004)
Shai Shalev-shwartz, Yoram Singer, Andrew Y. Ng
We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The...
Large margin hierarchical classification (2004)
Ofer Dekel, Joseph Keshet, Yoram Singer
We present an algorithmic framework for supervised classification learning where the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree...
Probability estimates for multi-class classification by pairwise coupling (2004)
Ting-fan Wu, Chih-jen Lin, Ruby C. Weng, Yoram Singer
Pairwise coupling is a popular multi-class classification method that combines all comparisons for each pair of classes. This paper presents two approaches for obtaining class probabilities. Both...
The power of selective memory: selfbounded learning of prediction suffix trees (2004)
Ofer Dekel, Shai Shalev-shwartz, Yoram Singer
Prediction suffix trees (PST) provide a popular and effective tool for tasks such as compression, classification, and language modeling. In this paper we take a decision theoretic view of PSTs for...
Log-Linear Models for Label Ranking (2003)
Dekel, Ofer, Manning, Christopher, Singer, Yoram
Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions...
Online Passive-Aggressive Algorithms (2003)
Crammer, Koby, Dekel, Ofer, Keshet, Joseph, Shalev-Shwartz, Shai, Singer, Yoram
We present a unified view for {\em online} classification, regression, and uniclass problems. This view leads to a single algorithmic framework for the three problems. We prove worst case loss bounds...
Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network (2003)
Kristina Toutanova, Dan Klein, Christopher D. Manning, Yoram Singer
We present a new part-of-speech tagger that demonstrates the following ideas: (i) explicit use of both preceding and following tag contexts via a dependency network representation, (ii) broad use of...
Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network (2003)
Kristina Toutanova, Dan Klein, Christopher D. Manning, Yoram Singer
We present a new part-of-speech tagger that demonstrates the following ideas: (i) explicit use of both preceding and following tag contexts via a dependency network representation, (ii) broad use of...
Think globally, fit locally: unsupervised learning of low dimensional manifolds (2003)
Lawrence K. Saul, Sam T. Roweis, Yoram Singer
The problem of dimensionality reduction arises in many fields of information processing, including machine learning, data compression, scientific visualization, pattern recognition, and neural...
Ultraconservative online algorithms for multiclass problems (2003)
Abstract. In this paper we study online classication algorithms for multiclass problems in the mistake bound model. The hypotheses we use maintain one prototype vector per class. Given an input...
A family of additive online algorithms for category ranking (2003)
Koby Crammer, Yoram Singer, Jaz K, Thomas Hofmann, Tomaso Poggio, John Shawe-taylor
We describe a new family of topic-ranking algorithms for multi-labeled documents. The motivation for the algorithms stem from recent advances in online learning algorithms. The algorithms are simple...
Smooth epsilon-Insensitive Regression by Loss Symmetrization (2003)
Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer
We describe a framework for solving regression problems by reduction to classification. Our reduction is based on symmetrization of margin-based loss functions commonly used in boosting algorithms,...
Greedy Algorithms for Classification - Consistency, Convergence Rates, and Adaptivity (2003)
Shie Mannor, Ron Meir, Tong Zhang, Yoram Singer
Many regression and classification algorithms proposed over the years can be described as greedy procedures for the stagewise minimization of an appropriate cost function. Some examples include...
An Efficient Boosting Algorithm for Combining Preferences (2003)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer, G. Dietterich
We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several...
Learning Algorithms for Enclosing Points in Bregmanian Spheres (2003)
We discuss the problem of nding a generalized sphere that encloses points originating from a single source. The points contained in such a sphere are within a maximal divergence from a center point....
Ultraconservative Online Algorithms for Multiclass Problems (2003)
Koby Crammer, Yoram Singer, K. Warmuth
In this paper we study a paradigm to generalize online classification algorithms for binary classification problems to multiclass problems. The particular hypotheses we investigate maintain one...
Margin-based generalization error bounds for threshold decision lists (2003)
In this paper we consider the generalization accuracy of classification methods based on the iterative use of linear classifiers. The resulting classifiers, which we call threshold decision lists act...
A Markov Model for the Acquisition of Morphological Structure (2003)
Leonid Kontorovich, Dana Ron, Yoram Singer
We describe a new formalism for word morphology. Our model views word generation as a random walk on a trellis of units where each unit is a set of (short) strings. The model naturally incorporates...
Smooth ε-Insensitive Regression by Loss Symmetrization (2003)
Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer, P. Bennett, Nicolo Cesa-bianchi
We describe new loss functions for regression problems along with an accompanying algorithmic framework which utilizes these functions. These loss functions are derived by symmetrization of...
Kernel design using boosting (2003)
Koby Crammer, Joseph Keshet, Yoram Singer
The focus of the paper is the problem of learning kernel operators from empirical data. We cast the kernel design problem as the construction of an accurate kernel from simple (and less accurate)...
Spikernels: Embedding spiking neurons in inner product spaces (2003)
Lavi Shpigelman, Yoram Singer, Rony Paz, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this paper is the construction of...
Ultraconservative online algorithms for multiclass problems (2003)
Koby Crammer, Yoram Singer, K. Warmuth
In this paper we study a paradigm to generalize online classification algorithms for binary classification problems to multiclass problems. The particular hypotheses we investigate maintain one...
Think globally, fit locally: unsupervised learning of low dimensional manifolds (2003)
Lawrence K. Saul, Yoram Singer
The problem of dimensionality reduction arises in many fields of information processing, including machine learning, data compression, scientific visualization, pattern recognition, and neural...
Spikernels: Embedding spiking neurons in inner product spaces (2003)
Lavi Shpigelman, Yoram Singer, Rony Paz, Eilon Vaadia
Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this paper is the construction of...
A family of additive online algorithms for category ranking (2003)
Koby Crammer, Yoram Singer, Jaz K, Thomas Hofmann, Tomaso Poggio, John Shawe-taylor
We describe a new family of topic-ranking algorithms for multi-labeled documents. The motivation for the algorithms stem from recent advances in online learning algorithms. The algorithms are simple...
Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network (2003)
Kristina Toutanova, Dan Klein, Christopher D. Manning, Yoram Singer
We present a new part-of-speech tagger that demonstrates the following ideas: (i) explicit use of both preceding and following tag contexts via a dependency network representation, (ii) broad use of...
Learning Algorithms for Enclosing Points in (2003)
Bregmanian Spheres Koby, Koby Crammer, Yoram Singer
We discuss the problem of finding a generalized sphere that encloses points originating from a single source. The points contained in such a sphere are within a maximal divergence from a center point.
Online Passive-Aggressive Algorithms (2003)
Koby Crammer, Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer
We present a unified view for online classification, regression, and uniclass problems. This view leads to a single algorithmic framework for the three problems. We prove worst case loss bounds for...
Log-Linear Models for Label Ranking (2003)
Ofer Dekel, Christopher D. Manning, Yoram Singer
Label ranking is the task of inferring a total order over a predefined set of labels for each given instance. We present a general framework for batch learning of label ranking functions from...
Online Classification on a Budget (2003)
Koby Crammer, Jaz Kandola, Royal Holloway, Yoram Singer
Online algorithms for classification often require vast amounts of memory and computation time when employed in conjunction with kernel functions. In this paper we describe and analyze a simple...
Kernel design using boosting (2003)
Koby Crammer, Joseph Keshet, Yoram Singer
The focus of the paper is the problem of learning kernel operators from empirical data. We cast the kernel design problem as the construction of an accurate kernel from simple (and less accurate)...
Margin-based generalization error bounds for threshold decision lists (2003)
In this paper we consider the generalization accuracy of classification methods based on the iterative use of linear classifiers. The resulting classifiers, which we call threshold decision lists act...
A new family of online algorithms for category ranking (2002)
We describe a new family of topic-ranking algorithms for multi-labeled documents. The motivation for the algorithms stems from recent advances in online learning algorithms. The algorithms we present...
Round Robin Classification (2002)
Round Robin Classification, Johannes Fürnkranz, Yoram Singer
In this paper, we discuss round robin classification (aka pairwise classification), a technique for handling multi-class problems with binary classifiers by learning one classifier for each pair of...
Discriminative Binaural Sound Localization (2002)
Time difference of arrival (TDOA) is commonly used to estimate the azimuth of a source in a microphone array. The most common methods to estimate TDOA are based on finding extrema in generalized...
Multiclass learning by probabilistic embeddings (2002)
We describe a new algorithmic framework for learning multiclass categorization problems. In this framework a multiclass predictor is composed of a pair of embeddings that map both instances and...
Discriminative binaural sound localization (2002)
Time difference of arrival (TDOA) is commonly used to estimate the azimuth of a source in a microphone array. The most common methods to estimate TDOA are based on finding extrema in generalized...
An Efficient PAC Algorithm for Reconstructing a Mixture of Lines (2002)
Sanjoy Dasgupta, Elan Pavlov, Yoram Singer
In this paper we study the learnability of a mixture of lines model which is of great importance in machine vision, computer graphics, and computer aided design applications. The mixture of lines is...
Robust Temporal and Spectral Modeling for Query by Melody (2002)
Shai Shalev-Shwartz, Shlomo Dubnov, Nir Friedman, Yoram Singer
Query by melody is the problem of retrieving musical performances from melodies. Retrieval of real performances is complicated due to the large number of variations in performing a melody and the...
Multiclass Learning by Probabilistic Embeddings (2002)
We describe a new algorithmic framework for learning multiclass categorization problems. In this framework a multiclass predictor is composed of a pair of embeddings that map both instances and...
Kernel Design using Boosting (2002)
Koby Crammer Joseph, Joseph Keshet, Yoram Singer
The focus of the paper is the problem of learning kernel operators from empirical data. We cast the kernel design problem as the construction of an accurate kernel from simple (and less accurate)...
Eleazar Eskin, William Noble Grundy, Yoram Singer
discrete events in biological sequences
We discuss the problem of ranking instances. In our framework each instance is associated with a rank or a rating, which is an integer from 1 to k. Our goal is to nd a rank-prediction rule that...
On the algorithmic implementation of multiclass kernel-based vector machines (2001)
Koby Crammer, Yoram Singer, Nello Cristianini, John Shawe-taylor, Bob Williamson
In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion...
On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines (2001)
Koby Crammer, Yoram Singer, Nello Cristianini, John Shawe-taylor, Bob Williamson
In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems.
Eleazar Eskin, William Noble, Yoram Singer
We present a method for classifying proteins into families based on short subsequences of amino acids using a new probabilistic model called sparse Markov transducers (SMT). We classify a protein by...
Improved output coding for classification using continuous relaxation (2001)
Output coding is a general method for solving multiclass problems by reducing them to multiple binary classification problems. Previous research on output coding has employed, almost solely,...
Eskin, Eleazar, Grundy, William N., Singer, Yoram
Accurately estimating probabilities from observations is important for probabilistic-based approaches to problems in computational biology. In this paper we present a biologically-motivated method...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Protein family classi� cation using sparse markov transducers (2000)
Eleazar Eskin, William Stafford Noble, Yoram Singer
We present a method for classifying proteins into families based on short subsequences of amino acids using a new probabilistic model called sparse Markov transducers (SMT). We classify a protein by...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Michael Collins, Robert E. Schapire, Yoram Singer
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this...
State-based classification of finger gestures from electromyographic signals (2000)
Peter Ju, Leslie Pack Kaelbling, Yoram Singer
Electromyographic signals may provide an important new class of user interface for consumer electronics. In order to make such interfaces effective, it will be crucial to map EMG signals to user...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Logistic regression, adaboost and bregman distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
Abstract. We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two...
Leveraged vector machines (2000)
We describe an iterative algorithm for building vector machines used in classification tasks. The algorithm builds on ideas from support vector machines, boosting, and generalized additive models....
Protein family classication using sparse markov transducers (2000)
William Noble Grundy, Yoram Singer
In this paper we present a method for classifying proteins into families using sparse Markov transducers (SMTs). Sparse Markov transducers, similar to probabilistic sux trees, estimate a probability...
BoosTexter: a boosting-based system for text categorization (2000)
Robert E. Schapire, Yoram Singer
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
State-based classification of finger gestures from electromyographic signals (2000)
Peter Ju, Leslie Pack Kaelbling, Yoram Singer
Electromyographic signals may provide an important new class of user interface for consumer electronics. In order to make such interfaces effective, it will be crucial to map EMG signals to user...
On the learnability and design of output codes for multiclass problems (2000)
Output coding is a general framework for solving multiclass categorization problems. Previous research on output codes has focused on building multiclass machines given predefined output codes. In...
Boosting for Document Routing (2000)
Raj Iyer, David Lewis, Robert E. Schapire, Yoram Singer, Amit Singhal
RankBoost is a recently proposed algorithm for learning ranking functions. It is simple to implement and has strong justifications from computational learning theory. We describe the algorithm and...
Protein Family Classification using Sparse Markov Transducers (2000)
Eleazar Eskin, William Noble Grundy, Yoram Singer
this paper we present a method for classifying
Logistic Regression, AdaBoost and Bregman Distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
. We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in...
On the Learnability and Design of Output Codes for Multiclass Problems (2000)
Output coding is a general framework for solving multiclass categorization problems. Previous research on output codes has focused on building multiclass machines given predefined output codes. In...
Logistic Regression, AdaBoost and Bregman Distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Logistic Regression, AdaBoost and Bregman Distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this...
Unsupervised Models for Named Entity Classification (1999)
This paper discusses the use of unlabeled examples for the problem of named entity classification. A large number of rules is needed for coverage of the domain, suggesting that a fairly large number...
Unsupervised Models for Named Entity Classification (1999)
mcollins,singer¡ This paper discusses the use of unlabeled examples for the problem of named entity classification. A large number of rules is needed for coverage of the domain, suggesting that a...
Efficient bayesian parameter estimation in large discrete domains (1999)
In this paper we examine the problem of estimating the parameters of a multinomial distribution over a large number of discrete outcomes, most of which do not appear in the training data. We analyze...
Learning to order things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the form of preference...
Boosting Applied to Tagging and PP Attachment (1999)
Steven Abney, Robert E. Schapire, Yoram Singer
Boosting is a machine learning algorithm that is not well known in computational linguistics. We apply it to part-of-speech tagging and prepositional phrase attachment. Performance is very...
Unsupervised Models for Named Entity Classification (1999)
This paper discusses the use of unlabeled examples for the problem of named entity classification. A large number of rules is needed for coverage of the domain, suggesting that a fairly large number...
A Simple, Fast, and Effective Rule Learner (1999)
William W. Cohen, Yoram Singer
We describe SLIPPER, a new rule learner that generates rulesets by repeatedly boosting a simple, greedy, rule-builder. Like the rulesets built by other rule learners, the ensemble of rules created by...
Improved Boosting Algorithms Using Confidence-rated Predictions (1999)
Robert E. Schapire, Yoram Singer
. We describe several improvements to Freund and Schapire's AdaBoost boosting algorithm, particularly in a setting in which hypotheses may assign confidences to each of their predictions. We...
Learning to Order Things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference...
Improved Boosting Algorithms Using Confidence-rated Predictions (1999)
Robert E. Schapire, Yoram Singer
. We describe several improvements to Freund and Schapire's AdaBoost boosting algorithm, particularly in a setting in which hypotheses may assign confidences to each of their predictions. We...
Efficient Bayesian Parameter Estimation in Large Discrete Domains (1999)
We examine the problem of estimating the parameters of a multinomial distribution over a large number of discrete outcomes, most of which do not appear in the training data. We analyze this problem...
Boosting Applied to Tagging and PP Attachment (1999)
Steven Abney, Robert E. Schapire, Yoram Singer
Boosting is a machine learning algorithm that is not well known in computational linguistics. We apply it to part-of-speech tagging and prepositional phrase attachment. Performance is very...
Learning to order things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
wcohen,schapire,singer¡ There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the...
Boosting applied to tagging and PP attachment (1999)
Steven Abney, Robert E. Schapire, Yoram Singer
Boosting is a machine learning algorithm that is not well known in computational linguistics. We apply it to part-of-speech tagging and prepositional phrase attachment. Performance is very...
Learning to order things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the form of preference...
Boosting and Rocchio Applied to Text Filtering (1998)
Robert E. Schapire, Yoram Singer, Amit Singhal
We discuss two learning algorithms for text filtering: modified Rocchio and a boosting algorithm called AdaBoost. We show how both algorithms can be adapted to maximize any general utility matrix...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
Boosting and Rocchio Applied to Text Filtering (1998)
Robert Schapire, Yoram Singer, Amit Singhal
We discuss two learning algorithms for text filtering: modified Rocchio and a boosting algorithm called AdaBoost. We show how both algorithms can be adapted to maximize any general utility matrix...
Boosting and Rocchio Applied to Text Filtering (1998)
Robert Schapire, Yoram Singer, Amit Singhal
We discuss two learning algorithms for text filtering: modified Rocchio and a boosting algorithm called AdaBoost. We show how both algorithms can be adapted to maximize any general utility matrix...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
. The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
Context-Sensitive Learning Methods for Text Categorization (1998)
William W. Cohen, Yoram Singer
Two recently implemented machine learning algorithms, RIPPER and sleepingexperts for phrases, are evaluated on a number of large text categorization problems. These algorithms both construct...
Recently, there has been work on on-line portfolio selection algorithms which are competitive with the best constant rebalanced portfolio determined in hindsight [2, 6, 3]. By their nature, these...
Learning to Order Things (1998)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
. The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
BoosTexter: A System for Multiclass Multi-label Text Categorization (1998)
Robert E. Schapire, Yoram Singer
This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. We first show how to extend the standard notion of classification by allowing...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
The Hierarchical Hidden Markov Model: Analysis and Applications (1998)
Shai Fine, Yoram Singer, Naftali Tishby
We introduce, analyze and demonstrate a recursive hierarchical generalization of the widely used hidden Markov models, which we name Hierarchical Hidden Markov Models (HHMM). Our model is motivated...
Shared Context Probabilistic Transducers (1998)
Yoshua Bengio, Samy Bengio, Yoram Singer
Recently, a model for supervised learning of probabilistic transducers represented by suffix trees was introduced. However, this algorithm tends to build very large trees, requiring very large...
On-Line Portfolio Selection Using Multiplicative Updates (1998)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Boosting and Rocchio Applied to Text Filtering (1998)
Robert Schapire, Yoram Singer, Amit Singhal
We discuss two learning algorithms for text filtering: modified Rocchio and a boosting algorithm called AdaBoost. We show how both algorithms can be adapted to maximize any general utility matrix...
A New Parameter Estimation Method for Gaussian Mixtures (1998)
Yoram Singer, Manfred K. Warmuth
We describe a new iterative method for parameter estimation of Gaussian mixtures. The new method is based on a framework developed by Kivinen and Warmuth for supervised online learning. In contrast...
Yoav Freund Center, Yoav Freund, G. Dietterich, C○ Yoav Freund, Raj Iyer, Raj Iyer, ...
We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several...
Batch and on-line parameter estimation of Gaussian mixtures based on the joint entropy (1998)
Yoram Singer, Manfred K. Warmuth
We describe a new iterative method for parameter estimation of Gaussian mixtures. The new method is based on a framework developed by Kivinen and Warmuth for supervised on-line learning. In contrast...
On-line portfolio selection using multiplicative updates (1998)
David P. Helmbold, Yoram Singer, Robert E. Schapire, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Using and Combining Predictors That Specialize (1997)
Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called "experts." These simple algorithms belong to...
An Efficient Extension to Mixture Techniques for Prediction and Decision Trees (1997)
Fernando C. Pereira, Yoram Singer
. We present an efficient method for maintaining mixtures of prunings of a prediction or decision tree that extends the previous methods for "node-based" prunings (Buntine, 1990; Willems,...
Update rules for parameter estimation in Bayesian networks (1997)
Eric Bauer, Daphne Koller, Yoram Singer
This paper re-examines the problem of parameter estimation in Bayesian networks with missing values and hidden variables from the perspective of recent work in on-line learning [12]. We provide a...
Using and Combining Predictors That Specialize (1997)
Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called "experts." These simple algorithms belong to...
Learning to Order Things (1997)
William Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference...
Update rules for parameter estimation in Bayesian networks (1997)
Eric Bauer, Daphne Koller, Yoram Singer
This paper re-examines the problem of parameter estimation in Bayesian networks with missing values and hidden variables from the perspective of recent work in on-line learning [12]. We provide a...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1997)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
Using and combining predictors that specialize (1997)
Yoav Freund, Robert E. Schapire, Yoram Singer
Abstract. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called “experts. ” These simple algorithms belong...
A comparison of new and old algorithms for a mixture estimation Problem (1997)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth, M. Long
Abstract. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for...
Pereira, Fernando C. N., Singer, Yoram, Tishby, Naftali
We describe, analyze, and evaluate experimentally a new probabilistic model for word-sequence prediction in natural language based on prediction suffix trees (PSTs). By using efficient data...
Context-sensitive learning methods for text categorization (1996)
William W. Cohen, Yoram Singer
Two recently implemented machine-learning algorithms, RIPPER and sleeping-experts for phrases, are evaluated on a number of large text categorization problems. These algorithms both construct...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
Dana Ron, Yoram Singer, NAFTALI TISHBY
. We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
Learning to Query the Web (1996)
William W. Cohen, Yoram Singer
The World Wide Web (WWW) is filled with "resource directories"---i.e., documents that collect together links to all known documents on a specific topic. Keeping resource directories...
On-Line Portfolio Selection Using Multiplicative Updates (1996)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Adaptive Mixtures of Probabilistic Transducers (1996)
We describe and analyze a mixture model for supervised learning of probabilistic transducers. We devise an on-line learning algorithm that efficiently infers the structure and estimates the...
Training Algorithms for Hidden Markov Models Using Entropy Based Distance Functions (1996)
Yoram Singer, Manfred K. Warmuth
We present new algorithms for parameter estimation of HMMs. By adapting a framework used for supervised learning, we construct iterative algorithms that maximize the likelihood of the observations...
Training Algorithms for Hidden Markov Models Using Entropy Based Distance Functions (1996)
Yoram Singer, Manfred K. Warmuth
We present new algorithms for parameter estimation of HMMs. By adapting a framework used for supervised learning, we construct iterative algorithms that maximize the likelihood of the observations...
William W. Cohen and Yoram Singer ATT Research 600 Mountain Avenue Murray Hill, NJ 07974 (1996)
Fwcohen Singerg, William W. Cohen, Yoram Singer
Two recently implemented machine learning algorithms, RIPPER and sleeping experts for phrases, are evaluated on a number of large text categorization problems. These algorithms both construct...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (1996)
. We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
Context-Sensitive Learning Methods for Text Categorization (1996)
William W. Cohen, Yoram Singer
Two recently implemented machine learning algorithms, RIPPER and sleeping experts for phrases, are evaluated on a number of large text categorization problems. These algorithms both construct...
On-Line Portfolio Selection Using Multiplicative Updates (1996)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Adaptive Mixture of Probabilistic Transducers (1996)
We introduce and analyze a mixture model for supervised learning of probabilistic transducers. We devise an online learning algorithm that efficiently infers the structure and estimates the...
On-Line Portfolio Selection Using Multiplicative Updates (1996)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
On-line portfolio selection using multiplicative updates (1996)
David P. Helmbold, Yoram Singer, Robert E. Schapire, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for a subclass of Acyclic Probabilistic Finite Automata (APFA). This subclass is characterized by a certain distinguishability property of the...
Fernando C. Pereira, Yoram Singer, Naftali Tishby
. We describe, analyze, and evaluate experimentally a new probabilistic model for word-sequence prediction in natural language based on prediction suffix trees (PSTs). By using efficient data...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for a subclass of Acyclic Probabilistic Finite Automata (APFA). This subclass is characterized by a certain distinguishability property of the...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
this paper. Our experimental evidence suggests that setting j ? 1 results in a more effective update. These results agree with the infinitesimal analysis in the limit of n !1 based on a stochastic...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
Fernando C. Pereira, Yoram Singer, Naftali Tishby
We describe, analyze, and experimentally evaluate a new probabilistic model for wordsequence prediction in natural languages, based on prediction suffix trees (PSTs). By using efficient data...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for a subclass of Acyclic Probabilistic Finite Automata (APFA). This subclass is characterized by a certain distinguishability property of the...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for a subclass of Acyclic Probabilistic Finite Automata (APFA). This subclass is characterized by a certain distinguishability property of the...
On the Learnability and Usage of Acyclic Probabilistic Finite Automata (1995)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for a subclass of Acyclic Probabilistic Finite Automata (APFA). This subclass is characterized by a certain distinguishability property of the...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
Part-of-Speech Tagging Using a Variable Memory Markov Model (1994)
We present a new approach to disambiguating syntactically ambiguous words in context, based on Variable Memory Markov (VMM) models. In contrast to fixed-length Markov models, which predict based on...
Dana Ron, Yoram Singer, Naftali Tishby
We propose a learning algorithm for a variable memory length Markov process. Human communication, whether given as text, handwriting, or speech, has multi characteristic time scales. On short scales...
Learning Probabilistic Automata with Variable Memory Length (1994)
Dana Ron, Yoram Singer, Naftali Tishby
We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name...
BoosTexter: A Boosting-based System for Text Categorization
Robert E. Schapire, Yoram Singer
. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting algorithms. We...
Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network
Kristina Toutanova Dan, Dan Klein, Christopher D. Manning, Yoram Singer
We present a new part-of-speech tagger that demonstrates the following ideas: (i) explicit use of both preceding and following tag contexts via a dependency network representation, (ii) broad use of...