hunch_net hunch_net-2007 hunch_net-2007-252 knowledge-graph by maker-knowledge-mining
Source: html
Introduction: It turns out that many different people use the term “Online Learning”, and often they don’t have the same definition in mind. Here’s a list of the possibilities I know of. Online Information Setting Online learning refers to a problem in which unlabeled data comes, a prediction is made, and then feedback is acquired. Online Adversarial Setting Online learning refers to algorithms in the Online Information Setting which satisfy guarantees of the form: “For all possible sequences of observations, the algorithim has regret at most log ( number of strategies) with respect to the best strategy in a set.” This is sometimes called online learning with experts. Online Optimization Constraint Online learning refers to optimizing a predictor via a learning algorithm tunes parameters on a per-example basis. This may or may not be applied in the Online Information Setting, and the strategy may or may not satisfy Adversarial setting theory. Online Computational Constra
sentIndex sentText sentNum sentScore
1 It turns out that many different people use the term “Online Learning”, and often they don’t have the same definition in mind. [sent-1, score-0.242]
2 Online Information Setting Online learning refers to a problem in which unlabeled data comes, a prediction is made, and then feedback is acquired. [sent-3, score-0.704]
3 Online Adversarial Setting Online learning refers to algorithms in the Online Information Setting which satisfy guarantees of the form: “For all possible sequences of observations, the algorithim has regret at most log ( number of strategies) with respect to the best strategy in a set. [sent-4, score-1.317]
4 ” This is sometimes called online learning with experts. [sent-5, score-0.644]
5 Online Optimization Constraint Online learning refers to optimizing a predictor via a learning algorithm tunes parameters on a per-example basis. [sent-6, score-0.891]
6 This may or may not be applied in the Online Information Setting, and the strategy may or may not satisfy Adversarial setting theory. [sent-7, score-1.104]
7 Online Computational Constraint Online learning refers to an algorithmic constraint that the amount of computation per example is constant as the number of examples increases. [sent-8, score-1.194]
8 Again, this doesn’t imply anything in particular about the Information setting in which it is applied. [sent-9, score-0.453]
9 Lifelong Learning Online learning refers to learning in a setting where different tasks come at you over time, and you need to rapidly adapt to past mastered tasks. [sent-10, score-1.63]
wordName wordTfidf (topN-words)
[('refers', 0.503), ('online', 0.498), ('setting', 0.313), ('constraint', 0.25), ('satisfy', 0.193), ('tasks', 0.167), ('strategy', 0.163), ('adversarial', 0.145), ('information', 0.142), ('mastered', 0.106), ('adapt', 0.101), ('sequences', 0.097), ('strategies', 0.097), ('may', 0.096), ('possibilities', 0.083), ('rapidly', 0.081), ('anything', 0.075), ('algorithmic', 0.075), ('called', 0.074), ('unlabeled', 0.074), ('optimizing', 0.073), ('learning', 0.072), ('guarantees', 0.071), ('constant', 0.069), ('parameters', 0.068), ('observations', 0.068), ('past', 0.065), ('imply', 0.065), ('different', 0.062), ('definition', 0.061), ('turns', 0.061), ('regret', 0.059), ('computation', 0.059), ('optimization', 0.058), ('term', 0.058), ('number', 0.057), ('predictor', 0.057), ('per', 0.056), ('log', 0.055), ('feedback', 0.055), ('amount', 0.053), ('list', 0.052), ('comes', 0.052), ('applied', 0.051), ('doesn', 0.048), ('respect', 0.047), ('computational', 0.046), ('via', 0.046), ('need', 0.045), ('come', 0.043)]
simIndex simValue blogId blogTitle
same-blog 1 0.99999988 252 hunch net-2007-07-01-Watchword: Online Learning
Introduction: It turns out that many different people use the term “Online Learning”, and often they don’t have the same definition in mind. Here’s a list of the possibilities I know of. Online Information Setting Online learning refers to a problem in which unlabeled data comes, a prediction is made, and then feedback is acquired. Online Adversarial Setting Online learning refers to algorithms in the Online Information Setting which satisfy guarantees of the form: “For all possible sequences of observations, the algorithim has regret at most log ( number of strategies) with respect to the best strategy in a set.” This is sometimes called online learning with experts. Online Optimization Constraint Online learning refers to optimizing a predictor via a learning algorithm tunes parameters on a per-example basis. This may or may not be applied in the Online Information Setting, and the strategy may or may not satisfy Adversarial setting theory. Online Computational Constra
2 0.30820951 267 hunch net-2007-10-17-Online as the new adjective
Introduction: Online learning is in vogue, which means we should expect to see in the near future: Online boosting. Online decision trees. Online SVMs. (actually, we’ve already seen) Online deep learning. Online parallel learning. etc… There are three fundamental drivers of this trend. Increasing size of datasets makes online algorithms attractive. Online learning can simply be more efficient than batch learning. Here is a picture from a class on online learning: The point of this picture is that even in 3 dimensions and even with linear constraints, finding the minima of a set in an online fashion can be typically faster than finding the minima in a batch fashion. To see this, note that there is a minimal number of gradient updates (i.e. 2) required in order to reach the minima in the typical case. Given this, it’s best to do these updates as quickly as possible, which implies doing the first update online (i.e. before seeing all the examples) is preferred. Note
3 0.2463226 8 hunch net-2005-02-01-NIPS: Online Bayes
Introduction: One nice use for this blog is to consider and discuss papers that that have appeared at recent conferences. I really enjoyed Andrew Ng and Sham Kakade’s paper Online Bounds for Bayesian Algorithms . From the paper: The philosophy taken in the Bayesian methodology is often at odds with that in the online learning community…. the online learning setting makes rather minimal assumptions on the conditions under which the data are being presented to the learner —usually, Nature could provide examples in an adversarial manner. We study the performance of Bayesian algorithms in a more adversarial setting… We provide competitive bounds when the cost function is the log loss, and we compare our performance to the best model in our model class (as in the experts setting). It’s a very nice analysis of some of my favorite algorithms that all hinges around a beautiful theorem: Let Q be any distribution over parameters theta. Then for all sequences S: L_{Bayes}(S) leq L_Q(S)
4 0.20627446 388 hunch net-2010-01-24-Specializations of the Master Problem
Introduction: One thing which is clear on a little reflection is that there exists a single master learning problem capable of encoding essentially all learning problems. This problem is of course a very general sort of reinforcement learning where the world interacts with an agent as: The world announces an observation x . The agent makes a choice a . The world announces a reward r . The goal here is to maximize the sum of the rewards over the time of the agent. No particular structure relating x to a or a to r is implied by this setting so we do not know effective general algorithms for the agent. It’s very easy to prove lower bounds showing that an agent cannot hope to succeed here—just consider the case where actions are unrelated to rewards. Nevertheless, there is a real sense in which essentially all forms of life are agents operating in this setting, somehow succeeding. The gap between these observations drives research—How can we find tractable specializations of
5 0.17758216 109 hunch net-2005-09-08-Online Learning as the Mathematics of Accountability
Introduction: Accountability is a social problem. When someone screws up, do you fire them? Or do you accept the error and let them continue? This is a very difficult problem and we all know of stories where the wrong decision was made. Online learning (as meant here), is a subfield of learning theory which analyzes the online learning model. In the online learning model, there are a set of hypotheses or “experts”. On any instantance x , each expert makes a prediction y . A master algorithm A uses these predictions to form it’s own prediction y A and then learns the correct prediction y * . This process repeats. The goal of online learning is to find a master algorithm A which uses the advice of the experts to make good predictions. In particular, we typically want to guarantee that the master algorithm performs almost as well as the best expert. If L(e) is the loss of expert e and L(A) is the loss of the master algorithm, it is often possible to prove: L(A) les
6 0.16775382 378 hunch net-2009-11-15-The Other Online Learning
7 0.14758764 309 hunch net-2008-07-10-Interesting papers, ICML 2008
8 0.14412577 186 hunch net-2006-06-24-Online convex optimization at COLT
9 0.13922235 251 hunch net-2007-06-24-Interesting Papers at ICML 2007
10 0.1294793 385 hunch net-2009-12-27-Interesting things at NIPS 2009
11 0.1209332 78 hunch net-2005-06-06-Exact Online Learning for Classification
12 0.1140934 258 hunch net-2007-08-12-Exponentiated Gradient
13 0.1111051 279 hunch net-2007-12-19-Cool and interesting things seen at NIPS
14 0.10609815 183 hunch net-2006-06-14-Explorations of Exploration
15 0.10598285 28 hunch net-2005-02-25-Problem: Online Learning
16 0.10123608 163 hunch net-2006-03-12-Online learning or online preservation of learning?
17 0.10059495 133 hunch net-2005-11-28-A question of quantification
18 0.099399872 269 hunch net-2007-10-24-Contextual Bandits
19 0.098593056 308 hunch net-2008-07-06-To Dual or Not
20 0.098224938 237 hunch net-2007-04-02-Contextual Scaling
topicId topicWeight
[(0, 0.19), (1, 0.126), (2, -0.01), (3, -0.05), (4, 0.126), (5, -0.022), (6, -0.092), (7, -0.086), (8, -0.051), (9, 0.218), (10, 0.189), (11, 0.019), (12, 0.123), (13, -0.062), (14, 0.045), (15, 0.024), (16, 0.03), (17, -0.142), (18, 0.125), (19, 0.03), (20, -0.066), (21, -0.124), (22, 0.041), (23, 0.031), (24, 0.144), (25, 0.078), (26, 0.081), (27, 0.019), (28, 0.025), (29, 0.078), (30, 0.049), (31, 0.077), (32, 0.001), (33, -0.019), (34, 0.008), (35, 0.028), (36, 0.076), (37, 0.005), (38, -0.089), (39, -0.118), (40, -0.002), (41, 0.115), (42, -0.009), (43, -0.014), (44, -0.085), (45, -0.055), (46, -0.059), (47, 0.078), (48, 0.005), (49, -0.078)]
simIndex simValue blogId blogTitle
same-blog 1 0.98083383 252 hunch net-2007-07-01-Watchword: Online Learning
Introduction: It turns out that many different people use the term “Online Learning”, and often they don’t have the same definition in mind. Here’s a list of the possibilities I know of. Online Information Setting Online learning refers to a problem in which unlabeled data comes, a prediction is made, and then feedback is acquired. Online Adversarial Setting Online learning refers to algorithms in the Online Information Setting which satisfy guarantees of the form: “For all possible sequences of observations, the algorithim has regret at most log ( number of strategies) with respect to the best strategy in a set.” This is sometimes called online learning with experts. Online Optimization Constraint Online learning refers to optimizing a predictor via a learning algorithm tunes parameters on a per-example basis. This may or may not be applied in the Online Information Setting, and the strategy may or may not satisfy Adversarial setting theory. Online Computational Constra
2 0.9367497 267 hunch net-2007-10-17-Online as the new adjective
Introduction: Online learning is in vogue, which means we should expect to see in the near future: Online boosting. Online decision trees. Online SVMs. (actually, we’ve already seen) Online deep learning. Online parallel learning. etc… There are three fundamental drivers of this trend. Increasing size of datasets makes online algorithms attractive. Online learning can simply be more efficient than batch learning. Here is a picture from a class on online learning: The point of this picture is that even in 3 dimensions and even with linear constraints, finding the minima of a set in an online fashion can be typically faster than finding the minima in a batch fashion. To see this, note that there is a minimal number of gradient updates (i.e. 2) required in order to reach the minima in the typical case. Given this, it’s best to do these updates as quickly as possible, which implies doing the first update online (i.e. before seeing all the examples) is preferred. Note
3 0.76547402 109 hunch net-2005-09-08-Online Learning as the Mathematics of Accountability
Introduction: Accountability is a social problem. When someone screws up, do you fire them? Or do you accept the error and let them continue? This is a very difficult problem and we all know of stories where the wrong decision was made. Online learning (as meant here), is a subfield of learning theory which analyzes the online learning model. In the online learning model, there are a set of hypotheses or “experts”. On any instantance x , each expert makes a prediction y . A master algorithm A uses these predictions to form it’s own prediction y A and then learns the correct prediction y * . This process repeats. The goal of online learning is to find a master algorithm A which uses the advice of the experts to make good predictions. In particular, we typically want to guarantee that the master algorithm performs almost as well as the best expert. If L(e) is the loss of expert e and L(A) is the loss of the master algorithm, it is often possible to prove: L(A) les
4 0.72831744 8 hunch net-2005-02-01-NIPS: Online Bayes
Introduction: One nice use for this blog is to consider and discuss papers that that have appeared at recent conferences. I really enjoyed Andrew Ng and Sham Kakade’s paper Online Bounds for Bayesian Algorithms . From the paper: The philosophy taken in the Bayesian methodology is often at odds with that in the online learning community…. the online learning setting makes rather minimal assumptions on the conditions under which the data are being presented to the learner —usually, Nature could provide examples in an adversarial manner. We study the performance of Bayesian algorithms in a more adversarial setting… We provide competitive bounds when the cost function is the log loss, and we compare our performance to the best model in our model class (as in the experts setting). It’s a very nice analysis of some of my favorite algorithms that all hinges around a beautiful theorem: Let Q be any distribution over parameters theta. Then for all sequences S: L_{Bayes}(S) leq L_Q(S)
5 0.72081673 378 hunch net-2009-11-15-The Other Online Learning
Introduction: If you search for “online learning” with any major search engine , it’s interesting to note that zero of the results are for online machine learning. This may not be a mistake if you are committed to a global ordering. In other words, the number of people specifically interested in the least interesting top-10 online human learning result might exceed the number of people interested in online machine learning, even given the presence of the other 9 results. The essential observation here is that the process of human learning is a big business (around 5% of GDP) effecting virtually everyone. The internet is changing this dramatically, by altering the economics of teaching. Consider two possibilities: The classroom-style teaching environment continues as is, with many teachers for the same subject. All the teachers for one subject get together, along with perhaps a factor of 2 more people who are experts in online delivery. They spend a factor of 4 more time designing
6 0.71083432 308 hunch net-2008-07-06-To Dual or Not
7 0.69083828 385 hunch net-2009-12-27-Interesting things at NIPS 2009
8 0.64387667 186 hunch net-2006-06-24-Online convex optimization at COLT
9 0.59476018 309 hunch net-2008-07-10-Interesting papers, ICML 2008
10 0.56759584 251 hunch net-2007-06-24-Interesting Papers at ICML 2007
11 0.56066942 388 hunch net-2010-01-24-Specializations of the Master Problem
12 0.5506655 28 hunch net-2005-02-25-Problem: Online Learning
13 0.53497338 133 hunch net-2005-11-28-A question of quantification
14 0.51897293 373 hunch net-2009-10-03-Static vs. Dynamic multiclass prediction
15 0.51542401 298 hunch net-2008-04-26-Eliminating the Birthday Paradox for Universal Features
16 0.51096499 258 hunch net-2007-08-12-Exponentiated Gradient
17 0.50765735 451 hunch net-2011-12-13-Vowpal Wabbit version 6.1 & the NIPS tutorial
18 0.50554127 163 hunch net-2006-03-12-Online learning or online preservation of learning?
19 0.48968717 78 hunch net-2005-06-06-Exact Online Learning for Classification
20 0.48577401 346 hunch net-2009-03-18-Parallel ML primitives
topicId topicWeight
[(3, 0.053), (27, 0.306), (53, 0.033), (55, 0.072), (67, 0.269), (94, 0.125)]
simIndex simValue blogId blogTitle
1 0.9763341 296 hunch net-2008-04-21-The Science 2.0 article
Introduction: I found the article about science using modern tools interesting , especially the part about ‘blogophobia’, which in my experience is often a substantial issue: many potential guest posters aren’t quite ready, because of the fear of a permanent public mistake, because it is particularly hard to write about the unknown (the essence of research), and because the system for public credit doesn’t yet really handle blog posts. So far, science has been relatively resistant to discussing research on blogs. Some things need to change to get there. Public tolerance of the occasional mistake is essential, as is a willingness to cite (and credit) blogs as freely as papers. I’ve often run into another reason for holding back myself: I don’t want to overtalk my own research. Nevertheless, I’m slowly changing to the opinion that I’m holding back too much: the real power of a blog in research is that it can be used to confer with many people, and that just makes research work better.
2 0.94076049 192 hunch net-2006-07-08-Some recent papers
Introduction: 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
same-blog 3 0.87116486 252 hunch net-2007-07-01-Watchword: Online Learning
Introduction: It turns out that many different people use the term “Online Learning”, and often they don’t have the same definition in mind. Here’s a list of the possibilities I know of. Online Information Setting Online learning refers to a problem in which unlabeled data comes, a prediction is made, and then feedback is acquired. Online Adversarial Setting Online learning refers to algorithms in the Online Information Setting which satisfy guarantees of the form: “For all possible sequences of observations, the algorithim has regret at most log ( number of strategies) with respect to the best strategy in a set.” This is sometimes called online learning with experts. Online Optimization Constraint Online learning refers to optimizing a predictor via a learning algorithm tunes parameters on a per-example basis. This may or may not be applied in the Online Information Setting, and the strategy may or may not satisfy Adversarial setting theory. Online Computational Constra
4 0.86735773 463 hunch net-2012-05-02-ICML: Behind the Scenes
Introduction: This is a rather long post, detailing the ICML 2012 review process. The goal is to make the process more transparent, help authors understand how we came to a decision, and discuss the strengths and weaknesses of this process for future conference organizers. Microsoft’s Conference Management Toolkit (CMT) We chose to use CMT over other conference management software mainly because of its rich toolkit. The interface is sub-optimal (to say the least!) but it has extensive capabilities (to handle bids, author response, resubmissions, etc.), good import/export mechanisms (to process the data elsewhere), excellent technical support (to answer late night emails, add new functionalities). Overall, it was the right choice, although we hope a designer will look at that interface sometime soon! Toronto Matching System (TMS) TMS is now being used by many major conferences in our field (including NIPS and UAI). It is an automated system (developed by Laurent Charlin and Rich Ze
5 0.81124073 41 hunch net-2005-03-15-The State of Tight Bounds
Introduction: What? Bounds are mathematical formulas relating observations to future error rates assuming that data is drawn independently. In classical statistics, they are calld confidence intervals. Why? Good Judgement . In many applications of learning, it is desirable to know how well the learned predictor works in the future. This helps you decide if the problem is solved or not. Learning Essence . The form of some of these bounds helps you understand what the essence of learning is. Algorithm Design . Some of these bounds suggest, motivate, or even directly imply learning algorithms. What We Know Now There are several families of bounds, based on how information is used. Testing Bounds . These are methods which use labeled data not used in training to estimate the future error rate. Examples include the test set bound , progressive validation also here and here , train and test bounds , and cross-validation (but see the big open problem ). These tec
6 0.76202232 258 hunch net-2007-08-12-Exponentiated Gradient
7 0.76105887 337 hunch net-2009-01-21-Nearly all natural problems require nonlinearity
8 0.75967443 183 hunch net-2006-06-14-Explorations of Exploration
9 0.75893813 351 hunch net-2009-05-02-Wielding a New Abstraction
10 0.75431758 435 hunch net-2011-05-16-Research Directions for Machine Learning and Algorithms
11 0.75266206 352 hunch net-2009-05-06-Machine Learning to AI
12 0.7520507 426 hunch net-2011-03-19-The Ideal Large Scale Learning Class
13 0.75187606 293 hunch net-2008-03-23-Interactive Machine Learning
14 0.7517556 347 hunch net-2009-03-26-Machine Learning is too easy
15 0.75165761 304 hunch net-2008-06-27-Reviewing Horror Stories
16 0.75165421 311 hunch net-2008-07-26-Compositional Machine Learning Algorithm Design
17 0.75143498 158 hunch net-2006-02-24-A Fundamentalist Organization of Machine Learning
18 0.75033939 432 hunch net-2011-04-20-The End of the Beginning of Active Learning
19 0.74933666 345 hunch net-2009-03-08-Prediction Science
20 0.74755269 95 hunch net-2005-07-14-What Learning Theory might do