昨年の論文をふりかえる
新年すっかりあけてました。
今年もよろしくお願いします。
年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。
D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf]
Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるような変数x1^*...xn^*を求めよという問題。このようなタスク設定はタンパク質の構造決定、写真が複数枚与えられての立体情報の復元など非常に広い問題で使われている。自然言語処理でも、普通現実的に使うCRFは一本鎖のグラフィカルモデルで、自由に枝を張ってしまう計算量が爆発してしまうというのが、枝を結構自由にはっても解けるようになったと思っていただければすごさがわかるかとおもう。
ずっと長い期間様々な方法が提案されてきたが、この論文では、非常に簡単なメッセージパッシングアルゴリズム、線形計画緩和、双対問題、制約の逐次追加などこれまでの技術の集大成でこの問題をきれいに解決している。UAIのbest paper。
G. Nong, et. al. Two Efficient Algorithms for Linear Suffix Array Construction, 2008, [pdf]
（上のconference version) Linear Suffix Array Construction by Almost Pure Induced-Sorting, DCC 2009 [pdf]
Moriさんにより実装・比較(sais)
線形時間で接尾辞配列を構築するコードがC++で100行弱で書けて、しかも結構速く（O(nlogn)の方がまだ速いがかなり縮まってきた）、無駄に使う作業領域量はほとんど無い。元東工大の伊藤さんから始まり、元群馬大の儘田さんや森さんなどが培ってきた二段階法の進化形。私も接尾辞配列の構築については１０年以上付き合ってきているので、この進化は感慨深い。すごく単純に言うと、接尾辞配列を構築する際には接尾辞を全部ソートする必要はなく、ソートが必要なものと必要じゃないものに分けることができて、一部をソートしたら、残りの順序はそのソート結果から自動的に決定できる。で、このソートが必要な部分の結果を求めるには元のテキストの部分文字列を新しい文字に置き換えて、長さが半分以下になったテキストに対する接尾辞配列の結果を使えば求まる。長さが半々になっていく再帰問題で、他の部分が全部線形時間で求まるのならば全体も線形時間でできる。で、この新しい文字への置き換えの部分も先ほどの「ソート結果から自動的に決定できる」のと全く同じアルゴリズムを動かすと求まるよというのが上の論文。部分文字列をradix sortしているだけといえばそうだが、ここまできれいにまとまるのはすごい。
B. Zhao, et.al, "Efficient multiclass maximum margin clustering", ICML 2008 [pdf]
前回のエントリで書いたので詳細は書かないが、読めば読むほど面白い。ちなみに著者らが所属している清華大の研究グループはものすごい量の論文を国際会議に通していることで話題になっているとこlink。
A. Haghighi, et. al. "Learning Bilingual Lexicons from Monolingual Corpora", ACL 2008 [pdf]
これも以前勉強会で紹介した[ppt]ものなので詳細は書きません。最近、自分でも学習データ作ったり、いろいろやってて思うのは、言語リソースを作るのには「教師無学習で得られた結果に対してアノテーションをする」というのが、かなり良いような気がしてきています（論文や研究としてはやりにくいけど、リソース作るコストとかにも注目した"Cheap and Fast But is it Good? ..."[pdf]とか論文も出てきてるし、何かできるかな）
Mihai Patrascu, "Succincter", FOCS 2008 [pdf]
圧縮したままアクセスするようなデータ構造でかなり基礎的な部分での上限を変えた。ブロックを符号化した場合、基本的にはブロックまとめて復元しないといけない。たとえば３通りある文字を符号化しようと思うと1bitでは保存できないので、なくなく2bit使うしかなく1文字あたり1bit近く損してしまう。そこで文字をk個まとめて符号化すると無駄は1文字あたり1/k bitと減るが、各文字の情報はブロック全体に広がってしまっているので、1文字にアクセスする場合もブロック全体を復元する必要があり、必要な作業領域と、必要な計算量は線形の関係があるように思われていた。
論文では、この直感は間違いで、溢れた情報を再帰的に管理していけば、ブロックあたり2bitの無駄を許すならば、ブロックサイズの対数時間でアクセスができるということを示してます。理論的にはすごいものだし（いろいろな簡潔構造の上限がだいぶ下がった）、実用的にももうちょい工夫すれば算術圧縮のランダム復元など面白いのができるだろうなぁ。student best paper
今年もいろいろ情報紹介していきます。よろしく
Comments
> 教師無学習で得られた結果に対してアノテーションをする
大切なところを教示してもらうという感じなので，これは能動学習の枠組みで論じられるのではないでしょうか？
教師なしで作れる改良できる言語モデルとかは，6グラムが9グラムになったインパクトは，3グラムが6グラムにになったそれよりずっと小さいので，データが増えてもあまりもう伸びないように思います．
で，しばらくは教師が必要なところがどうしても重要になる気がします．半教師学習，転移学習，能動学習あたりの枠組みが活発になっていると思います．
Posted by: しましま | 2009.01.17 at 02:45 AM
>大切なところを教示してもらうという感じなので，これは能動学習の枠組みで論じられるのではないでしょうか？
確かに能動学習ですが、一サンプル毎教示するのではなく、クラスタリングした結果に対して正解を与えるというイメージです（すでにこういうのはありますかね？）。データは似ているものが多いので、クラスタリングした結果に対して与えると、効率よく、しかも網羅的にできるんではないかなぁと思います。
このあたりの話を、場当たり的ではなく、普遍的な、しかも実用的な話にどうもっていけるかが面白そうかなぁと思います。
Posted by: hillbig | 2009.01.18 at 10:28 PM
If some one needs expert view regarding blogging and site-building afterward i advise him/her to visit this weblog, Keep up the nice job.
Posted by: Awesome | 2012.11.23 at 01:26 PM
Superb website you have here but I was wondering if you knew of any discussion boards that cover the same topics discussed here? I'd really like to be a part of group where I can get responses from other experienced people that share the same interest. If you have any recommendations, please let me know. Cheers!
Posted by: iherb.com coupon | 2013.12.28 at 02:47 AM
Hello my family member! I wish to say that this article is amazing, nice written and come with almost all vital infos. I'd like to look extra posts like this .
Posted by: Wizard101 Crown Generator | 2014.01.06 at 01:02 PM
I'm curious to find out what blog system you are working with? I'm experiencing some small security problems with my latest site and I'd like to find something more risk-free. Do you have any suggestions?
Posted by: Wizard101 Crown Generator | 2014.01.07 at 06:45 PM
This was a period from the 1920s though the 1950s when sweets were as popular as teen idols in America. As an example, you can approach wherever you would like the windows to be. It is a unique hobby that teaches the lesson of animal care.
Posted by: top bar bee hive plans | 2014.03.03 at 08:04 AM
It is important to avoid procrastinating if at all possible also. It has been considered the "evil twin" of earth--just like its hospitable sister but without the kindness to life. She also said that Arthur has a history of depression and suicide attempts.
Posted by: Low cost venus factor | 2014.03.10 at 09:24 AM
Virgo ascendant is considered as the self-ascendant of Rahu. Her standout scenes including a tender moment as she jams a hypodermic needle into a nosy patient's eyeball and a moment where she kills a male prostitute with a pair of scissors. Check out my related article as of March 4, 2007 to see my results.
Posted by: Free venus factor | 2014.03.11 at 07:49 PM
She used it to write and record much of her 2006 album Folk Is the New Black, including "Jackie Skates," 'because the rich bright top end lent itself to the guitar part. A small razor knife will be required, as will a battery powered hand grinder known as a dremel tool. Considering that then, there continues to be a lineal evolution of several numerous several years of instruments that can be directly in comparison with present-day acoustic guitars.
Posted by: acoustic guitars cheap | 2014.03.14 at 08:02 PM
They were expensive to design, costly to reproduce andrequired lots of manpower and postage to assemble and distribute. Facilities like parking, non smoking room, parks, etc. {Be sure to keep pillows and blankets on hand in the room, and just as before, focus on darker colors so they will not distract from the TV experience|One side of the fridge will warm one room, and cool the other|) Also there are some great cheap shots to be head from which are only one dollar apiece|The benefit of getting a brand for yourself in Facebook can't be overstated whenever you run a small business|Your fitness room does not have to be your whole finished basement|The Xbox 360 serves as what they call a "whole home node," meaning it's simply an additional "node" for an existing IPTV setup|1)
Posted by: media room | 2014.03.16 at 02:04 PM
A rinse of water and vinegar can be used in finished toys to remove crayon marks and oil based discoloration. A normal parrot will probably scream at least two times a day. Watch out for exposed nails, screw heads or threads, and staples.
Posted by: plans for wooden toys | 2014.03.16 at 04:04 PM
Empower BES is available for a small, one-time fee and is only available for devices using the 4. On a subconscious level it makes your reader feel obligated to buy. As far as importance of a mail message is concerned, it is basically associated with its attachments.
Posted by: wood mailbox post plans | 2014.03.17 at 11:18 AM
You can easily find these at your local feed store or a tractor supply store. You should never support unlawful logging as this kills our own jungles. and Europe and has helped revitalize the fruit growing industry in the provinces, particularly the Philippine's native orange variety called "dalandan".
Posted by: chicken house plan | 2014.03.17 at 06:59 PM
A battery charger will save you some money from buying replacement batteries, since the video display screen requires pretty big power consumption. The wires can be set into place using a staple gun. This kind of horticulture device speeds up your own shredding activity.
Posted by: wood trellis plans | 2014.03.22 at 10:19 PM
but what's happeningin your imagination is a series of negative images or 'pictures' caused by this sudden turn of events. Just when you think you've got something figured out, it's time to be skeptical again. The colour of your splashback could be the same as the rest of the tiles in the room.
Posted by: hammock | 2014.03.23 at 08:33 AM
The Economy and Private School Loans Private loans may are actually hit probably the most difficult with all the falling economy and students will still possess a hard time getting private loans miley cyrus concert tickets also, do not obtain a car that you cannot conveniently afford.
Posted by: miley cyrus concert tickets | 2014.03.27 at 03:28 AM
The Venus Factor Program had been developed to solve the weight related stuffs of females. This is a unique program which basically only focuses on the female physiology functioning. The quality of this program is that it has been made just only for women. It had been developed by John who is a world famous health expert. He has many celebrities into his client list and is there for a decade now. He has given all his brain and expertise into this thing. The Venus Factor
Posted by: The Venus Factor | 2014.04.21 at 10:26 PM
I write a comment when I appreciate a article on a website or I have something to add to the discussion. It is triggered by the fire communicated in the article I browsed. And after this post 昨年の論文をふりかえる: DO++. I was actually moved enough to post a leave a responsea response ;) I actually do have a few questions for you if you do not mind. Is it only me or does it look as if like a few of the comments come across as if they are left by brain dead folks? :-P And, if you are writing at other online sites, I would like to keep up with everything new you have to post. Would you list all of your community pages like your linkedin profile, Facebook page or twitter feed?
Posted by: busco mujeres | 2014.05.25 at 11:31 AM
It's true - what you do, at work and at play, can lead to venous insufficiency. Her laptop is in front, with them, and the laptops they are donating to friends and relatives in Zoomwood are packed safely in a compartment under the back seats. But her twin is far more into academics than tennis, so don't look for a new sister duo.
Posted by: venus diet program youtube | 2014.07.14 at 11:08 AM
Pretty! This was an extremely wonderful post. Many thanks for providing this information.
Posted by: rapid weight loss diet | 2014.08.04 at 08:52 PM
When someone writes an article he/she maintains the thought of a user in his/her brain that how a user can understand it. Thus that's why this article is perfect. Thanks!
Posted by: from quest bars this | 2014.08.28 at 02:55 AM
Greate article. Keep writing such kind of info on your site. Im really impressed by it. Hey there, You've done a great job. I'll definitely digg it and in my opinion suggest to my friends. I'm confident they'll be benefited from this site.
Posted by: Quest Bars | 2014.08.28 at 09:43 AM
If you want to obtain much from this post then you have to apply these techniques to your won weblog.
Posted by: Quest Bars Free Sample | 2014.09.10 at 05:38 AM
They will make a decision on your ability to maintain yourself, how much confidence and respect you seem to have, and whether or not they even want to deal with you. If you place your energy towards it, you can succeed in body building. One of the most popular problems for most individuals who try to build muscle is that they often fed with the incorrect information.
Posted by: Adonis Golden Ratio | 2014.09.18 at 02:53 PM
Heey there! I know this is somewhat off topic bbut I was wondering which blog platform are you using for this site? I'm getting fed up of Wordpress becawuse I've had problems with hackers and I'm looking at alternatives for another platform. I would be awesome if you could point me inn the direction of a good platform.
Posted by: wordpress platforms theme | 2014.10.06 at 03:19 PM
Great post! We are linking to this great post on our website. Keep up the great writing.
Posted by: Where Can I Buy Quest Bars Cheap | 2014.10.07 at 02:26 AM
Thanks very interesting blog! Quest Bars blogesaurus
Posted by: quest protein bars | 2014.10.07 at 11:13 PM
Every weekend i used to visit this web site, as i wish for enjoyment, as this this site conations in fact nice funny information too. Quest Bars blogesaurus
Posted by: quest bars Free sample | 2014.10.08 at 09:42 AM
Hi colleagues, nice piece of writing and pleasant urging commented here, I am genuinely enjoying by these. Quest Bars blogesaurus
Posted by: quest Bars Free Sample | 2014.10.10 at 08:24 AM
Hi, for all time i used to check webpage posts here early in the morning, since i enjoy to gain knowledge of more and more.
Posted by: Diet Plans for Women to Lose Weight | 2014.10.10 at 02:14 PM
You have made some really good points there. I looked on the internet for more info about the issue and found most people will go along with your views on this website. Quest Bars blogesaurus
Posted by: quest protein bars | 2014.10.12 at 10:47 AM
It's wonderful that you are getting ideas from this piece of writing as well as from our dialogue made here. Quest Bars blogesaurus
Posted by: quest bars | 2014.10.12 at 11:20 AM
Hi my family member! I ish to say that this article iis awesome, great written and include almost all significant infos. I'd like to peer extra posts like this .
Posted by: Http://Insole.Publog.Jp | 2014.10.29 at 06:44 AM
Why visitors still make use of to read news papers when in this technological world the whole thing is existing on net?
Posted by: We build futures. We create citizens of tomorrow. We make a difference..... | 2014.11.02 at 01:31 PM
After hours of searching via the web, individuals could either uncover one that suits them or none at all. The ONLY roadblock is in DEVELOPING the complete, total. A couple of old-time gangsters (played by Keith David and Terry Crews) front Kevin a.
Posted by: the BETTING SAMURAI customer reviews | 2014.11.13 at 04:12 AM
At fiгst glance (and each subsequent one, too), the ԛuestion seems either redundant, or absurԀ. The big decision you'll have to mаke is whаt level of challenge you want to have. Goѵinda secretly enjoys Katrina and Salman currently being a adore guru will help Govindɑ to express his love.
Posted by: http://freepdfsite.com | 2014.12.10 at 12:00 AM
I'm more than happy to uncover this website. I want to to thank you for ones time just for this fantastic read!! I definitely appreciated every little bit of it and I have you bookmarked to see new information in your website.
Posted by: Michell | 2014.12.19 at 10:54 AM
Hello my loved one! I wish to say that this post is amazing, great written and include almost all important infos. I would like to peer extra posts like this .
Posted by: http://maxinetrahan.deviantart.com/ | 2015.02.13 at 04:02 PM
This article is in fact a good one it helps new internet viewers, who are wishing in favor of blogging.
Posted by: custom t shirts online | 2015.07.06 at 11:20 PM
If you desire to take much from this paragraph then you have to apply such techniques to your won website.
Posted by: delicious.Com | 2015.07.13 at 12:21 AM
Thе note provided that all ρrinciƿal and accrued interest was due in а single balloon payment at the еnd of the note term, and neithег principal nor interest could be prepaid. You need to seek Tax Filing Help if you would like stay awаy from Tax Levy complications liкe a Wage Lеvy or Bank Leνy. Avoid hype or ցimmicks and let people knoա exactly what to expect and what they are required to do in oгder to receive what they are being offered.
Posted by: Boca Raton Cpat Test Questions | 2015.09.07 at 10:55 AM
always i used to read smaller content that as well clear their motive, and that is also happening with this article which I am reading at this time.
Posted by: t shirt sale | 2015.09.19 at 05:43 PM
I loved as much as you will receive carried out right here. The sketch is tasteful, your authored material stylish. nonetheless, you command get bought an nervousness over that you wish be delivering the following. unwell unquestionably come more formerly again as exactly the same nearly a lot often inside case you shield this hike.
Posted by: custom tee | 2015.10.28 at 12:54 PM