ALT 2017

I’ve just returned from the 28th International Conference on Algorithmic Learning Theory (ALT 2017), which was held in Kyoto, Japan.  The last time ALT was held in Japan was in 2007, exactly 10 years ago.  Back then, I was a second year grad student at my first ALT, and at one of my first conferences altogether.  Now, ten years later, I got to watch my Ph.D. student Mano Vikash present his first conference paper, and I was serving as program co-chair, together with Steve Hanneke.  What a difference 10 years makes!

a photo I took at Yasaka Shrine in Kyoto

Except for handling some last-minute duties concerning session chair assignments and minor issues with the online proceedings, there was little left for me and Steve to do at the actual conference. Once the conference started, the local organizers and general chair took over, and they kept things running smoothly.  But the experience of attending was still different for me.  By the time the conference started, I had read many of the papers and was at least a little familiar with the rest of them.  I also felt a strange sense of responsibility to go to every single talk, and I enjoyed doing this more than I expected.

Being PC chair was a lot of work, but it was quite gratifying.  I appreciate that Steve and I were able to work quite well together.  I’m thankful that so many amazing people agreed to serve on the PC and that our invited speakers readily agreed to come all the way to Japan.  I am thankful that we got many good submissions — more submitted papers than in any year since my first ALT a decade ago.  And I am especially grateful for the quality of the reviews; the PC had to handle more papers than usual, yet the reviews were careful and detailed, catching multiple bugs and providing valuable feedback to authors.  The resulting proceedings are online.

We also had two great invited speakers for ALT.  Sasha Raklin, among other things, gave some interesting results that I was not previously aware of at the intersection of Rademacher complexity and online learning.  Adam Kalai gave great and accessible talk on "fairness" and had a nice way to express various notions of fairness as loss functions. I must admit I’ve been skeptical of this area for a while, but chatting with Adam afterwards has made me less so.  

When blogging about conferences in the past, I discussed some of my favorite papers.  I don’t feel it would be especially appropriate for me to do so in this case, so I’ll just mention the paper for which the E. M. Gold student paper award was given to Tyler Dorhn, an undergraduate student at Yale.  In the paper, Dana Angluin and Tyler Dohrn showed that when equivalence queries are answered randomly, the expected query complexity of exact learning is drastically improved over when equivalence queries are answered adversarially.  In doing so, they introduced a nice notion called the "elimination graph" of a concept space.  It's a concept that I expect to have more applications.   And this is a problem I and others have informally thought about, so I’m glad to see progress in this area.

Finally, I’ll note that ALT has been going through some changes lately.  This year, in addition to more minor tweaks, we switched publication venues from Springer to PMLR (the new name for JMLR’s conference proceedings) in favor of open access, and we got rid of page limits.  More big changes are coming next year: ALT 2018 also will co-locate with AISTATS instead of DS next year, and PC co-chairs Mehryar Mohri and Karthik Sridharan have put out an ambitious call for papers with the goal of becoming the "best conference in algorithmic and theoretical machine learning."  (The co-location with AISTATS also means that the conference is moving from Fall to Spring, and papers are due in a week!)

Computational learning theory has two main conferences: COLT and ALT, with COLT being the larger of the two.  ALT has always had strong authors and PC members, but hadn’t grown in prestige and visibility like COLT.  My former postdoc host John Langford wrote, "ALT = 0.5 COLT." Yet, I’ve always appreciated ALT’s breadth and its resilience to various trends that change the theme of some other conferences almost yearly.  ALT grew this year, and I’m optimistic about its future. And my hope is that ALT can meet its new ambitions while retaining its friendly and open culture.

Turing's Revolution

In my post Alan Turing Year, I discussed how it's important for people to be aware of Turing's intellectual contributions to math and computer science, as well as his war efforts and tragic death.  It's time to live up to my own call and do my part.  In this post I'll talk about Turing's impact, from his best known contributions to his lesser known, but important ones.

I should note that the content of this post is largely stolen from answers to a question I asked on the StackExchange (SE) cstheory site, where I sought to gather a compendium of Turing's less known results.  The answers made a collection of impressive contributions, some of which I wasn't familiar with.  Some of his contributions turned out to be surprisingly modern.  They also introduced us to viewing the world through an algorithmic lens.

Without further ado, here they are:

1. Defining Turing Machines and Showing the Existence of UTMs (1936): A Turing machine is a universal computing device that forms the basis of how we think about computing.  A Universal Turing machine is a fixed machine that can simulate any other Turing machine -- most relevant to our current computers. (SE link)

a Lego Turing Machine, photo from wikipedia 

2. The Church-Turing Thesis (1939): The idea that the Turing Machine (and Lambda calculus) captures all of computation, and is therefore worth studying.  This hypothesis cannot be proven, but everyone believes it nonetheless. (wiki link) 

3. Solving the Entscheidungsproblem (1936): Turing solved Hilbert's "decision problem" by showing that deciding whether a program will halt is not possible in general.  (wiki link) 

4. The Turing Test and Introducing AI (1950): Turing gave an objective test that decides whether a computer exhibits intelligence.  The idea is to say that a computer is intelligent if it can fool humans into thinking it is also human.  Accepting this idea is a way to avoid many philosophical arguments about the nature of intelligence. (wiki link) 

5. Introducing Oracles and Relativization into Computability Theory (1939): Oracles are incredibly useful for all sorts of analysis -- for example the famous Baker-Gill-Solovay result that says P vs NP cannot be separated any technique that relativizes (holds for relative to any oracle), eg diagnolization.  It was part of the paper "Computing machinery and intelligence" that launched AI. (SE link) 

6. The Bombe (1950): Also called the Turing-Welchman Bombe, for breaking the German enigma machine in WW2 and introducing tools to cryptanalysis. (SE link)  

 the Bombe, from http://www.uh.edu/engines/epi2666.htm

7. Randomized Algorithms (1950): Turing observed the potential advantage an algorithm can gain from having access to randomness. (SE link)

8. The First Artificial Neural Network (1948): This idea is an important one in AI and machine learning.  Turing's design predated Rosenblatt's preceptron. (SE link) 

9. The Chemical Basis of Morphogenisis (1952): In his most cited paper, he began to tackle the question of how a symmetric embryo develops into an assymetric organism using symmetry perserving chemical reactions.  This started to introduce algorithmic thinking into biology. (SE link) 

10. Good-Turing Estimator (1953): For estimating an unseen fraction on a population when given past data. (SE link) 

11. One of the First Chess Algorithms (1952): Before we had computers, we had paper chess algorithms. (SE link) 

  Deep Blue, photo form wikipedia

12. Checking a Large Routine (1949): The idea of using invariants to prove properties of programs and "well-foundedness" to prove termination. (SE link) 

13. LU-Decomposition (1947): A method for factorizing a matrix as the product of a lower triangular matrix and an upper triangular matrix.  Now commonly studied in Linear Algebra. (SE link)

14. Turing's Method for Computational Analysis of a Function (1943): Invented for studying the of the Riemann zeta-function but is more widely applied. (SE link)

I'm sure there are more.  Any one of these is an impressive achievement for a scientist -- the first couple are revolutionary.  That Turing did all of these and more shows his remarkable contributions to our field.

Update (12/31/12): Alan Richmond points out another important work of Turing's, which I added as # 14.  Also, my wording for the Turing test proved a bit controversial, so I've changed it to better reflect reality.

Happenings on CSTheory Q&A

In addition to machine learning, one of my main research interests is theoretical computer science.  Following the success of MathOverflow and other Q&A sites, cstheory.stackexchange.com ("cstheory" for short) was born about a year ago, and I've been an active participant since its inception.  In the last year, we've worked hard to make cstheory a valuable resource and to promote it.  I'd say the efforts paid off -- the site is doing quite well, with over 5000 members.

Moreover, cstheory recently added a blog (Aaron Sterling and Joe Fitzsimons are editors), whose posts are on topics related to theoretical computer science and to the site itself.  In one of the first posts, Suresh Venkatasubramanian, a site moderator and one of the people most responsible for its success, wrote a nice summary of cstheory's first year.

I've also volunteered to occasionally blog about the learning theory side of things.  My first entry, on learning regular languages, was just posted.  It touches on many interesting issues learning theorists regularly encounter. Enjoy!