{"id":1729,"date":"2011-03-19T16:24:51","date_gmt":"2011-03-19T22:24:51","guid":{"rendered":"http:\/\/hunch.net\/?p=1729"},"modified":"2011-03-19T16:24:51","modified_gmt":"2011-03-19T22:24:51","slug":"the-ideal-large-scale-learning-class","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=1729","title":{"rendered":"The Ideal Large Scale Learning Class"},"content":{"rendered":"

At NIPS, Andrew Ng<\/a> asked me what should be in a large scale learning class. After some discussion with him and Nando<\/a> and mulling it over a bit, these are the topics that I think should be covered.<\/p>\n

There are many different kinds of scaling.<\/p>\n

    \n
  1. Scaling in examples<\/strong> This is the most basic kind of scaling.\n
      \n
    1. Online Gradient Descent<\/strong> This is an old algorithm—I’m not sure if anyone can be credited with it in particular. Perhaps the Perceptron<\/a> is a good precursor, but substantial improvements come from the notion of a loss function of which squared loss<\/a>, logistic loss<\/a>, Hinge Loss, and Quantile Loss<\/a> are all worth covering. It’s important to cover the semantics<\/a> of these loss functions as well. Vowpal Wabbit<\/a> is a reasonably fast codebase implementing these.<\/li>\n
    2. Second Order Gradient Descent methods<\/strong> For some problems, methods taking into account second derivative information can be more effective. I’ve seen preconditioned conjugate gradient work well, for which Jonathan Shewchuck<\/a>‘s writeup<\/a> is reasonable. Nando likes L-BFGS<\/a> which I don’t have much experience with.<\/li>\n
    3. Map-Reduce<\/strong> I have a love-hate relationship with the Map-Reduce framework. In my experience, it’s an excellent filesystem, but it’s quite frustrating to do machine learning with, since it encourages the parallelization of slow learning algorithms. I liked what Markus<\/a> said at the LCCC workshop<\/a>: nobody wants to give up on the idea of distributed fault tolerant storage and moving small amounts of code to large amounts of data rather than vice-versa. The best way to use this for Machine Learning isn’t yet clear to me. Hadoop<\/a> is probably the most commonly used open source implementation of Map-Reduce.<\/li>\n<\/ol>\n<\/li>\n
    4. Feature Scaling<\/strong>—what do you do when you have very many features?\n
        \n
      1. Hashing approaches<\/a> are surprisingly effective in my experience. It’s a good idea to also present Bloom Filters<\/a>, as they help with the intuition of where this works substantially.<\/li>\n
      2. Online l1<\/sub><\/em> regularization is via truncated gradient<\/a>. See Bob Carpenter’s discussion<\/a>. John Duchi’s composite mirror descent<\/a> generalization is also a useful general treatment.<\/li>\n
      3. Boosting<\/a> based approaches can also be effective, although training time can become problematic. This is partially mitigated by parallelization algorithms as discussed at the LCCC workshop<\/a> See Jerry Ye’s talk<\/a> and Krysta’s talk.<\/a>. A really good public implementation of this is so far missing, as far as I know.<\/li>\n<\/ol>\n<\/li>\n
      4. Test-time Evaluation<\/strong> Ultrafast and efficient test-time evaluation seems to be a goal independent of training.\n
          \n
        1. Indicies<\/strong> One way to speed things up is with inverted indicies. Aside from the basic datastructure, I’d cover WAND<\/a> and predictive indexing<\/a>.<\/li>\n
        2. GPU<\/strong> The use of GPU’s to make evaluation both more efficient and fast seems to make sense in many applications.<\/li>\n<\/ol>\n<\/li>\n
        3. Labels<\/strong>\n
            \n
          1. Sourcing<\/strong> Just acquiring sufficient label information can be problematic.\n
              \n
            1. Mechanical Turk<\/a> can be an efficient approach. The basic approach can be improved with some work<\/a>.<\/li>\n
            2. When you are paying directly for labels, active learning<\/a> approaches can substantially cut your costs. Burr Settles<\/a> active learning survey<\/a> is pretty comprehensive, although if I was to cover one algorithm, it would be this one<\/a> which enjoys a compelling combination of strong theoretical guarantees, computational tractability, empirical performance, and generality.<\/li>\n
            3. The other common approach is user-feedback information where bias and exploration effects becomes a critical concern. The tutorial Alina<\/a> and I did on learning and exploration<\/a> is critical here.<\/li>\n<\/ol>\n<\/li>\n
            4. Many Labels<\/strong> It’s common to need to make a complex prediction.\n
                \n
              1. Label Tree<\/strong> based approaches are a good starting point. I’d discuss the inconsistency of the naive approach and the Filter Tree, discussed here<\/a>. Online tree building and conditional probability trees<\/a> are also potentially extremely useful. Building smarter trees can help, such as with a confusion matrix<\/a> or in an iterative fashion<\/a>.<\/li>\n
              2. Label Tree approaches breakdown when the number of labels becomes so large that filtering eliminates too many examples. Here Structured Prediction<\/strong> techniques become particularly important. I’d cover Searn<\/a> as well as some of Drew Bagnell<\/a>‘s work such as this one<\/a>. Many other people are still interested in CRF<\/a>s or Max-Margin Markov Networks<\/a> which I find somewhat less compelling for computational reasons.<\/li>\n
              3. Cascade Learning<\/strong> is also a compelling approach. The canonical paper on this is the Viola-Jones Face Detector<\/a>. I’m sure there’s much other vision-related work on cascades that I’m unfamiliar. A more recent instance is the structured prediction cascade<\/a>.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n

                What else is essential and missing?<\/p>\n","protected":false},"excerpt":{"rendered":"

                At NIPS, Andrew Ng asked me what should be in a large scale learning class. After some discussion with him and Nando and mulling it over a bit, these are the topics that I think should be covered. There are many different kinds of scaling. Scaling in examples This is the most basic kind of … <\/p>\n

                Continue reading “The Ideal Large Scale Learning Class”<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[29,5],"tags":[],"class_list":["post-1729","post","type-post","status-publish","format-standard","hentry","category-machine-learning","category-teaching"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/1729","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1729"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/1729\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1729"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1729"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1729"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}