Vega, Vinsensius B, Ruan, Yijun, Liu, Jianjun, Lee, Wah, Wei, Chia, Se-Thoe, Su, ...
Abstract Background The SARS coronavirus is the etiologic agent for the epidemic of the Severe Acute Respiratory Syndrome. The recent emergence of this new pathogen, the careful tracing of its...
Boosting and Microarray Data (2003)
Philip M. Long, Vinsensius Berlian Vega
We have found one reason why AdaBoost tends not to perform well on gene expression data, and identi ed simple modi cations that improve its ability to nd accurate class prediction rules. These modi...
A Theoretical Analysis of Query Selection for Collaborative (2002)
Sanjoy Dasgupta, Wee Sun Lee, Philip M. Long
We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple algorithm for...
Minimum Majority Classification and Boosting (2002)
Motivated by a theoretical analysis of the generalization of boosting, we examine learning algorithms that work by trying to fit data using a simple majority vote over a small number of a collection...
The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning (2002)
Yi Li, Philip M. Long, Aravind Srinivasan
Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a...
A Theoretical Analysis of Query Selection for Collaborative Filtering (2001)
We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple and fast...
Characterizations of Learnability for Classes of {0, . . . , n}-valued Functions (2001)
Shai Ben-david, David Haussler, Philip M. Long
We investigate the PAC learnability of classes of f0; : : : ; ng-valued functions (n ! 1). For n = 1 it is known that the finiteness of the Vapnik-Chervonenkis dimension is necessary and sufficient...
On the Difficulty of Approximately Maximizing Agreements (2001)
Shai Ben-david, Nadav Eiron, Philip M. Long
We address the computational complexity of learning in the agnostic framework. For a variety of common concept classes we prove that, unless P=NP, there is no polynomial time approximation scheme for...
Shai Ben-david, Philip M. Long, Yishay Mansour
. We extend the boosting paradigm to the realistic setting of agnostic learning, that is, to a setting where the training sample is generated by an arbitrary (unknown) probability distribution over...
Shai Ben-david, Philip M. Long, Yishay Mansour
. We extend the boosting paradigm to the realistic setting of
A Theoretical Analysis of Query Selection for Collaborative Filtering (2001)
. We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple and fast...
The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning (2000)
Yi Li, Philip M. Long, Aravind Srinivasan
Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a...
The Relaxed Online Maximum Margin Algorithm (2000)
We describe a new incremental algorithm for training linear threshold functions: the Relaxed Online Maximum Margin Algorithm, or ROMMA. ROMMA can be viewed as an approximation to the algorithm that...
Dictionary Selection using Partial Matching (2000)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
This work concerns the search for text compressors that compress better than existing dictionary coders, but run faster than statistical coders. We describe a new method for text compression using...
On the Difficulty of Approximately Maximizing Agreements (2000)
Shai Ben-david, Nadav Eiron, Philip M. Long
We address the computational complexity of learning in the agnostic framework. For a variety of common concept classes we prove that, unless P=NP, there is no polynomial time approximation scheme for...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (2000)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Learning to Make Rent-to-Buy Decisions with Systems Applications (2000)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Worst-case Quadratic Loss Bounds for Prediction Using Linear Functions and Gradient Descent (2000)
Philip M. Long, Manfred K. Warmuth
In this paper we study the performance of gradient descent when applied to the problem of on-line linear prediction in arbitrary inner product spaces. We show worst-case bounds on the sum of the...
The Relaxed Online Maximum Margin Algorithm (2000)
We describe a new incremental algorithm for training linear threshold functions: the Relaxed Online Maximum Margin Algorithm, or ROMMA. ROMMA can be viewed as an approximation to the algorithm that...
Text Compression Via Alphabet Re-Representation (2000)
Philip M. Long, Apostol I. Natsev, Jeffrey S. Vitter
This paper introduces the notion of alphabet re-representation in the context of text compression. We consider re-representing the alphabet so that a representation of a character reflects its...
The Relaxed Online Maximum Margin Algorithm (2000)
We describe a new incremental algorithm for training linear threshold functions: the Relaxed Online Maximum Margin Algorithm, or ROMMA. ROMMA can be viewed as an approximation to the algorithm that...
The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning (2000)
Yi Li, Philip M. Long, Aravind Srinivasan
Haussler, Littlestone and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved a bound on the probability that their algorithm made a mistake in...
Improved Bounds on the Sample Complexity of Learning (1999)
Yi Li, Philip M. Long, Aravind Srinivasan
We present two improved bounds on the sample complexity of learning. First, we present a new general upper bound on the number of examples required to estimate all of the expectations of a set of...
Associative Reinforcement Learning using Linear Probabilistic Concepts (1999)
We consider the problem of maximizing the total number of successes while learning about a probability function determining the likelihood of a success. In particular, we consider the case in which...
Approximating Hyper-Rectangles: Learning and Pseudo-random Sets (1998)
Peter Auer, Philip M. Long, Aravind Srinivasan
The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles...
On the Complexity of Function Learning (1998)
Peter Auer, Philip M. Long, Wolfgang Maass, Gerhard J. Woeginger
The majority of results in computational learning theory are concerned with concept learning, i.e. with the special case of function learning for classes of functions with range f0; 1g. Much less is...
Simulating Access to Hidden Information while Learning (1998)
We introduce a new technique which enables a learner without access to hidden information to learn nearly as well as a learner with access to hidden information. We apply our technique to solve an...
Approximating Hyper-Rectangles: Learning and Pseudo-random Sets (1998)
Peter Auer, Philip M. Long, Aravind Srinivasan
The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles...
Efficient Cost Measures for Motion Estimation at Low Bit Rates (1998)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and videoconferencing applications, where low bit rates...
On the Complexity of Learning from Drifting Distributions (1997)
Rakesh D. Barve, Philip M. Long
We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in...
On the Complexity of Learning from Drifting Distributions (1997)
Rakesh D. Barve, Philip M Long
Abstract not available.
Efficient Cost Measures for Motion Estimation at Low Bit Rates (1997)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We present and compare methods for choosing motion vectors for block-based motioncompensated video coding. The primary focus is on videophone and videoconferencing applications, where low bit rates...
Efficient Cost Measures for Motion Estimation at Low Bit Rates (1997)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We present and compare methods for choosing motion vectors for block-based motion-compensated video coding. The primary focus is on videophone and videoconferencing applications, where low bit rates...
Learning to Make Rent-to-Buy Decisions with Systems Applications (1997)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1997)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Text Compression via Alphabet Re-Representation (Extended Abstract) (1996)
Philip M. Long, Apostol I. Natsev, Jeffrey Scott Vitter
We consider re-representing the alphabet so that a representation of a character reflects its properties as a predictor of future text. This enables us to use an estimator from a restricted class to...
The Composition of Messages in Speech-Graphics Interactive Systems (1996)
Alan W. Biermann, Philip M. Long
We consider the problem of multimodal message generation. The main ideas of this paper are to unify the treatment of speech, text and graphics using a single grammar, and to adapt an evaluation...
Learning to Make Rent-to-Buy Decisions with Systems Applications (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Learning to Make Rent-to-Buy Decisions with Systems Applications (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Learning to Make Rent-to-Buy Decisions with Systems Applications (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Learning to Make Rent-to-Buy Decisions with Systems Applications (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Dzung T. Hoang, Philip M. Long, Jeffrey S. Vitter
We make a case that taking the number of bits to code each motion vector into account when estimating motion for video compression results in significantly better performance at low bit rates, using...
Efficient Cost Measures for Motion Compensation at Low Bit Rates (Extended Abstract) (1996)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We make a case that, even with severe efficiency constraints, taking the number of bits to code each motion vector into account when estimating motion for video compression results in significantly...
Explicit Bit Minimization for Motion-Compensated Video Coding (Extended Abstract) (1996)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We compare methods for choosing motion vectors for motion-compensated video compression. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are necessary,...
Multiple-Dictionary Compression Using Partial Matching (1996)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
Motivated by the desire to find text compressors that compress better than existing dictionary methods, but run faster than PPM implementations, we describe methods for text compression using...
Rate-Distortion Optimizations for Motion Estimation in Low-Bitrate Video Coding (1996)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We present and compare methods for choosing motion vectors for motion-compensated video coding. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are...
Absolute Loss Bounds for Prediction using Linear Functions (1996)
We prove new absolute loss bounds for learning linear functions in the standard on-line prediction model. These bounds are on the difference between the sum of absolute prediction errors made by the...
On the Complexity of Learning from Drifting Distributions (1996)
Rakesh D. Barve, Philip M. Long
We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1996)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Tracking Drifting Concepts By Minimizing Disagreements (1995)
David P. Helmbold, Philip M. Long
In this paper we consider the problem of tracking a subset of a domain (called the target) which changes gradually over time. A single (unknown) probability distribution over the domain is used to...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1995)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Fat-Shattering and the Learnability of Real-Valued Functions (1995)
Philip M. Long, Robert C. Williamson, Peter L. Bartlett
We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide...
Rate-Distortion Optimizations for Motion Estimation in Low-Bitrate Video Coding (1995)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We present and compare methods for choosing motion vectors for motion-compensated video coding. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are...
Learning to Make Rent-to-Buy Decisions with Systems Applications (1995)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
More Theorems about Scale-sensitive Dimensions and Learning (1995)
Peter L. Bartlett, Philip M. Long
We present a new general-purpose algorithm for learning classes of [0, 1]-valued functions in a generalization of the prediction model, and prove a general upper boundon the expected absolute error...
More Theorems about Scale-sensitive Dimensions and Learning (1995)
Peter L. Bartlett, Philip M. Long
We present a new general-purpose algorithm for learning classes of [0; 1]-valued functions in a generalization of the prediction model, and prove a general upper boundon the expected absolute error...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1995)
P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
Adaptive Disk Spindown via Optimal Rent-to-Buy in Probabilistic Environments (1995)
Jeffrey S. Vitter, P. Krishnan, Philip M. Long, Jeffrey Scott Vitter
In the single rent-to-buy decision problem, without a priori knowledge of the amount of time a resource will be used we need to decide when to buy the resource, given that we can rent the resource...
More Theorems about Scale-sensitive Dimensions and Learning (1995)
Peter L. Bartlett, Philip M. Long
We present a general-purpose algorithm for learning classes of [0, 1]-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of...
More Theorems about Scale-sensitive Dimensions and Learning (1995)
Peter L. Bartlett, Philip M. Long
We present a general-purpose algorithm for learning classes of [0; 1]-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of...
Explicit Bit Minimization for Motion-Compensated Video Coding (1994)
Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter
We compare methods for choosing motion vectors for motion-compensated video compression. Our primary focus is on videophone and videoconferencing applications, where very low bit rates are necessary,...
Fat-Shattering and the Learnability of Real-Valued Functions (1994)
Peter L. Bartlett, Philip M. Long, Robert C. Williamson
We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide...
Fat-Shattering and the Learnability of Real-Valued Functions (1994)
Peter L. Bartlett, Philip M. Long, Robert C. Williamson
We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide...
Philip M. Long, Manfred K. Warmuth
this paper we study the performance of gradient descent when applied to the problem of on-line linear prediction in arbitrary inner product spaces. We show worst-case bounds on the sum of the squared...
Characterizations of Learnability for Classes of {0, . . . , n}-valued Functions (1993)
Shai Ben-david, David Haussler, Philip M. Long
this paper we present a general scheme for extending the VC-dimension to the case n ? 1. Our scheme defines a wide variety of notions of dimension in which several variants of the VC-dimension,...
Tracking Drifting Concepts By Minimizing Disagreements (1993)
David P. Helmbold, Philip M. Long
this paper we consider the problem of tracking a subset of a domain (called
Sorting and Searching With a Faulty Comparison Oracle (1992)
this paper, we follow usual convention of denoting the base 2 logarithm by log and the natural logarithm by ln.
On-Line Learning of Linear Functions (1992)
Nicholas Littlestone, Philip M. Long, Manfred K. Warmuth
this paper, we present near-optimal strategies for combining opinions in situations like this. In more abstract terms, we study the on-line learning of linear functions. We assume that learning...
Composite Geometric Concepts and Polynomial Predictability (1992)
Philip M. Long, Manfred K. Warmuth
this paper, we assume not only that the target concept is chosen from a particular class, but that the concepts of this class are encoded using a particular representation language, and we allow the...
Towards a more comprehensive theory of learning in computers /--by Philip M. Long. (1992)
Typescript.
Towards a more comprehensive theory of learning in computers /--by Philip M. Long. (1992)
Thesis (Ph. D.)--University of California, Santa Cruz, 1992.
Towards a more comprehensive theory of learning in computers / (1992)
Abstract: "We attempt to determine the theoretical boundaries of the ability of computers to learn. We consider several rigorous models of learning, aimed at addressing types of learning problems...
Fat-Shattering and the Learnability of Real-Valued Functions (1970)
Philip M. Long, Robert C. Williamson, Peter L. Bartlett
We consider the problem of learning real-valued functions from random examples when the function values are corrupted with noise. With mild conditions on independent observation noise, we provide...
Sotiriou, Christos, Neo, Soek-Ying, McShane, Lisa M., Korn, Edward L., Long, Philip M., Jazaeri, Amir, ...
Comprehensive gene expression patterns generated from cDNA microarrays were correlated with detailed clinico-pathological characteristics and clinical outcome in an unselected group of 99...
Mutational dynamics of the SARS coronavirus in cell culture and human populations isolated in 2003
Vega, Vinsensius B, Ruan, Yijun, Liu, Jianjun, Lee, Wah Heng, Wei, Chia Lin, Se-Thoe, Su Yun, ...
Sotiriou, Christos, Neo, Soek-Ying, McShane, Lisa M., Korn, Edward L., Long, Philip M., Jazaeri, Amir, ...
Comprehensive gene expression patterns generated from cDNA microarrays were correlated with detailed clinico-pathological characteristics and clinical outcome in an unselected group of 99...