{"id":975,"date":"2009-10-03T07:01:48","date_gmt":"2009-10-03T13:01:48","guid":{"rendered":"http:\/\/hunch.net\/?p=975"},"modified":"2009-10-03T07:20:30","modified_gmt":"2009-10-03T13:20:30","slug":"static-vs-dynamic-multiclass-prediction","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=975","title":{"rendered":"Static vs. Dynamic multiclass prediction"},"content":{"rendered":"

I have had interesting discussions about distinction between static vs. dynamic classes with Kishore<\/a> and Hal<\/a>. <\/p>\n

The distinction arises in multiclass prediction settings. A static set of classes is given by a set of labels {1,…,k}<\/i> and the goal is generally to choose the most likely label given features. The static approach is the one that we typically analyze and think about in machine learning. <\/p>\n

The dynamic setting is one that is often used in practice. The basic idea is that the number of classes is not fixed, varying on a per example basis. These different classes are generally defined by a choice of features. <\/p>\n

The distinction between these two settings as far as theory goes, appears to be very substantial. For example, in the static setting, in learning reductions land<\/a>, we have techniques now for robust O(log(k))<\/i> time prediction in many multiclass setting variants. In the dynamic setting, the best techniques known are O(k)<\/i>, and furthermore this exponential gap may be essential, at least without further assumptions.<\/p>\n

Are there techniques for converting from dynamic multiclass to static multiclass? For example, we could embed a dynamic set of classes within a much larger static set ranging over all possible dynamic classes while eliminating all class-dependent features. In some cases, this approach may work well, but I’ve also seen it fail, with the basic problem being that a learning algorithm might easily choose an invalid class. We could of course force a learning algorithm to choose amongst the dynamically valid set, but I don’t know a general way to do that without making the running time at least scale with the number of valid classes.<\/p>\n

So, a basic question that’s bothering me is: When and how can we effectively predict amongst a set of dynamically defined classes in sublinear time? A quick answer is “it’s not possible because simply reading off the set of dynamically defined classes require O(class count)<\/i> time”. This answer isn’t satisfying, because there are many ways to implicitly specify a set in sublinear time. So the modified question is “Are there natural ways to dynamically define classes in sublinear time? And can these be used for sublinear prediction?”<\/p>\n","protected":false},"excerpt":{"rendered":"

I have had interesting discussions about distinction between static vs. dynamic classes with Kishore and Hal. The distinction arises in multiclass prediction settings. A static set of classes is given by a set of labels {1,…,k} and the goal is generally to choose the most likely label given features. The static approach is the one … <\/p>\n

Continue reading “Static vs. Dynamic multiclass prediction”<\/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,16],"tags":[],"class_list":["post-975","post","type-post","status-publish","format-standard","hentry","category-machine-learning","category-problems"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/975","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=975"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/975\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=975"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=975"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=975"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}