Machine Learning (Theory)

10/29/2018

Please vote

Tags: General jl@ 2:45 pm

This is not at all related to Machine Learning.

I lived in Squirrel Hill as a graduate student at Carnegie Mellon so the massacre there is feeling particularly immediate. While the person who did it is obviously culpable, the pattern of events makes it clear that others bear responsibility as well. This pattern includes an attempted bomber of Democrats and Trump critics by a Trump fanboy. It also includes a more general cross section of Republicans and their leaders pushing anti-semitism and more general xenophobia about migrants.

I don’t believe that stochastic terrorism is the goal here. Instead, I have a rather pessimal view of politics in which politicians do pretty much anything to get re-elected, at least in aggregate. Donald Trump’s presidential campaign showed how to do this with a platform of populism, nostalgia, xenophobia, and anti-abortion voters.

The populist angle is looking fairly broken now between anti-populist tax cuts and widely publicized efforts to allow preexisting condition discrimination by insurance companies via Obamacare repeal. About the only populist angle which works is the economy, which is doing fine. On the other hand, there is no obvious change in employment trends since 2011 and no change in wage trends since 2014 so the case for responsibility is clearly tenuous.

Alliances in a two-party system tend to be fragile since winning with a smaller constituency enables better serving that constituency. Losing the populist angle leaves a double-down on the remaining agenda as the most plausible choice. Xenophobia is much older than democracy and psychologically potent so it has obvious value. It’s historically used by leaders who pick some characteristic to divide people and position themselves to thrive on the conflict or distraction that creates. Almost anything will do—if you take away religion, birthplace, skin color, and ethnicity, it would just change to hair color, nose size, or left-handedness. In a democracy, the goal with this approach is simply convincing people to vote according to their activated xenophobia.

For people embracing xenophobia to retain power, stochastic terrorism is just an unfortunate side effect. In this sense, inciting xenophobia about a caravan of refugee Guatemalans at the other end of Mexico is rather clever since most of them won’t even make it to the US border months after the election plausibly leaving only electoral consequences. Yet xenophobia is known to be hard to control. Given this, it’s difficult to imagine stochastic terrorism as anything other than deliberately accepted by the Republican party leadership as an observed consequence of this behavior. The Squirrel Hill massacre and the attempted bombing campaigns are precisely the sort of thing that can happen when you dial up the rhetoric just before an election.

This is part of a pattern of moral collapse across the Republican party. By any reasonable measure Donald Trump is a serial liar with Republican politicians now mimicking this behavior. A remarkable set of people around the Trump campaign are confessed or convicted criminals with members of the Republican party variously tolerating, condoning, and perhaps mimicking.

In this context, the upcoming midterm election seems particularly important. If politicians in aggregate behave as if they will do anything to get reelected, then voters must vote for the behavior they want at the ballot box rather than relying on or appealing to it at a later date. In most situations, this is about picking and choosing the better candidate. I’ve been registered as an independent for this reason—I want to decide for myself.

This is not most situations. Do voters rebuke the Republican party or not? If the answer is not (a 37% chance according to bettors at present) then the slide into corruption likely accelerates as confirmed control of the government erodes the remaining institutional checks on corruption. We are several steps away from a state of deep corruption and it takes time for the consequences of corruption to really seep into society. But every step on the path makes the situation worse and we are on the wrong path now as evidenced by bombing attempts, a xenophobic massacre, and the wider context creating them.

I want to particularly encourage those who are eligible to vote in the United States midterms November 6th.

7/6/2018

A Real World Reinforcement Learning Research Program

Tags: Funding,Reinforcement,Research jl@ 9:10 am

We are hiring for reinforcement learning related research at all levels and all MSR labs. If you are interested, apply, talk to me at COLT or ICML, or email me.

More generally though, I wanted to lay out a philosophy of research which differs from (and plausibly improves on) the current prevailing mode.

Deepmind and OpenAI have popularized an empirical approach where researchers modify algorithms and test them against simulated environments, including in self-play. They’ve achieved significant success in these simulated environments, greatly expanding the reportoire of ‘games solved by reinforcement learning’ which consisted of the singleton backgammon when I was a graduate student. Given the ambitious goals of these organizations, the more general plan seems to be “first solve games, then solve real problems”. There are some weaknesses to this approach, which I want to lay out next.

  • Broken API One issue with this is that multi-step reinforcement learning is a broken API in the sense that it creates an interface for problem definitions that is unsolvable via currently popular algorithm families. In particular, you can create problems which are either ‘antishaped’ so local rewards mislead w.r.t. long term rewards or keylock problems, as are common in Markov Decision Process lower bounds. I coded up simple versions of these problems a couple years ago and stuck them on github now to be extra crisp. If you try to apply policy gradient or Q-learning style algorithms on these problems they commonly run into exponential (in the number of states) sample complexity. As a general principle, APIs which create exponential sample complexity are bad—they imply that individual applications require taking advantage of special structure in order to succeed.
  • Transference Another significant issue is the degree of transference between solutions in simulation and the real world. “Transference” here potentially happens at several levels.
    • Do the algorithms carry over? One of the persistent issues with simulation-based approaches is that you don’t care about sample complexity that much—optimal performance at acceptable computational complexities is the typical goal. In real world applications, this is somewhat absurd—you really care about immediately doing something reasonable and optimizing from there.
    • Do the simulators carry over? For every simulator, there is a fidelity question which comes into play when you want to transfer a policy learned in the simulator into action in the real world. Real-time ray tracing and simulator quality more generally are advancing, but I’m not ready yet to trust a self-driving care trained in a simulated reality. An accurate simulation of the physics is unclear—friction for example is known-difficult, and more generally the representative variety of exogenous events in an open world seems quite difficult to implement.
  • Solution generality When you test and discover that an algorithm works in a simulated world, you know that it works in the simulated world. If you try it in 30 simulated worlds and it works in all of them, it can still easily be the case that an algorithm fails on the 31st simulated world. How can you achieve confidence beyond the number of simulated worlds that you try and succeed on? There is some sense by which you can imagine generalization over an underlying process generating problems, but this seems like a shaky justification in practice, since the nature of the problems encountered seems to be a nonstationary development of an unknown future.
  • Value creation Solutions of a ‘first A, then B’ flavor naturally take time to get to the end state where most of the real value is set to be realized. In the years before reaching applications in the real world, does the funding run out? We certainly hope not for the field of research but a danger does exist. Some discussion here including the comments is relevant.

What’s an alternative?

Each of the issues above is addressable.

  • Build fundamental theories of what are statistically and computationally tractable sub-problems of Reinforcement Learning. These tractable sub-problems form the ‘APIs’ of systems for solving these problems. Examples of this include simpler (Contextual Bandits), intermediate (learning to search, and move advanced (Contextual Decision Process).
  • Work on real-world problems. The obvious antidote to simulation is reality, driving both the need to create systems that work in reality as well as a research agenda around reality-centered issues like performance at low sample complexity. There are some significant difficulties with this—reinforcement style algorithms require interactive access to learn which often drives research towards companies with an infrastructure. Nevertheless, offline evaluation on real-world data does exist and the choice of emphasis in research directions is universal.
  • The combination of fundamental theories and a platform which distills learnings so they are not forgotten and always improved upon provides a stronger basis for expectation of generalization into the next problem.
  • The shortest path to creating valuable applications in the real world is to simply work on creating valuable applications in the real world. Doing this in a manner guided by other elements of the research program is just good sense.

The above must be applied in moderation—some emphasis on theory, some emphasis on real world applications, some emphasis on platforms, and some emphasis on empirics. This has been my research approach for a little over 10 years, ever since I started working on contextual bandits.

Let’s call the first research program ’empirical simulation’ and the second research program ‘real fundamentals’. The empirical simulation approach has a clear strong advantage in that it creates impressive demos, which creates funding, which creates more research. The threshold for contribution to the empirical simulation approach may also be lower simply because it requires mastery of fewer elements, implying people can more easily participate in it. At the same time, the real fundamentals approach has clear advantages in addressing the weaknesses of the empirical simulation approach. At a concrete level, this means we have managed to define and create fundamentals through research while creating real-world applications and value radically more efficiently than the empirical simulation approach has achieved.

The ‘real fundamentals’ concept is behind the open positions above. These positions have been designed to come with both the colleagues and mandate to address the most difficult research problems along with the organizational leverage to change the world. For people interested in fundamentals and making things happen in the real world these are prime positions—please consider joining us.

6/4/2018

When the bubble bursts…

Tags: AI,Machine Learning jl@ 2:39 pm

Consider the following facts:

  1. NIPS submission are up 50% this year to ~4800 papers.
  2. There is significant evidence that the process of reviewing papers in machine learning is creaking under several years of exponentiating growth.
  3. Public figures often overclaim the state of AI.
  4. Money rains from the sky on ambitious startups with a good story.
  5. Apparently, we now even have a fake conference website (https://nips.cc/ is the real one for NIPS).

We are clearly not in a steady-state situation. Is this a bubble or a revolution? The answer surely includes a bit of revolution—the fields of vision and speech recognition have been turned over by great empirical successes created by deep neural architectures and more generally machine learning has found plentiful real-world uses.

At the same time, I find it hard to believe that we aren’t living in a bubble. There was an AI bubble in the 1980s (before my time), a techbubble around 2000, and we seem to have a combined AI/tech bubble going on right now. This is great in some ways—many companies are handing out professional sports scale signing bonuses to researchers. It’s a little worrisome in other ways—can the field effectively handle the stress of the influx?

It’s always hard to say when and how a bubble bursts. It might happen today or in several years and it may be a coordinated failure or a series of uncoordinated failures.

As a field, we should consider the coordinated failure case a little bit. What fraction of the field is currently at companies or in units at companies which are very expensive without yet justifying that expense? It’s no longer a small fraction so there is a chance for something traumatic for both the people and field when/where there is a sudden cut-off. My experience is that cuts typically happen quite quickly when they come.

As an individual researcher, consider this an invitation to awareness and a small amount of caution. I’d like everyone to be fully aware that we are in a bit of a bubble right now and consider it in their decisions. Caution should not be overdone—I’d gladly repeat the experience of going to Yahoo! Research even knowing how it ended. There are two natural elements here:

  1. Where do you work as a researcher? The best place to be when a bubble bursts is on the sidelines.
    1. Is it in the middle of a costly venture? Companies are not good places for this in the long term whether a startup or a business unit. Being a researcher at a place desperately trying to figure out how to make research valuable doesn’t sound pleasant.
    2. Is it in the middle of a clearly valuable venture? That could be a good place. If you are interested we are hiring.
    3. Is it in academia? Academia has a real claim to stability over time, but at the same time opportunity may be lost. I’ve greatly enjoyed and benefited from the opportunity to work with highly capable colleagues on the most difficult problems. Assembling the capability to do that in an academic setting seems difficult since the typical maximum scale of research in academia is a professor+students.
  2. What do you work on as a researcher? Some approaches are more “bubbly” than others—they might look good, but do they really provide value?
    1. Are you working on intelligence imitation or intelligence creation? Intelligence creation ends up being more valuable in the long term.
    2. Are you solving synthetic or real-world problems? If you are solving real-world problems, you are almost certainly creating value. Synthetic problems can lead to real-world solutions, but the path is often fraught with unforeseen difficulties.
    3. Are you working on a solution to one problem or many problems? A wide applicability for foundational solutions clearly helps when a bubble bursts.

Researchers have a great ability to survive a bubble bursting—a built up public record of their accomplishments. If you are in a good environment doing valuable things and that environment happens to implode one day the strength of your publications is an immense aid in landing on your feet.

4/16/2018

Reinforcement Learning Platforms

If you are interested in building an industrial Reinforcement Learning platform, we are hiring a data scientist and multiple developers as a followup to last year’s hiring. Please apply if interested as this is a real chance to be a part of building the future :-)

3/5/2018

ICML Board and Reviewer profiles

The outcome of the election for the IMLS (which runs ICML) adds Emma Brunskill and Hugo Larochelle to the board. The current members of the board (and the reason for board membership) are:

President Elect is a 2-year position with little responsibility, but I decided to look into two things. One is the website which seems relatively difficult to navigate. Ideas for how to improve are welcome.

The other is creating a longitudinal reviewer profile. I keenly remember the day after reviews were due when I was program chair (in 2012) which left a panic-inducing number of unfinished reviews. To help with this, I’m planning to create a profile of reviewers which program chairs can refer to in making decisions about who to ask to review. There are a number of ways to do this wrong which I’m avoiding with the following procedure:

  1. After reviews are assigned, capture the reviewer/paper assignment. Call this set A.
  2. After reviews are due, capture the completed & incomplete reviews for papers. Call these sets B & C respectively.
  3. Strip the paper ids from B (completed reviews) turning it into a multiset D of reviewers completed reviews.
  4. Compute C-A (as a set difference) then turn it into a multiset E of reviewers incomplete reviews.
  5. Store D & E for long term reference.

This approach:

  • Is objectively defined. Approaches based on subjective measurements seem both fraught with judgment issues and inconsistent. Consider for example the impressive variation we all see in review quality.
  • Does not record a review as late for reviewers who are assigned a paper late in the process via step (1) and (4). We want to encourage reviewers to take on the unusual but important late tasks that arrive.
  • Does not record a review as late for reviewers who discover they are inappropriate after assignment and ask for reassignment. We want to encourage reviewers to look at their papers early and, if necessary, ask for a paper to be reassigned early.
  • Preserves anonymity of paper/reviewer assignments for authors who later become program chairs. The conversion into a multiset removes the paper id entirely.

Overall, my hope is that several years of this will provide a good and useful tool enabling program chairs and good (or at least not-bad) reviewers to recognize each other.

Older Posts »

Powered by WordPress