« txをアップデートしました。 | Main | tx-0.08 »

2008.02.15

線形識別器チュートリアル

ワークショップ中の夕食で話したのですが、今のところ日本で(素性関数ベース&線形識別器)機械学習のいろいろな手法をまとめて体系的に教えてる資料などがあまりないなぁという話をしていました。

で、探すと、このあたりの大部分をまとめて説明しているいいチュートリアル(英語)がありました。
夏の学校資料[pdf]
その他のコードやリンク

ちょっとだけ解説

現在自然言語処理の多くで使われている学習器は線形識別器です。
入力x(例:単語、文、文書)から出力y(例:品詞、品詞列、文書のトピック)を予測したいという場合は、(x,y)のペアからいろいろな値を取り出し(x,yのペアから値を取り出す関数を素性関数と呼ぶ)、その値を並べたベクトルを素性ベクトルと呼び、f(x,y)とかきます。そして、その素性ベクトルf(x,y)と同じ次元数を持つ重みベクトルwとの内積を測って、その値が正か負か、または大きいか小さいかを調べて、出力は何が尤もらしいかを予測します。

機械学習では、この重みベクトルwを正解データの集合(x_1, y_1), ..., (x_n, y_n) を使って、推定(普通は訓練と呼ぶ)します。正解が正しくでるようにwをチューニングするわけです。このチューニングは基本的には訓練データから各素性に関する統計量を取り、最適化問題を解く事で行われます。

例えば、入力が文書で、出力が「その文書がスパムだったら正の値、そうじゃなかったら負の値をとる」、という問題の場合は、まず、実際にスパムかどうかのラベルがついた文書集合を集めます(もしくは自分で作る)。次に素性関数を設計します。文書分類の場合は単語の出現が重要な情報となるので、各単語が1次元分を担当し、各素性の値は例えばその出現回数とすることが多いです。

素性関数1, 2, 3, 4がそれぞれ単語"Best","Drug","Congratulation","flower"に対応するとしたら、訓練データを使って重みベクトルを訓練すると、重みベクトルは(-1, 3, 1, -2)というふうに、drug, congratulationが出たらスパムとなって、best, flowerが出たらスパムじゃないとなってくれるように学習されます。

それで文書として、best, drug, congratulation, flowerという単語がそれぞれ、1, 3, 0, 1回出現しているものが与えられたら、その素性ベクトルは(1,3,0,1)であり、重みベクトルとの内積は -1*1 + 3*3 + 0*0 + 1*1 = 9 となり、これは正なのでスパムとめでたく判定されるわけです。

線形識別器は非常に単純ですが、それでも自然言語処理だと有効です。理由の一つとして、次元数が非常に大きく(例えば数千万次元とか)、線形でも十分区別する能力があるということがあげられます。

で、問題はどのようにこのwを訓練するかということになり、これには、いろいろな方法があります。例えばNaive Bayesは一番単純なモデルです(それでも強力だが)。このモデルでは各次元が完全に独立だとし、それぞれ独立に学習、推定し、結果をまとめます。

もうちょっと賢い線形識別器だと、各素性は独立じゃなく相関があるものだとし(推定時は独立に扱うが)、学習時にどのような基準(損失関数)で学習するかも工夫されてます。

有名なのだと、出力が簡単な問題(例えば文書分類とか二値分類)を解こうとする場合は次のようなものがあります。
- 線形対数モデル(最大エントロピーモデル、ロジスティック回帰)
- (Linear) Support Vector Machines

出力が構造を持ってる場合、例えば系列(品詞列とか形態素列)とかの場合は、上記のそれぞれが次のようなモデルに拡張されます。
- Conditional Random Fields (条件付確率場)
- Max-margin Markov Network
これらのモデルでは出力、素性、損失関数が部品に分解できるようになっており、出力の候補数が入力長の指数個に比例する数ぐらいあっても動的計画法などで効率よく学習/推定ができるようになっています。

あとは、実装が非常に簡単だけど強力な次のような手法があります。これらはオンライン学習、つまり訓練データを1例ずつ見てパラメータを更新していきます。
- Averaged Perceptron 
- Structured Perceptron 
- MIRA

これらについては上記のチュートリアルにまとめられてます。

#あるといっても広く知られるためにも、やはり日本語の資料もつくりたいですね。

|

« txをアップデートしました。 | Main | tx-0.08 »

Comments

s/drag/drug/;
s/congratuation/congratulations/;
おつかれさまですといわざるをえない。

Posted by: Gus | 2008.02.15 at 01:26 PM

指摘どもです。直しました。
半分間違いは識別モデルとしては失格ですw

Posted by: oka | 2008.02.15 at 04:37 PM

This post is genuinely a nice one it helps new internet users, who are wishing for blogging.

Posted by: best adjustable dumbbells | 2013.08.04 at 06:56 PM

But with serious uprisings looming over from gay marriage to Lords reform, Downing Street seems to be drawing in their horns avicii tickets 2014 what will be the guidelines regarding a family savings as mentioned above.

Posted by: avicii tickets 2014 | 2014.03.02 at 07:36 AM

Hello, Neat post. There iss an isѕue along witɦ your wеb site in wweb explorer, would check this? IE still is the market leadеr and а huɡе cօmponent to otɦer people will pass over your wonderful writing because of this problem.

Posted by: clean House | 2014.07.05 at 04:19 AM

Thssе are actually impreѕsive ideas in regarding blogging. Youu Һaave touchned some good thingѕ here. Any way keep up wrinting.

Posted by: free music download program | 2014.07.06 at 08:57 PM

Thankvulness to my father who staed to me conceerning ths blog, this weblog iss truly awesome.

Posted by: free music tempo changer software | 2014.07.13 at 10:30 AM

We stumbled over here different wweb page and thought I may as wdll check things out. I like what I see so i am just following you. Look forward to going over your web page yet again.

Posted by: plumbing Sydney | 2014.07.13 at 05:23 PM

Amazing! Itss truly remarkable article, I have got much clear idea about from this article.

Posted by: chore Charts printable free | 2014.07.15 at 01:29 AM

I have been eхploring foг a lttle foг any high-quality articles orr weblog poҳts in tҺis sort of ѕpace . Exploring in Yahoo I at last stumbled upon this web site. Reading this info So i am glad to convey that I have a vеry excellent uncanny feeling I discoѵered еxɑcty what I needed. I moѕt undoubtedly will make certain to don?t fail to remember this web sitte and proviodes іt a llook regularly.

Posted by: chore charts templates free | 2014.08.12 at 11:59 PM

Hello just wanted to give you a quick heads up and let you know a few of the images aren't loading properly. I'm not sure why but I think its a linking issue. I've tried it in two different browsers and both show the same outcome.

Posted by: hackingengine.com | 2014.08.21 at 11:24 AM

It's awesome in support of me to have a web site, which is helpful in favor of my experience. thanks admin

Posted by: xbox live gold codes | 2014.08.21 at 03:35 PM

Bij Farm Heroes moet je drie dezelfde gewassen met elkaar zien te combineren.

Posted by: Farm Heroes Saga Cheats | 2014.11.24 at 02:00 AM

This hack tool is really easy to use.

Posted by: monster legends hack v.1.3 Free download | 2014.11.25 at 01:10 AM

Do ӏ want to find a girlfriend that I can settle down with, and fall in love (gasp). t feel awkward or uncomfortable when you use these eleνator insoles. Govinda secretly enjoys Katrina and Salman currently bеing a adore ɡuru wіll help Govinda to express his love.

Posted by: The Beta Switch Free | 2014.11.26 at 07:29 PM

Verify that the hack functions nicely and that it is completely cost-free of viruses.

Posted by: monster legends cheat codes for ipad | 2014.12.07 at 04:03 AM

Genuinely when someone doesn't be aware of then its up to other viewers that they will help, so here it happens.|

Posted by: Sheryl | 2015.01.07 at 12:47 PM

I like it when people get together and share views. Great blog, continue the good work!

Posted by: match.com | 2015.04.07 at 01:35 AM

Fantastic goods from you, man. I've understand your stuff previous to and you are just extremely fantastic. I actually like what you've acquired here, certainly like what you're stating and the way in which you say it. You make it entertaining and you still take care of to keep itt wise. I can't wait to read much more from you. This is actually a tremendous site.

Posted by: https://usapothecary.com | 2015.04.14 at 06:56 AM

Hi, this weekend is fastidious in favor of me, as this occasion i am reading this enormous informative piece of writing here at my house.

Posted by: Top Puzzle Game | 2015.05.18 at 06:41 PM

area unit these procedures particular for the shopper, or area unit they solely a product of today's surreal ideals. Your plastic surgeon will evaluate your health and make the determination. Talk things out with your medical professional beforehand.

Posted by: http://168txw.com | 2015.07.02 at 03:24 AM

A user can just click on 'start a hang out' making him visible to everyone the people in his social circles and send them a notification that their friend is hanging out and so they will then join the concept out and commence videos chat in a very private chat room. In this short article I want to show you how to find market which has cheaper clicks so it is possible to make more money from your traffic. People soon came to understand that getting listed within the online directories may lead to a higher search results ranking, and they also begun to exploit that.

Posted by: google adwords certification | 2015.08.03 at 10:23 PM

The player will have asphalt 8 hack on windows phone to pay a fairly economical cost. In terms of visual appearance, very good audio system along with a throw shot. More than 40 percent of users in a two way radio, newspapers, and your real e-Mail address. You will experience reality by having a common language closer to machine level would make a camping trip, it can be witnessed. Or a short span of time.

Posted by: asphalt 8 cheats download free | 2015.08.20 at 04:01 AM

Therefore, if you're a developer, you can even try to expand on the functionalities of this impressive program. This material may not be published, broadcast, rewritten, or redistributed in full without first contacting the author. You should know various things about Long Island DJ.

Posted by: telecharger virtual Dj | 2015.08.22 at 06:08 AM

These are mystery boxes containing prizes, which could be diamonds. One unit of corn planted in your field yields two corn units in your silo. The action begins with Chauncey (the man who brought this sport to the beaches of Santa Monica) dodging three balls coming from all sides, in front and behind, as he leaps into the air and lands in a split position on the sand.

Posted by: boom beach diamants | 2015.08.22 at 09:21 AM

Quality posts is the important to be a focus for the viewers to pay a quick visit the web page, that's what this web site is providing.

Posted by: Cheapest MoT Manchester | 2015.08.29 at 12:55 PM

Cold sores usually show on the lip area, but can also develop on the cheeks and.

Posted by: http://facebook.com | 2015.09.02 at 10:29 AM

Well, the study demonstrates honey healed lip sores 43% better than acyclovir, and healed genital herpes sores 53% better than acyclovir.

Posted by: natural cure for herpes | 2015.09.12 at 06:03 AM

When someone writes an post he/she retains the plan of a user in his/her brain that how a user can understand it. Thus that's why this piece of writing is outstdanding. Thanks!

Posted by: clash of clans hack | 2015.09.12 at 11:08 PM

All fuel tanks at BP filling stations must be equipped with large basins (buckets) around each fill pipe.

Posted by: gas station near me | 2015.09.20 at 05:54 AM

Given the amazing value and functionality of this i - Pad application, however, you might already have it in your i - Pad. Retaining in line with the '70s aesthetic, the Russos largely withdraw from your unnecessary use concerning computer-generated mental imagery, conjointly it pays off splendidly. Hippy Grandparents - Okay, maybe a hippy grandma or grandpa is just as cool as a Disco grandparent.

Posted by: avengers age of ultron online movie | 2015.09.20 at 01:41 PM

PC keyboards have a lot of key combination andd basically have more keys than gaming peripherals like joysticks or gamepads. Additionally, due consideration has been givewn to the competitive landscape to enable clients understand the mmarket structure and growth prospects in coming years. These metals can get nto yoour drfinking water from natural sources, industrial processes, and the materials used in your plumbing system.

Posted by: Pendaftaran STIN 2016 | 2015.09.27 at 04:09 PM

Finally, Seal of Approval carpet cleaning solutions must show that they do not add to residue on stack yarn that can accelerate color change.

Posted by: biodegradable cleaning products | 2015.10.22 at 06:49 PM

Do you have a spam issue on this blog; I also am a blogger, and I was wondering your situation; we have created some nice procedures and we are looking to swap solutions with others, be sure to shoot me an email if interested.

Posted by: sewer line replacement | 2015.12.24 at 11:15 AM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/40127685

Listed below are links to weblogs that reference 線形識別器チュートリアル:

« txをアップデートしました。 | Main | tx-0.08 »