Home

Daniel Hsu

  1. Two SVDs Suffice: Spectral decompositions for probabilistic topic modeling and latent Dirichlet allocation.

    Tue, 05/01/2012 - 15:01 — SomNambul
    Authors: Animashree Anandkumar, Sham M. Kakade, Daniel Hsu, Dean P. Foster, Yi-Kai Liu
    Subjects: Learning
    Abstract

    Topic models can be seen as a generalization of the clustering problem, in
    that they posit that observations are generated due to multiple latent factors
    (e.g. the words in each document are generated as a mixture of several active
    topics, as opposed to just one). This increased representational power comes at
    the cost of a more challenging unsupervised learning problem of estimating the
    topic probability vectors (the distributions over words for each topic), when
    only the words are observed and the corresponding topics are hidden.

  2. An Online Learning-based Framework for Tracking.

    Mon, 03/19/2012 - 15:01 — SomNambul
    Authors: Yoav Freund, Kamalika Chaudhuri, Daniel Hsu
    Subjects: Artificial Intelligence
    Abstract

    We study the tracking problem, namely, estimating the hidden state of an
    object over time, from unreliable and noisy measurements. The standard
    framework for the tracking problem is the generative framework, which is the
    basis of solutions such as the Bayesian algorithm and its approximation, the
    particle filters. However, these solutions can be very sensitive to model
    mismatches. In this paper, motivated by online learning, we introduce a new
    framework for tracking. We provide an efficient tracking algorithm for this
    framework.

  3. A Method of Moments for Mixture Models and Hidden Markov Models.

    Tue, 03/06/2012 - 15:01 — SomNambul
    Authors: Animashree Anandkumar, Sham M. Kakade, Daniel Hsu
    Subjects: Learning
    Abstract

    Mixture models are a fundamental tool in applied statistics and machine
    learning for treating data taken from multiple subpopulations. The current
    practice for estimating the parameters of such models relies on local search
    heuristics (e.g., the EM algorithm) which are prone to failure, and existing
    consistent methods are unfavorable due to their high computational and sample
    complexity which typically scale exponentially with the number of mixture
    components.

  4. A tail inequality for quadratic forms of subgaussian random vectors.

    Fri, 10/14/2011 - 15:01 — SomNambul
    Authors: Tong Zhang, Sham M. Kakade, Daniel Hsu
    Subjects: Probability
    Abstract

    We prove an exponential probability tail inequality for positive semidefinite
    quadratic forms in a subgaussian random vector. The bound is analogous to one
    that holds when the vector has independent Gaussian entries.

  5. Stochastic convex optimization with bandit feedback.

    Tue, 07/12/2011 - 15:01 — SomNambul
    Authors: Sham M. Kakade, Daniel Hsu, Alekh Agarwal, Alexander Rakhlin, Dean P. Foster
    Subjects: Optimization and Control
    Abstract

    This paper addresses the problem of minimizing a convex, Lipschitz function
    $f$ over a convex, compact set $\xset$ under a stochastic bandit feedback
    model. In this model, the algorithm is allowed to observed noisy realizations
    of the function value $f(x)$ at any query point $x \in \xset$. The quantity of
    interest is regret of the algorithm, which is the sum of the function values at
    algorithm's query points minus the optimal function value. We demonstrate a
    generalization of the ellipsoid algorithm that incurs $\otil(\poly(d)\sqrt{T})$
    regret.

  6. Spectral Methods for Learning Multivariate Latent Tree Structure.

    Fri, 07/08/2011 - 15:01 — SomNambul
    Authors: Tong Zhang, Animashree Anandkumar, Sham M. Kakade, Kamalika Chaudhuri, Daniel Hsu, Le Song
    Subjects: Learning
    Abstract

    This work considers the problem of learning the structure of a broad class of
    multivariate latent variable tree models, which include a variety of continuous
    and discrete models (including the widely used linear-Gaussian models, hidden
    Markov models, and Markov evolutionary trees). The setting is one where we only
    have samples from certain observed variables in the tree and our goal is to
    estimate the tree structure (i.e., the graph of how the underlying hidden
    variables are connected to the observed variables).

  7. Efficient Optimal Learning for Contextual Bandits.

    Tue, 06/14/2011 - 15:01 — SomNambul
    Authors: Tong Zhang, John Langford, Daniel Hsu, Lev Reyzin, Nikos Karampatziakis, Miroslav Dudik, Satyen Kale
    Subjects: Learning
    Abstract

    We address the problem of learning in an online setting where the learner
    repeatedly observes features, selects among a set of actions, and receives
    reward for the action taken. We provide the first efficient algorithm with an
    optimal regret. Our algorithm uses a cost sensitive classification learner as
    an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number
    of classification rules among which the oracle might choose. This is
    exponentially faster than all previous algorithms that achieve optimal regret
    in this setting.

  8. An Analysis of Random Design Linear Regression.

    Tue, 06/14/2011 - 15:01 — SomNambul
    Authors: Tong Zhang, Sham M. Kakade, Daniel Hsu
    Subjects: Statistics
    Abstract

    The random design setting for linear regression concerns estimators based on
    a random sample of covariate/response pairs. This work gives explicit bounds on
    the prediction error for the ordinary least squares estimator and the ridge
    regression estimator under mild assumptions on the covariate/response
    distributions. In particular, this work provides sharp results on the
    "out-of-sample" prediction error, as opposed to the "in-sample" (fixed design)
    error. Our analysis also explicitly reveals the effect of noise vs. modeling
    errors.

  9. Parallel Online Learning.

    Wed, 03/23/2011 - 16:01 — SomNambul
    Authors: John Langford, Daniel Hsu, Alex Smola, Nikos Karampatziakis
    Subjects: Learning
    Abstract

    In this work we study parallelization of online learning, a core primitive in
    machine learning. In a parallel environment all known approaches for parallel
    online learning lead to delayed updates, where the model is updated using
    out-of-date information.

  10. Robust Matrix Decomposition with Outliers.

    Tue, 11/09/2010 - 16:01 — SomNambul
    Authors: Tong Zhang, Sham M. Kakade, Daniel Hsu
    Subjects: Machine Learning
    Abstract

    Suppose a given observation matrix can be decomposed as the sum of a low-rank
    matrix and a sparse matrix (outliers), and the goal is to recover these
    individual components from the observed sum. Such additive decompositions have
    applications in a variety of numerical problems including system
    identification, latent variable graphical modeling, and principal components
    analysis. We study conditions under which recovering such a decomposition is
    possible via a combination of $\ell_1$ norm and trace norm minimization.

  11. A parameter-free hedging algorithm.

    Wed, 01/20/2010 - 16:02 — SomNambul
    Authors: Yoav Freund, Kamalika Chaudhuri, Daniel Hsu
    Subjects: Learning
    Abstract

    We study the problem of decision-theoretic online learning (DTOL). Motivated
    by practical applications, we focus on DTOL when the number of actions is very
    large. Previous algorithms for learning in this framework have a tunable
    learning rate parameter, and a barrier to using online-learning in practical
    applications is that it is not understood how to set this parameter optimally,
    particularly when the number of actions is large.

  12. Tracking using explanation-based modeling.

    Wed, 01/20/2010 - 16:02 — SomNambul
    Authors: Yoav Freund, Kamalika Chaudhuri, Daniel Hsu
    Subjects: Learning
    Abstract

    We study the tracking problem, namely, estimating the hidden state of an
    object over time, from unreliable and noisy measurements. The standard
    framework for the tracking problem is the generative framework, which is the
    basis of solutions such as the Bayesian algorithm and its approximation, the
    particle filters. However, the problem with these solutions is that they are
    very sensitive to model mismatches. In this paper, motivated by online
    learning, we introduce a new framework -- an {\em explanatory} framework -- for
    tracking.

Math-arch

Syndicate content