Posted on

Some recent papers

It was a fine time for learning in Pittsburgh. John and Sam mentioned some of my favorites. Here’s a few more worth checking out:

Online Multitask Learning
Ofer Dekel, Phil Long, Yoram Singer
This is on my reading list. Definitely an area I’m interested in.

Maximum Entropy Distribution Estimation with Generalized Regularization
Miroslav Dudík, Robert E. Schapire

Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path
András Antos, Csaba Szepesvári, Rémi Munos
Again, on the list to read. I saw Csaba and Remi talk about this and related work at an ICML Workshop on Kernel Reinforcement Learning. The big question in my head is how this compares/contrasts with existing work in reductions to reinforcement learning. Are there advantages/disadvantages?

Higher Order Learning On Graphs> by Sameer Agarwal, Kristin Branson, and Serge Belongie, looks to be interesteding. They seem to poo-poo “tensorization” of existing graph algorithms.

Cover Trees for Nearest Neighbor (Alina Beygelzimer, Sham Kakade, John Langford) finally seems to have gotten published. It’s an embarrassment to the community that it took this long– and a reminder of how diligent one has to be in ensuring good work gets published. This seems to happen on a regular basis. (See A New View of EM.)

Finally, I thought this one was very cool:
Constructing Informative Priors by Rajat Raina, Andrew Y. Ng, Daphne Koller.
Same interest as the first paper on the list.
Check them out!

Posted on

Branch Prediction Competition

Alan Fern points out the second branch prediction challenge (due September 29) which is a follow up to the first branch prediction competition. Branch prediction is one of the fundamental learning problems of the computer age: without it our computers might run an order of magnitude slower. This is a tough problem since there are sharp constraints on time and space complexity in an online environment. For machine learning, the “idealistic track” may fit well. Essentially, they remove these constraints to gain a weak upper bound on what might be done.

Posted on

more icml papers

Here are a few other papers I enjoyed from ICML06.

Topic Models:


  • Dynamic Topic Models
    David Blei, John Lafferty
    A nice model for how topics in LDA type models can evolve over time,
    using a linear dynamical system on the natural parameters and a very
    clever structured variational approximation (in which the mean field
    parameters are pseudo-observations of a virtual LDS). Like all Blei
    papers, he makes it look easy, but it is extremely impressive.

  • Pachinko Allocation
    Wei Li, Andrew McCallum
    A very elegant (but computationally challenging) model which induces
    correlation amongst topics using a multi-level DAG whose interior nodes
    are “super-topics” and “sub-topics” and whose leaves are the
    vocabulary words. Makes the slumbering monster of structure learning stir.

Sequence Analysis (I missed these talks since I was chairing another session)


  • Online Decoding of Markov Models with Latency Constraints
    Mukund Narasimhan, Paul Viola, Michael Shilman
    An “ah-ha!” paper showing how to trade off latency and decoding
    accuracy when doing MAP labelling (Viterbi decoding) in sequential
    Markovian models. You’ll wish you thought of this yourself.

  • Efficient inference on sequence segmentation model
    Sunita Sarawagi
    A smart way to re-represent potentials in segmentation models
    to reduce the complexity of inference from cubic in the input sequence
    to linear. Also check out her NIPS2004 paper with William Cohen
    on “segmentation CRFs”. Moral of the story: segmentation is NOT just
    sequence labelling.

Optimal Partitionings/Labellings


  • The uniqueness of a good optimum for K-means
    Marina Meila
    Marina shows a stability result for K-means clustering, namely
    that if you find a “good” clustering it is not too “different” than the
    (unknowable) optimal clustering and that all other good clusterings
    are “near” it. So, don’t worry about local minima in K-means as long
    as you get a low objective.

  • Quadratic Programming Relaxations for Metric Labeling and Markov Random Field MAP Estimation
    Pradeep Ravikumar, John Lafferty
    Paradeep and John introduce QP relaxations for the problem of finding
    the best joint labelling of a set of points (connected by a weighted
    graph and with a known metric cost between labels and extended
    the non-metric case). Surprisingly, they show that the QP relaxation
    is both computationally more attractive and more accurate than
    the “natural” LP relaxation or than loopy BP approximations.

Distinguished Paper Award Winners

Posted on

ICML papers

Here are some ICML papers which interested me.

  1. Arindam Banerjee had a paper which notes that PAC-Bayes bounds, a core theorem in online learning, and the optimality of Bayesian learning statements share a core inequality in their proof.
  2. Pieter Abbeel, Morgan Quigley and Andrew Y. Ng have a paper discussing RL techniques for learning given a bad (but not too bad) model of the world.
  3. Nina Balcan and Avrim Blum have a paper which discusses how to learn given a similarity function rather than a kernel. A similarity function requires less structure than a kernel, implying that a learning algorithm using a similarity function might be applied in situations where no effective kernel is evident.
  4. Nathan Ratliff, Drew Bagnell, and Marty Zinkevich have a paper describing an algorithm which attempts to fuse A* path planning with learning of transition costs based on human demonstration.

Papers (2), (3), and (4), all seem like an initial pass at solving interesting problems which push the domain in which learning is applicable.

I’d like to encourage discussion of what papers interested you and why. Maybe we’ll all learn a little bit, and it’s very likely that we all missed interesting papers in a multitrack conference.

Posted on

Presentation of Proofs is Hard.

When presenting part of the Reinforcement Learning theory tutorial at ICML 2006, I was forcibly reminded of this.

There are several difficulties.

  1. When creating the presentation, the correct level of detail is tricky. With too much detail, the proof takes too much time and people may be lost to boredom. With too little detail, the steps of the proof involve too-great a jump. This is very difficult to judge.
    1. What may be an easy step in the careful thought of a quiet room is not so easy when you are occupied by the process of presentation.
    2. What may be easy after having gone over this (and other) proofs is not so easy to follow in the first pass by a viewer.

    These problems seem only correctable by process of repeated test-and-revise.

  2. When presenting the proof, simply speaking with sufficient precision is substantially harder than in normal conversation (where precision is not so critical). Practice can help here.
  3. When presenting the proof, going at the right pace for understanding is difficult. When we use a blackboard/whiteboard, a natural reasonable pace is imposed by the process of writing. Unfortunately, writing doesn’t scale well to large audiences for vision reasons, losing this natural pacing mechanism.
  4. It is difficult to entertain with a proof—there is nothing particularly funny about it. This particularly matters for a large audience which tends to naturally develop an expectation of being entertained.

Given all these difficulties, it is very tempting to avoid presenting proofs. Avoiding the proof in any serious detail is fairly reasonable in a conference presentation—the time is too short and the people viewing are too heavily overloaded to follow the logic well. The “right” level of detail is often the theorem statement.

Nevertheless, avoidance is not always possible because the proof is one of the more powerful mechanisms we have for doing research.