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...
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...
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, 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...
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,...
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...
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)
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...
Online and Batch Learning of Pseudo-Metrics (2004)
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)
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...
Smooth ε-Insensitive Regression by Loss Symmetrization (2004)
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...
Learning Algorithms for Enclosing Points in (2004)
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.
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....
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...
Online and Batch Learning of Pseudo-Metrics (2004)
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.
Greedy Algorithms for Classification - Consistency, Convergence Rates, and Adaptivity (2004)
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...
Online Passive-Aggressive Algorithms (2004)
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 (2004)
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 (2004)
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...
Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network (2004)
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...
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...
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...
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...
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...
A Markovian Lattice Model (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 lattice of units where each unit is a set of (short) strings. The model naturally incorporates...
Smooth epsilon-Insensitive Regression by Loss Symmetrization (2003)
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,...
Learning Algorithms for Enclosing Points in (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....
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...
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...
Discriminative Binaural Sound Localization (2003)
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...
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)...
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, Nikola Jevti C, 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 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...
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...
Multiclass Learning by Probabilistic Embeddings (2003)
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...
Multiclass Learning by Probabilistic Embeddings (2003)
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 (2003)
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...
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)...
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...
Fernando C. Pereira, Yoram Singer, Nafah Tishby
We describe, analyze, and experimentally evaluate a new probabilistic model for word- sequence prediction in natural languages, based on prediction suffix trees (PSTs). By using efficient data...
Unsupervised Models for Named Entity Classification (2002)
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...
Boosting Applied to Tagging and PP Attachment (2002)
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...
Context-Sensitive Learning Methods for Text Categorization (2002)
William W. Cohen, Yoram Singer
this article, we will investigate the performance of two recently implemented machine-learning algorithms on a number of large text categorization problems. The two algorithms considered are...
Spikernels: Embedding Spiking Neurons in Inner-Product Spaces (2002)
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...
An Ecient PAC Algorithm for Reconstructing (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...
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...
Robust Temporal and Spectral Modeling for (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...
Part-of-Speech Tagging Using a Variable Memory Markov Model (2002)
Hinrich Schfitze, Yoram Singer
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...
Round Robin Classification (2002)
Round Robin Classification, Johannes Furnkranz, 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...
Boosting Applied to Tagging and PP Attachment (2002)
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