{"id":38,"date":"2005-03-04T00:23:42","date_gmt":"2005-03-04T06:23:42","guid":{"rendered":"\/?p=38"},"modified":"2005-03-04T20:53:11","modified_gmt":"2005-03-05T02:53:11","slug":"the-big-o-and-constants","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=38","title":{"rendered":"The Big O and Constants in Learning"},"content":{"rendered":"

The notation g(n) = O(f(n))<\/em> means that in the limit as n<\/em> approaches infinity there exists a constant C<\/em> such that the g(n)<\/em> is less than Cf(n)<\/em>.<\/p>\n

In learning theory, there are many statements about learning algorithms of the form “under assumptions x<\/em>,y<\/em>, and z<\/em>, the classifier learned has an error rate of at most O(f(m))<\/em>“.<\/p>\n

There is one very good reason to use O(): it helps you understand the big picture and neglect the minor details which are not important in the big picture. However, there are some important reasons not to do this as well.<\/p>\n

    \n
  1. Unspeedup<\/strong> In algorithm analysis, the use of O() for time complexity is pervasive and well-justified. Determining the exact value of C is inherently computer architecture dependent. (The “C” for x86 processors might differ from the “C” on PowerPC processors.) Since many learning theorists come from a CS theory background, the O() notation is applied to generalization error. The O() abstraction breaks here—you can not generally change learning algorithm and decrease your error rate by some constant factor.<\/li>\n
  2. You’re fired<\/strong> When you go and run a learning algorithm to acquire some predictor, the performance it achieves is a key quantity of significant interest. Using an algorithm with merely twice the error rate of a better algorithm can easily make the difference between “it works” and “it doesn’t”. This is not often true when programming, as evidenced by the large number of people who use computationally inefficient languages to solve problems.<\/li>\n<\/ol>\n

    We can’t say “never use O()<\/em>“, because sometimes abstracting away details is the right thing to do. However, any use of O()<\/em> should be analyzed for “reasonableness” more thoroughly than for computational complexity. Similarly, more interest should be allocated to improving constants in such analysis than is done in algorithms.<\/p>\n","protected":false},"excerpt":{"rendered":"

    The notation g(n) = O(f(n)) means that in the limit as n approaches infinity there exists a constant C such that the g(n) is less than Cf(n). In learning theory, there are many statements about learning algorithms of the form “under assumptions x,y, and z, the classifier learned has an error rate of at most … <\/p>\n

    Continue reading “The Big O and Constants in Learning”<\/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":[8],"tags":[],"class_list":["post-38","post","type-post","status-publish","format-standard","hentry","category-prediction-theory"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/38","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=38"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/38\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=38"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=38"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=38"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}