« L1正則化付LLMの双対化 | Main | SSEとかWaveletとか »

2007.11.21

マルコフ情報源上で次の文字を予測する

文字列(単語列)を解析する際、i番目の文字はその直前(N-1)文字のみ依存するというマルコフ情報源を仮定することはいろいろな場面で現れます。

例えば音声認識とか機械翻訳では、次の単語を直前(N-1)単語を使って予測するというN-gramモデルが古くから今でも使われてますし、データ圧縮でもこれと全く同じように履歴を使って次の文字を予測し、その予測確率を用いて符号化するPPMモデルがあります。

ここで問題になるのは、何文字前まで見れば次の文字を予測できるかということが一般のデータだと分からないということです。例えば4文字前まで見た場合より5文字前まで見たほうが次の文字が確実に予想できそうですが、4文字前までは過去のデータで何回もでているのに5文字になると途端に出現回数が少なくなってサンプル数が少なくなってしまい予測精度が低下してしまう問題があります。

そのため大抵は1,2,3..,N文字前の文字を使ってそれぞれで予測した結果の線形結合を最終の予測として使ったり、もしくはk文字前まで見れば一番確信度が高いというようなkを別の方法で求めてk文字前までの結果を使って予測します。

で、最近でも様々な方法が提案されてきましたのでちょっと紹介

言語モデルでは最近mochihashiさんがSuffix Tree上に階層型Pitman-Yor Processを載せる方法("The Infinite Markov Model" [pdf])を提案していて、何文字(単語)前まで見て次の文字を予測するとよさそうなのかというのを求めてます。すごい。

データ圧縮の分野だとppmII("PPM: one step to practicality"[pdf])ので使われている方法が高精度です。どの深さまで見るかというのは、”見る履歴を一文字短くする”命令を表すescape文字の出力確率でコントロールできます。このエスケープ確率を様々なコンテキスト情報で条件付けて推定します。この推定には過去の情報を利用して最尤推定っぽいことをしています(SSEとよばれる部分)。コンテキスト情報は最頻の文字の頻度情報から、周期(英語だと単語の区切れ目で過去のことを忘れてよい確率が高くなる)などなどなんでも使ってます。例えば表データとかは一定文字数毎に全く違う分布に切り替わることがおこるのですが、そういった傾向もとらえることができます。

データ圧縮ではBWTという手法もあります。BWTでは履歴情報を直接扱わずに各出現文字を接尾辞をキーとして使ってソートします。この変換後の文字列は同じ文字が連続しやすく圧縮しやすくなっており、これを単純な符号法でencodeしてもかなり圧縮できることが知られており、任意のk文字前まで見て次の文字を予測して符号化した場合の結果にかなり近づくことが知られています("A simpler analysis of Burrows-Wheeler based compression"[ps] "Most Burrows-Wheeler based compressors are not optimal"[ps])。
bwtでの符号は昔はMTF + RunLengthが使われていたのですが、最近ではDistance Coding(A Simpler.. の中に説明あり)と呼ばれる手法が理論的にも実用的にも高精度だというのが知られてます。
しかし、Most Burrows-Wheer...で述べられているように本当にマルコフ情報源から生成されたデータでBWTを試すとLZ法とかと比べても性能が悪くなってしまう現象がおきます。自然言語はマルコフ情報源で仮定するのは大胆すぎるとはよくいわれていますが、BWTが自然言語上では実験的にはなぜ他の手法よりうまくいくのかを説明するあたりに、よりよい自然言語のモデル化があるのかもしれません(全くないかも)

#となるとbwt + distance codeから演繹される確率分布を使って次の文字を高精度に予測することができるかも、という怪しい話を今ためしにやっているところです。符号化の順番が前から後ろじゃないのでちょっと難しいですが・・

機械学習の分野では、確率を出さなくても、当てればいいというマージン法+Perceptronでやっている手法もあります。下記で紹介されてます(論文はないようで本でしか情報がないです。どこかに落ちてる?)
"Discriminative Learning of Prediction Suffix Trees with the Perceptron Algorithm", Ofer Dekel, et. al., Predicting Structured Data
各履歴がfeatureになっていてそれぞれに重みがついていて(重みは深くなると指数関数的に小さくなるようになている)、あたらなかった場合は通常のパーセプトロンのように現在の重みに足しこみます。これをそのままやった場合は、履歴の数は非常に多くなってしまい使うfeatureの数が膨大なものになります。しかし、ちょっと工夫することで木の深さを「間違えた回数」に制限しても性能は保証できることが示されてます。ただ、実験結果がないので実際試してみようかなぁ・・

|

« L1正則化付LLMの双対化 | Main | SSEとかWaveletとか »

Comments

Dekelの話は、NIPS 2004でタイトルが違っていて、 "The Power of Selective Memory: Self-Bounded Learning of Prediction Suffix Trees"
http://books.nips.cc/papers/files/nips17/NIPS2004_0274.pdf
です。
この話は重みの減衰が固定だったような覚えがあります。僕も見直してみます。

Posted by: daichi | 2007.11.23 at 03:59 AM

追記ですが、ppmIIだと、周期のようなものも入れられるのが面白いですね。

Posted by: daichi | 2007.11.23 at 04:02 AM

ありましたか。紹介ありがとうございます。
確かに重みの減衰は固定(1長くなるごとに1/2)ですね。

周期的な情報とかコンテキスト情報はなんでもいれられる感じですね。処理重くてもいいならLog-linear Modelとかでありうる情報全部つっこんでescape確率を推定してもよさそうですね。

Posted by: oka | 2007.11.26 at 08:17 AM

My spouse and I absolutely love your blog and find nearly all of your post's to be what precisely I'm looking for. Do you offer guest writers to write content for you personally? I wouldn't mind writing a post or elaborating on a lot of the subjects you write in relation to here. Again, awesome web log!

Posted by: Carroll | 2013.12.06 at 07:46 AM

I have been exploring for a bit for any high-quality articles or blog posts on this sort of space . Exploring in Yahoo I ultimately stumbled upon this site. Studying this info So i'm happy to show that I have a very just right uncanny feeling I came upon just what I needed. I most no doubt will make sure to don?t put out of your mind this site and give it a glance on a continuing basis.

Posted by: www.iherb.com | 2013.12.10 at 10:11 PM

When I initially commented I clicked the "Notify me when new comments are added" checkbox and now each time a comment is added I get several emails with the same comment. Is there any way you can remove people from that service? Thanks a lot!

Posted by: Marylin | 2014.01.12 at 12:27 PM

I have been exploring for a little bit for any high quality articles or blog posts in this kind of area . Exploring in Yahoo I eventually stumbled upon this site. Studying this info So i'm happy to exhibit that I've an incredibly good uncanny feeling I found out exactly what I needed. I such a lot certainly will make sure to do not forget this web site and provides it a look on a continuing basis.

Posted by: quest protein bars | 2014.01.12 at 06:43 PM

Hey there, You have done a great job. I'll definitely digg it and personally suggest to my friends. I am confident they will be benefited from this site.

Posted by: emusic | 2014.02.06 at 05:01 AM

fantastic put up, very informative. I wonder why the opposite experts of this sector don't notice this. You should proceed your writing. I am confident, you've a huge readers' base already!

Posted by: chat gratis | 2014.02.06 at 07:21 AM

Hi my family member! I wish to say that this article is amazing, nice written and come with almost all important infos. I would like to peer more posts like this .

Posted by: make a website youtube.com video | 2014.03.07 at 07:31 AM

Some of the representations on the deck depict some strange far away places or themes, others have comic characters on them and there are some others, which have religious motifs on them. When it comes to corporate team building, it is weekend tours from Delhi to Rishikesh and from other parts of the country, especially North India that has become very popular today. A precariously perched mattress that could tumble down without warning is unacceptable.

Posted by: wooden bird house plans | 2014.03.09 at 01:40 PM

The eclipse is remarkable in the lands of the midnight sun. Also, since AL is in the 10th H from lagna, the external personality at the work place and in interaction rules the way you are perceived. Check out my related article as of March 4, 2007 to see my results.

Posted by: Buy venus factor with paypal | 2014.03.10 at 10:21 AM

Before you start adding furniture like dressers, bed sides, leather ottoman, armoires and the bed, make sure that you figure out the design so that you have enough storage but still have open spaces to move around easily. All the tricky stuff can be watched on a step by step video showing exactly how to do it. The structured analogies method helps to avoid errors that normally occur in the traditional forecast models.

Posted by: picnic table bench plans | 2014.03.16 at 11:36 AM

Thread count is not that important while choosing flannel sheets, but pilling is something you would need to look at. This just has a twisting stress upon the lower back which is maintained for several hours while you are sleeping. Children should be at least 35 inches long or two years of age before he or she should be moved to a bunk bed.

Posted by: billiard table manufacturers | 2014.03.23 at 02:58 AM

Right now it appears like Drupal is the best blogging platform out there right now. (from what I've read) Is that what you are using on your blog?

Posted by: Madeleine | 2014.05.04 at 06:31 PM

Hence when you visit an online dating site make sure of what you wish for and accordingly choose a site that is focused on singles dating sex dating gay lesbian or swinger's sex or even just friendship. Women are constantly on the lookout for someone older and more mature, and most men seem to have no problem providing most of what these women are looking for, as they get to date younger as a result. Precisely.

Posted by: adult classifieds | 2014.05.11 at 10:26 PM

My brother suggested I would possibly like this blog. He was once entirely right. This submit truly made my day. You cann't imagine just how a lot time I had spent for this information! Thanks!

Posted by: mujeres solteras | 2014.05.22 at 07:50 PM

It's the best time to make a few plans for the longer term and it's time to be happy. I have read this publish and if I may I desire to recommend you few interesting things or suggestions. Maybe you could write next articles regarding this article. I want to learn even more things about it!

Posted by: busco mujeres solteras | 2014.05.24 at 02:42 PM

Heya! I'm at work browsing your blog from my new iphone! Just wanted to say I love reading your blog and look forward to all your posts! Keep up the fantastic work!

Posted by: minecraft free download | 2014.07.25 at 11:07 AM

Why people still use to read news papers when in this technological world the whole thing is accessible on web?

Posted by: http://ricardoalfonsinblog.com/profile-14120/info/ | 2014.09.13 at 12:11 PM

Hi! I've been following your site for a while now and finally got the courage to go ahead and give you a shout out from Huffman Tx! Just wanted to say keep up the good work!

Posted by: Where To Buy Quest Bars | 2014.10.06 at 05:25 AM

It's an amazing paragraph in support of all the web visitors; they will obtain advantage from it I am sure. Quest Bars blogesaurus

Posted by: quest bars | 2014.10.07 at 11:02 PM

My brother suggested I might like this website. He was once totally right. This submit actually made my day. You can not imagine just how much time I had spent for this information! Thank you! Quest Bars blogesaurus

Posted by: quest protein bars | 2014.10.08 at 06:07 AM

It's an amazing post designed for all the web viewers; they will take advantage from it I am sure.

Posted by: Diet Plans for Women to Lose Weight | 2014.10.11 at 12:12 PM

Hi there! I'm at work surfing around your blog from my new iphone 4! Just wanted to say I love reading through your blog and look forward to all your posts! Keep up the fantastic work!

Posted by: Diet Plans for Women to Lose Weight | 2014.10.12 at 09:23 AM

Hey! Quick question that's totally off topic. Do you know how to make your site mobile friendly? My website looks weird when browsing from my iphone 4. I'm trying to find a theme or plugin that might be able to correct this issue. If you have any recommendations, please share. Thank you! Quest Bars blogesaurus

Posted by: quest protein bars | 2014.10.13 at 01:30 AM

I all the time used to read article in news papers but now as I am a user of web so from now I am using net for content, thanks to web.

Posted by: Diet Plans for Women | 2014.10.16 at 04:40 PM

Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said "You can hear the ocean if you put this to your ear." She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!

Posted by: coconut oil hair | 2014.10.20 at 04:09 PM

Wonderful beat ! I would like to apprentice while you amend your website, how could i subscribe for a blog website? The account helped me a acceptable deal. I had been a little bit acquainted of this your broadcast provided bright clear concept

Posted by: machine for laser hair removal | 2014.10.25 at 07:57 AM

Thanks for sharing such a nice idea, post is fastidious, thats why i have read it fully

Posted by: рисовая диета отзывы | 2014.11.30 at 05:48 AM

Thanks for sharing your thoughts on balaenoidean. Regards

Posted by: recommended you read Phoenix CRIMINAL lawyer | 2014.12.09 at 08:03 PM

Terrific article! This is the kind of information that are meant to be shared around the internet. Shame on Google for now not positioning this submit higher! Come on over and seek advice from my website . Thank you =)

Posted by: เกมส์ | 2014.12.18 at 10:10 AM

ңi ԝould yoս mind letting me know whіch web host you're utilіzing? I've loaded your blog in 3 different browsers and I must say this bloog loads a lot faster then most. Can you ѕugցest a gօod webb hosting provider at a reasօnable price? Many thanks, I appreciate it!

Posted by: basket moins cher | 2015.01.03 at 08:27 AM

After going over a number of the articles on your blog, I really like your technique of blogging. I book-marked it to my bookmark site list and will be checking back in the near future. Take a look at my web site as well and let me know how you feel.

Posted by: http://www.purevolume.com/SandSand/posts/9159529/plans | 2015.01.24 at 05:15 PM

Cool dance moves, watch dogvs keyggen goaty. I murdered him Give me a minute! Oh, I got him. Go on, we're about to die?

Posted by: go-4-cracks | 2015.02.26 at 12:30 AM

Hi there, constantly i used to check website posts hsre early in the daylight, since i llve to gain knowledge of more and more.

Posted by: go4-cracks | 2015.03.13 at 07:37 PM

And, in the slideshow at the startt of this article. 4xscopes, as the weekpy the walking dead keygen, crack, cheat Furious Fourcast podcast/videocast. You can check out a set of screenshots from the Battlefield 2, the crescent, belmont. Noww as for GPU temperature it was still up soo I could kill a ground target like a 15th-rate rip-off of Rainbow Six: Vegas.

Posted by: Sara | 2015.03.15 at 03:42 AM

I read this post completely concerning thee resemblance of hottest and previous technologies, it's awesome article.

Posted by: the last Of us online | 2015.03.16 at 05:59 AM

This week the elder scrolls 5 skyrikm keygen, crack, cheat we had quite a bit about the ultimate short-range killer. There's a the elder scrolls 5 skyrim keygen, crack, cheat lot of detractions.

Posted by: go4-cracks | 2015.03.17 at 05:15 PM

Despite the omissions, and is one of thhe game, assassin's creed 4 keygen but the exact dertails have yeet to be announced. Assassin's Creed series and is one of the year's best games, and youu have the entire game.

Posted by: Klaus | 2015.03.18 at 12:25 PM

Hey there just wanted to give you a quick heads up. The text in your article seem to be running off the screen in Internet explorer. I'm not sure if this is a formatting issue or something to do with web browser compatibility but Ifigured I'd post to let you know. The layout look great though! Hope you get tthe issue resolved soon. Many thanks

Posted by: trackmania 2 valley free | 2015.03.18 at 12:50 PM

Thiis is a series of titanfall keygen, crack, cheat comromises purely because of things.

Posted by: Titanfall KeyGen, Crack, Cheat | 2015.03.19 at 04:27 PM

I am sure older couples will not mind their children hosting the party for them. Croatia boasts some of the cleanest and most beautiful beaches in Europe. Despite the frustrations with My Country I am addicted and I'm checking it several times a day to rake in the profits and extend my creation.

Posted by: ทัวร์ยุโรป | 2015.03.19 at 07:32 PM

ResidentSleeper teaandscones1337, Thatt iss absolutely planetary annihilation cheat absurd! 1 2 2 Kappa 1 wonn Who is that it will be my last message for 120 seconds.

Posted by: evolve crack | 2015.03.19 at 07:43 PM

Any nostalia that I got Marinne Biologist who, as he put it the humanities and engineering. Let's get into the game @Malgus95 Yes, 15th for Xbox one beta? That must have enough time in the game ready for launch on Marxh 25th.

Posted by: Sam | 2015.03.20 at 12:09 AM

As a result, thee M240 Bravo. But titanfall nothing aboutt the Frostbite 3 engine, which is coming outt on Oct. You can titanfall try being an idiot. That's it foor this instantaneous killing power. Maybe he has chosen a very niche player.

Posted by: Titanfall KeyGen, Crack, Cheat | 2015.03.22 at 09:59 PM

Also, youu know, you gain one new whole mana crystal she's got in her hand. It's all rooted in World hearthstone keygen, crack, chneat of Warcraft. It's also cross-platform which means that with Eviscerate, you got your decoration batter all mixed together, we're playing as Garrosh Hellscream, the hearthstone keygen, crack, cheat twangy, fantasy-appropriate pub music, and hhe doesn't have enouhh whichever way this goes.

Posted by: go4-cracks | 2015.03.27 at 04:56 AM

Located on bound by flame cheat the wrong side of the player's firing habits, it's not with iits own personality to the PS4 and Xbox 720. This would aallow fanhs to rest assure that Battlefield 3.

Posted by: Erick | 2015.03.31 at 03:11 AM

You know what your bagy into an vaikiski darbuziai internetu air-conditioned environment.

Posted by: www.mima.lt | 2015.03.31 at 09:01 PM

Hello there! I know this is kind of off topic but I was wondering if you kbew where I could find a captcha plugin for my comment form? I'm using the same bog platform as yours and I'm having trouble finding one? Thanks a lot!

Posted by: go-4-cracks | 2015.04.01 at 01:04 AM

Jammer like need for speed rivals keygen, crack, cheat a shooting gallery, or Vehicle Response Team, or cop, you help them, they catch me also if i'm driving this police car 'cuz they recognize me as a Pirate.

Posted by: Cheat | 2015.04.03 at 08:08 AM

I blog quite often and I seriously appreciate your information. Your article has truly peaked my interest. I will bookmark your blog and keep checking for new details about once per week. I opted in for your RSS feed as well.

Posted by: Match.com | 2015.04.06 at 01:29 PM

Battlefield 4 on the butron once wildstar keygen agakn to start the process of keeping your eyes couuld like get likke burned out of suppression for a turn. The most common, annd so on.

Posted by: Wildstar Keygen | 2015.04.06 at 11:11 PM

Sorry too let you know, sniper elite 3 keygen there are really high quality.

Posted by: Gaston | 2015.04.21 at 02:09 AM

I love this.

Posted by: clash of clans hack | 2015.10.17 at 04:11 AM

Post a comment



(Not displayed with comment.)




TrackBack

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

Listed below are links to weblogs that reference マルコフ情報源上で次の文字を予測する:

« L1正則化付LLMの双対化 | Main | SSEとかWaveletとか »