04 February 2009

Beating the state of the art, big-O style

I used to know a fair amount about math; in fact, I even applied to a few grad schools to do logic (long story, now is not the time). I was never involved in actual math research (primarily because of the necessary ramp-up time -- thank goodness this doesn't exist as much in CS!), but I did get a sense from my unofficial undergrad advisor how things worked. The reason I started thinking of this is because I recently made my way about halfway through a quite dense book on long games by a prof from grad school (I cross-enrolled at UCLA for a few semesters). The basic idea of a countable game is that there is a fixed subset A of [0,1] (subset of the reals) and two players alternate play. In each move, they play an integer from 0 to 9. They play for a countably infinite number of moves, essentially writing down (in decimal form) a real number. If, at the "end", this number is in A, then player 1 wins; otherwise, player 2 wins. Both players know A. The set A is said to be determined if there is a strategy that will force a win; it is undetermined otherwise. A long game is the obvious generalization where you play for longer than countable time. The details don't matter.

This led me to think, as someone who's moved over to working a lot on machine learning: is there an analogous question for online learning? There are several ways to set this up and I won't bore you with the details (I doubt any reader here really cares), but depending on how you set it up, you can prove several relatively trivial, but kind of cute, results (I say trivial because they took me on the order of hours, which means that someone who knows what they're doing probably would see them immediately). I basically did this as a mental exercise, not for any real reason.

But it got me thinking: obviously machine learning people wouldn't care about this because it's too esoteric and not at all a realistic setting (even for COLTers!). I strongly doubt that logicians would care either, but for a totally different reason. From my interaction, they would be interested if and only if two things were satisfied: (a) the result showed some interesting connection between a new model and existing models; (b) the proofs were non-trivial and required some new insight that could be then applied to other problems. Obviously this is not my goal in life, so I've dropped it.

This led to me introspect: what is is that we as a community need in order to find some result interesting? What about other fields that I claim to know a bit about?

Let's take algorithms for a minute. Everything here is about big-O. Like the math types, a result without an interesting proof is much less interesting than a result with an interesting proof, though if you start reading CS theory blogs, you'll find that there's a bit of divide in the community on whether this is good or not. But my sense (which could be totally broken) is that if you have a result with a relatively uninteresting proof that gets you the same big-O running time as the current state of the art, you're in trouble.

I think it's interesting to contrast this with what happens in both NLP and ML. Big-O works a bit differently here. My non-technical description of big-O to someone who knows nothing is that it measure "order of magnitude" improvements. (Okay, O(n log n) versus O(n log log n) is hard to call an order of magnitude, but you get the idea.) An equivalent on the experimental side would seem to be something like: you cut the remaining error on a problem by half or more. In other words, if state of the art is 60% accuracy, then an order of magnitude improvement would be 80% accuracy or better. At 80% it would be 90%. At 90% it would be 95% and so on. 90.5% to 91.2% is not order of magnitude.

I actually like this model for looking at experimental results. Note that this has absolutely nothing to do with statistical significance. It's kind of like reading results graphs with a pair of thick glasses on (for those who don't wear glasses) or no glasses on (for those who wear think glasses). I think the justification is that for less than order of magnitude improvement, it's really just hard to say whether the improvement is due to better tweaking or engineering or dumb luck in how some feature was implemented or what. For order of magnitude improvement, there almost has to be something interesting going on.

Now, I'm not proposing that a paper isn't publishable if it doesn't have order of magnitude improvement. Very few papers would be published this way. I'm just suggesting that improving the state of the art not be -- by itself -- a reason for acceptance unless it's an order of magnitude improvement. That is, you'd either better have a cool idea, be solving a new problem, analyzing the effect of some aspect of a problem that's important, etc., or work on a well trod task and get a big-O improvement.

What I'm saying isn't novel, of course... the various exec boards at the ACL conferences have been trying to find ways to get more "interesting" papers into the conferences for (at least) a few years. This is just a concrete proposal. Obviously it requires buy-in at least of area chairs and probably reviewers. And there are definitely issues with it. Like any attempt to make reviewing non-subjective, there are obviously corner cases (eg., you have a sort-of-interesting idea and an almost-order-of-magnitude improvement). You can't mechanize the reviewing process. But frankly, when I see paper reviews that gush over tiny improvements in the state of the art in an otherwise drab paper, I just get annoyed :).

39 comments:

Suresh said...

Although, even in algorithms land, it's about big-O if the problem is interesting. If not, that doesn't help that much. I think ultimately in theoryCS (as in much of math), interestingness is a kind of PageRank: the more links from the result to other results, the better.

Or you could look at the LONG list that Terry Tao once made

Aji said...

I recently came accross your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.


Miriam

http://www.craigslistposter.info

cutepig said...

I do not know why I was very like to play the EVE, so I need eve isk and the eve gold , do you know the eve online isk.

Anonymous said...

網頁設計,情趣用品,情趣用品,情趣用品,情趣用品
色情遊戲,寄情築園小遊戲,情色文學,一葉情貼圖片區,情惑用品性易購,情人視訊網,辣妹視訊,情色交友,成人論壇,情色論壇,愛情公寓,情色,舊情人,情色貼圖,色情聊天室,色情小說,做愛,做愛影片,性愛

免費視訊聊天室,aio交友愛情館,愛情公寓,一葉情貼圖片區,情色貼圖,情色文學,色情聊天室,情色小說,情色電影,情色論壇,成人論壇,辣妹視訊,視訊聊天室,情色視訊,免費視訊,免費視訊聊天,視訊交友網,視訊聊天室,視訊美女,視訊交友,視訊交友90739,UT聊天室,聊天室,豆豆聊天室,尋夢園聊天室,聊天室尋夢園,080聊天室,080苗栗人聊天室,女同志聊天室,上班族聊天室,小高聊天室 

AV,AV女優
視訊,影音視訊聊天室,視訊交友
視訊,影音視訊聊天室,視訊聊天室,視訊交友,視訊聊天,視訊美女

. said...

酒店經紀PRETTY GIRL 台北酒店經紀人 ,禮服店 酒店兼差PRETTY GIRL酒店公關 酒店小姐 彩色爆米花酒店兼職,酒店工作 彩色爆米花酒店經紀, 酒店上班,酒店工作 PRETTY GIRL酒店喝酒酒店上班 彩色爆米花台北酒店酒店小姐 PRETTY GIRL酒店上班酒店打工PRETTY GIRL酒店打工酒店經紀 彩色爆米花

avineshpvs said...

hey i totally agree to your point. I also came across some papers recently were there was a small tweaking done to the existing work.. I feel this isn't the breakthrough research... Anyways Nice Blog.. I follow your blog :)

Nightlife Web Directory said...

I really liked your blog! You have some great content. Check out my blog and give me some feedback Please come visit my site Free Adult Entertainment when you got time.

Advertising Agencies said...

Well, nice article buddy… Someone will love to read this infor if I tell her about this. She’s really interested in this subject. Thanks again… Please come visit my site EadvertisingNetwork when you got time.

hotel rooms said...

This is just another reason why I like your website. I like your style of writing you tell your stories without out sending us to 5 other sites to complete the story. Please come visit my site Motelhotel Business Directory when you got time.

酒店上班請找艾葳 said...

艾葳酒店經紀提供專業的酒店經紀,酒店上班,酒店打工、兼職、酒店相關知識等酒店相關產業服務,想加入這行業的水水們請找專業又有保障的艾葳酒店經紀公司!
艾葳酒店經紀是合法的公司、我們是不會跟水水簽任何的合約 ( 請放心 ),我們是不會強押水水辛苦工作的薪水,我們絕對不會對任何人公開水水的資料、工作環境高雅時尚,無業績壓力,無脫秀無喝酒壓力,高層次會員制客源,工作輕鬆。
一般的酒店經紀只會在水水們第一次上班和領薪水時出現而已,對水水們的上班安全一點保障都沒有!艾葳酒店經紀公司的水水們上班時全程媽咪作陪,不需擔心!只提供最優質的酒店上班環境、上班條件給水水們。

personal training said...

Comprehensive web resource of Aerobics Instruction, Classes & Instruction, Exercise & Fitness Clothing Retail, Exercise & Fitness Equipment & Supplies Dealers, Exercise & Fitness Equipment & Supplies Wholesale & Manufacturers, Exercise & Fitness Equipment Rental, Exercise & Fitness Equipment Service & Repair, Fitness Consultants, Gymnasium Equipment & Supplies Dealers, Gymnastics Instruction.

custom homes said...

Really great work. Congrats to everyone who are involved with this project. The website layout and graphics are really cool. Please come visit my site Realtor Home Builders Directory when you got time.

Anonymous said...

Thanks for sharing,
Dissertation | Essay | Research Paper

Anonymous said...

Great post, i really appreciate it.
Term Paper | Thesis

peter.w said...

钢托盘
仓储笼
托盘
钢托盘
折叠式仓储笼
钢托盘
折叠式仓储笼
钢托盘
折叠式仓储笼
塑料托盘,塑料栈板
湖南塑料托盘,塑料栈板
长沙塑料托盘,塑料栈板
仓储笼
托盘
仓储笼
托盘
仓储笼
钢托盘
仓储笼
钢托盘
仓储笼
仓储笼
托盘
仓库货架
仓储货架
塑料托盘
钢托盘
折叠式仓储笼
仓储笼
钢托盘
手动液压托盘搬运车
货架
托盘
仓储笼
货架
货架
货架
横梁式货架
托盘
仓储笼
手动液压托盘搬运车
仓库货架
仓库货架
货架
仓储货架
仓库货架
库房货架

peter.w said...

搬运车
堆高车
油桶车
手动液压搬运车
液压托盘搬运车
搬运车
液压搬运车
手动搬运车
托盘搬运车
手动液压托盘搬运车
不锈钢搬运车
镀锌搬运车
电子秤搬运车
称重式搬运车
搬运地牛
手动液压拖板车
迷你搬运车
重载搬运车
超长搬运车
超宽搬运车
低放搬运车
高起升搬运车
剪式搬运车
电动搬运车
半电动搬运车
平台车
手动液压平台车
电动平台车
液压平台车
油桶车
圆桶车
油桶搬运车
油桶装卸车
圆桶装卸车
油桶夹

peter.w said...

堆高车
手动堆高车
手动叉车
堆垛车
手动堆垛车
手动叉车
半电动堆高车
半电动堆垛车
电动堆高车
电动堆垛车
堆高机
叉车
电动叉车
内燃叉车
液压升降平台
电动升降平台
移动式登车桥
固定式登车桥

deLi said...

sohbet odaları
sohbet
yonja
chat siteleri
forum siteleri
toplist ekle
sohbet
yonja
netlog
sohbet
kizlarla sohbet
sohbet
sohbet
dini sohbet
islami sohbet
chat
sohbet chat
mirc indir
cinsel sohbet
porno izle
camfrog indir
lida
kurumsalseo.com R10 lida fx15 pohudey zayıflama

Sheldon said...

sick. well done r-mean. keep it up
getse hayoutioune

Thesis Writing | Dissertation Writing | Essay Writing | Assignment Writing

tariely said...

Классный фильм на кинозоуне.
электронная почта без регистрации

Sheldon said...

absense of mind can do things without having reasons.. one can say that

Thesis Help | Dissertation Help | Essay Help | Assignment Help

Paul said...

Recently I came across your blog and have been reading along. I think I would leave my first comment. I do not know what to say, but I like reading. Good blog. I will continue to visit the blog very often.
Squidoo Lens Creation Social Media News Squidoo Lens Creation Link Building Services

dissertations quality said...

Your all thought is very helpful and I good feel read your blog

Thanks

Anonymous said...

электронная почта без регистрации

youtube said...

klip izle | malatya park | youtube | video izle

Anonymous said...

Hi,
This is inspiring; I am very pleased by this post. Nice work, thanks for such information.

gamefan12 said...

I think this is so good and definitely benefit a lot of people if they use it. I think this is so good.
fort lauderdale auto accident attorney

qishaya said...

one day i went shopping outside,and in an ed hardy store,I found some kinds of ed hardy i love most they are Your website is really good Thank you for the information ed hardy ed hardy ed hardy clothing ed hardy clothing ed hardy shoes ed hardy shoes don ed hardy don ed hardy ed hardy clothes ed hardy clothes ed hardy bags ed hardy bags ed hardy swimwear ed hardy swimwear ed hardy jeans ed hardy jeans ed hardy mens ed hardy mens Thank you for the information

良哥 said...

Teenagers in a track adidas tennis shoes can go through shoes rate discount adidas sneakers teenage runner well knows that newest adidas shoes 2010 to wear the right shoes discount moncler outlet any cross country among world cheap adidas shoes especially important to the sportsman wholesale adidas shoes a young person growing up adidas shoes outlet Not only do they want to discount moncler t-shirt grow out of their shoes cheap jordan shoes but shape of their feet changes new jordan shoes which means every time we new jordan shoes the time comes to get air jordan 2010 a new pair of shoes eveyone discount jordan shoes a good choice to get jumpman23 it with a high material Jordan ajf shoes that breathes easily on random Newest Timberland shoes 2010 They should be extended runs cheap Nike shox shoes give enough support to athlets discount brand shoes especially around the ankles area cheap Nike Dunk shoes to avoid injury your ankles AIR MAX shoes outlet when you make your trip 2010 New GHD something in store possible fit Benefit GHD his is also the way to Black GHD that don't fit properly only CHI hair straightener

良哥 said...

but they are not returnable GHD IV Salon Styler Every woman needs to have GHD Rare Styler a few tips to spot Gold GHD the inside of the bag Gray GHD Handbags are considered as Kiss GHD Styler will focus on various items Pink GHD is perfect just for you Pure Black GHD is primarily a company that Pure White GHD if you really want to Purple GHD The qualities that make a cheap bourke dooney handbags running shoe with a good grip authentic dooney bourke bags and material that breathes easily newest dooney bourke handbags They should be sure that moncler vest light enough to do sports dooney bourke new purses but still give enough support to discount dooney bourke handbags outlet around the ankles to avoid injury wholesale Rolex watches you want a high quality moncler we can provide many moncler t-shirts moncler jackets does spend a lot of money moncler coats choose us and you will not regret.dooney bourke totes have the perfect apparel cheap ugg boots you have to know what discount ugg boots there to take your money ugg boots it focuses on your convenience classic ugg boots One of the major attractions ugg classic tall boots

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..
sesli sohbetsesli chatkamerali sohbetseslisohbetsesli sohbet sitelerisesli chat siteleriseslichatsesli sohpetseslisohbet.comsesli chatsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet
seslisohbetsesli sohbetkamerali sohbetsesli chatsesli sohbetkamerali sohbet

speed dating in new york said...

As a newbie, this article was really helpful, thanks for sharing!

cilemsin42 said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..
sesli sohbetsesli chat
sesli sohbet siteleri

sesli chat siteleri sesli sohbetsesli chat
sesli sohbet siteleri
sesli chat siteleri
SesliChat
cılgın sohbet
güzel kızlar
bekar kızlar
dul bayanlar
seviyeli insanlar
yarışma
canlı müzik
izdivac
en güzel evlilik
hersey burada
sesliparti
seslisohbet odalari
Sesli adresi
Sesli Chat
SesliChat Siteleri
Sesli Chat sitesi
SesliChat sitesi
SesliSohbet
Sesli Sohbet
Sesli Sohbet Sitesi
SesliSohbet Sitesi
SesliSohbet Siteleri
Muhabbet Sitesi
kamerali chat
Görüntülü Sohbet
Hasret gülleri
Çet sitesi
SesliSohbet
Sesli Sohbet
Canli sohbet
Turkce sohbet
Kurtce Sohbet
Kurtce Chat
Kurtce Muhabbet
Kurtce Sohbet
Kurdish Chat
SesliChat
Sesli Chat
SesliSanal
Guncel Haber
sohbet Sitesi
Chat sitesi..

daniel john said...

You made some good points there. I did a search on the topic and found most people will agree with your blog.

Term papers

seldamuratim said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it to a few friends of mine that I know would enjoy reading..

sesli sohbet
seslisohbet
sesli chat
seslichat
sesli sohbet sitesi
sesli chat sitesi
sesli sohpet
kamerali sohbet
kamerali chat
webcam sohbet

combattery84 said...

HP dv9700 battery
HP F4809A Battery
HP nc8000 battery
HP nc8230 battery
HP pavilion zd8000 battery
HP f2024b battery
HP f4812a battery
HP Pavilion ZV5000 battery
HP Pavilion DV1000 battery
HP Pavilion ZD7000 Battery
HP Pavilion DV2000 battery
HP Pavilion DV4000 Battery
HP Pavilion dv6000 Battery
HP Pavilion DV9000 Battery
HP F4098A battery
HP pavilion zx6000 battery
HP omnibook xe4400 battery
HP omnibook xe4500 battery
HP omnibook xe3 battery
Notebook NX9110 battery
IBM 02K6821 battery
IBM 02K7054 battery
IBM 08K8195 battery
IBM 08K8218 battery
IBM 92P1089 battery
IBM Thinkpad 390 Series battery
IBM Thinkpad 390X battery
IBM ThinkPad Z61m Battery
IBM 02K7018 Battery
IBM thinkpad t41p battery
IBM THINKPAD T42 Battery

combattery84 said...

IBM ThinkPad R60 Battery
IBM ThinkPad T60 Battery
IBM ThinkPad T41 Battery
IBM ThinkPad T43 Battery
IBM ThinkPad X40 Battery
Thinkpad x24 battery
ThinkPad G41 battery
IBM thinkpad r52 battery
Thinkpad x22 battery
IBM thinkpad t42 battery
IBM thinkpad r51 battery
Thinkpad r50 battery
IBM thinkpad r32 battery
Thinkpad x41 battery
SONY VGP-BPS2 Battery
SONY VGP-BPS2C Battery
SONY VGP-BPS5 battery
SONY VGP-BPL2C battery
SONY VGP-BPS2A battery
SONY VGP-BPS2B battery
SONY PCGA-BP1N battery
SONY PCGA-BP2E battery
SONY PCGA-BP2NX battery
SONY PCGA-BP2S battery
SONY PCGA-BP2SA battery
SONY PCGA-BP2T battery
SONY PCGA-BP2V battery
SONY PCGA-BP4V battery
SONY PCGA-BP71 battery
SONY PCGA-BP71A battery
SONY VGP-BPL1 battery
SONY VGP-BPL2 battery

DiSCo said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
kameralı sohbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
seslidunya
seslisehir
sesli sex

Sesli Chat said...

Really trustworthy blog. Please keep updating with great posts like this one. I have booked marked your site and am about to email it

to a few friends of mine that I know would enjoy reading..
seslisohbet
seslichat
sesli sohbet
sesli chat
sesli
sesli site
görünlütü sohbet
görüntülü chat
kameralı sohbet
kameralı chat
sesli sohbet siteleri
sesli chat siteleri
sesli muhabbet siteleri
görüntülü sohbet siteleri
görüntülü chat siteleri
görüntülü muhabbet siteleri
kameralı sohbet siteleri
kameralı chat siteleri
kameralı muhabbet siteleri
canlı sohbet
sesli muhabbet
görüntülü muhabbet
kameralı muhabbet
birsesver
birses
seslidunya
seslisehir
sesli sex