A family of additive online algorithms for category ranking
Published 1 March 2003
Koby Crammer, Yoram Singer
Citations180
SJR quartileQ1
SJR score2.02
SNIP3.07
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new family of topic- ranking algorithms for multi-labeled documents that achieve state-of-the-art results and outperforms topic-ranking adaptations of Rocchio's algorithm and of the Perceptron algorithm are described.
Abstract
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 to implement and are also time and memory efficient. We provide a unified analysis of the family of algorithms in the mistake bound model. We then discuss experiments with the proposed family of topic-ranking algorithms on the Reuters-21578 corpus and the new corpus released by Reuters in 2000. On both corpora, the algorithms we present achieve state-of-the-art results and outperforms topic-ranking adaptations of Rocchio's algorithm and of the Perceptron algorithm.
Keywords
Computer Science
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Cambridge University Press eBooksAn Introduction to Support Vector Machines and Other Kernel-based Learning Methods
13,883 Citations2000Nello Cristianini, John Shawe‐Taylor
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.
11,746 Citations1958Frank F. Rosenblatt
This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.
ePrints Soton (University of Southampton)An Introduction to Support Vector Machines
4,120 Citations2000Nello Cristianini, John Shawe‐Taylor
Improved boosting algorithms using confidence-rated predictions
2,568 Citations1998Robert E. Schapire, Yoram Singer
The MIT Press eBooksA Kernel Method for Multi-Labelled Classification
1,336 Citations2002André Elisseeff, Jason Weston
This article presents a Support Vector Machine like learning system to handle multi-label problems, based on a large margin ranking system that shares a lot of common properties with SVMs.
Large margin classification using the perceptron algorithm
1,099 Citations1998Yoav Freund, Robert E. Schapire
ACM SIGIR ForumPivoted Document Length Normalization
863 Citations2017Amit Singhal, Chris Buckley +1 more
Pivoted normalization is presented, a technique that can be used to modify any normalization function thereby reducing the gap between the relevance and the retrieval probabilities, and two new normalization functions--pivoted unique normalization and piuotert byte size normalization are presented.
An Efficient Boosting Algorithm for Combining Preferences
814 Citations1998Yoav Freund, Raj D. Iyer +2 more
This work describes and analyze an efficient algorithm called RankBoost for combining preferences based on the boosting approach to machine learning, and gives theoretical results describing the algorithm’s behavior both on the training data, and on new test data not seen during training.
ScienceDevelopments in Automatic Text Retrieval
623 Citations1991Gerard Salton
The text analysis problem is examined, and modern approaches leading to the identification and retrieval of selected text items in response to search requests are discussed.
The MIT Press eBooksPranking with Ranking
550 Citations2002Koby Crammer, Yoram Singer
A simple and efficient online algorithm is described, its performance in the mistake bound model is analyzed, its correctness is proved, and it outperforms online algorithms for regression and classification applied to ranking.
New ranking algorithms for parsing and tagging
505 Citations2001Michael Collins, Nigel Duffy
New learning algorithms for natural language processing based on the perceptron algorithm are introduced, showing how the algorithms can be efficiently applied to exponential sized representations of parse trees, such as the "all subtrees" (DOP) representation described by (Bod 1998).
Feature selection, perception learning, and a usability case study for text categorization
446 Citations1997Hwee Tou Ng, Wei Boon Goh +1 more
An automated learning approach to text categorization based on perception learning and a new feature selection metric, called correlation coefficient, is described and empirical results indicate that this approach outperforms the best published results on this % uters collection.
Applied Physics Letters10.1162/jmlr.2003.3.4-5.951
323 Citations2000
This paper describes a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores.
Boosting and Rocchio applied to text filtering
299 Citations1998Robert E. Schapire, Yoram Singer +1 more
This paper discusses two learning algorithms for text filtering: modified Rocchio and a boosting algorithm called AdaBoost, and shows how both algorithms can be adapted to maximize any general utility matrix that associates cost for each pair of machine prediction and correct label.
Journal of Computer and System SciencesOn Weak Learning
74 Citations1995David P. Helmbold, Manfred K. Warmuth
This paper presents relationships between weak learning, weak prediction, and consistency oracles and uses an algorithm to show that a concept class is polynomially learnable if and only if there is a polynomial probabilistic consistency oracle for the class.