# A Hierarchical Bayesian Language Model based on Pitman-Yor Processes (HPYLM)

2016年07月26日

## はじめに

HPYLMはPitan-Yor過程によるスムージングを行うベイズ階層n-gram言語モデルの一種です。

## スムージングとHPYLM

テキストデータが以下の3文とします。

she will sing
she will like
he will call


この時、たとえば単語列she willに続いてlikeが来る確率$P(like\mid she\ will)$は、she willで始まる文が2つあり、そのうちの1つがshe willに続いてlikeが来ているので、$1$割る$2$で$0.5$となります。

しかしhe willにlikeが続くデータはないため、$P(like\mid he\ will)=0$となります。

このようにデータに出てこないものは全て確率が$0$となってしまうのですが、スムージングと呼ばれる方法を用いると$0$ではない適切な確率を計算できるようになります。

ここでは3-gramなモデルで説明を行います。

つまり、ある単語が生成される確率は、以下のように後ろの2単語のみで決まると仮定したモデルです。

HPYLMは以下の様な文脈木を考え、単語のことを客、木のノードをレストランと呼びます。

HPYLMではこの文脈木を用いて単語の数をカウントします。

たとえばshe willという単語列の後にlikeという単語が何回来たかをカウントしたい場合、文脈木のルートからwill→sheとレストランをたどり、sheというレストランにlikeという客を追加します。

こうすることでshe willに続いてlikeが1回来たとカウントされます。

この状態では先程と同じく、he willに続いてlikeが来る回数はheのノードにlikeという客がいないため$0$となります。

そこで代理客（図の白色の客）を親のレストランに送ります。

そうするとhe willの後にlikeが続く回数は依然$0$ですが、willに続いてlikeが来る回数が$1$になります。

よって$P(like\mid he\ will)$を求めるときに、ノード$he$が持つ3-gram確率$P(like\mid he\ will)$（これは0）と、その親ノード$will$が持つ2-gram確率$P(like\mid will)$をうまく補完すれば$0$ではない値にすることが可能になります。

これがスムージングの考え方で、HPYLMではPitman-Yor過程と呼ばれる確率過程を用いて補完しています。

## 学習

HPYLMにおけるパラメータは文脈木内の代理客を含めた全ての客の配置です。

と表され、n-gram確率が$\boldsymbol\Theta$によって決まります。

### $\boldsymbol\Theta$のサンプリング

まず${\rm RemoveCustomer(\boldsymbol u,w)}$によりレストラン$\boldsymbol u$から$w$を削除します。

こうすると新たな配置$\boldsymbol\Theta^{new}$がギブスサンプリングされたことになります。

## 実装

C++での実装をGitHubに上げておきました。

ここからはHPYLMで単語2-gram言語モデルを学習させる前提で実装について説明します。

また用いる記号については論文に合わせて

• $w$
• 単語
• $\boldsymbol u$
• 単語$w$の左側にあるすべての単語列（文脈）
• $\pi(\boldsymbol u)$
• 文脈$\boldsymbol u$のオーダーを1つ下げた文脈
• $\mid\boldsymbol u\mid$
• 文脈$\boldsymbol u$に含まれる単語数
• $c_{\boldsymbol uwk}$
• レストラン$\boldsymbol u$で単語$w$を提供しているいくつかのテーブルのうち、$k$番目のテーブルにいる客数
• $c_{\boldsymbol uw\cdot}$
• レストラン$\boldsymbol u$で単語$w$を提供しているすべてのテーブルの客の総数
• $c_{\boldsymbol u\cdot\cdot}$
• レストラン$\boldsymbol u$にいる客の総数
• $t_{\boldsymbol uw}$
• レストラン$\boldsymbol u$で単語$w$を提供しているテーブルの総数
• $t_{\boldsymbol u\cdot}$
• レストラン$\boldsymbol u$のテーブルの総数
• $d_{\mid\boldsymbol u\mid}$
• Pitman-Yor過程のハイパーパラメータ
• レストランごとではなく深さごとに共通の値を使う
• $\theta_{\mid\boldsymbol u\mid}$
• Pitman-Yor過程のハイパーパラメータ
• レストランごとではなく深さごとに共通の値を使う
• $G_0(w)$
• 基底測度（単語0-gram確率）
• 語彙数の逆数をパラメータに持つ一様分布とする

とします。

たとえば文が$she\ will\ sing$で$w$が$sing$である場合、

となります。

### WordProbability($\boldsymbol u$, $w$)

となり、再帰的に文脈のオーダーを落として計算します。

### AddCustomer($\boldsymbol u$, $w$)

• $max(0, c_{\boldsymbol uwk} - d_{\mid\boldsymbol u\mid}t_{\boldsymbol uw})$に比例する確率で、$w$を提供しているすべてのテーブルの中の$k$番目のテーブルに追加
• $(\theta_{\boldsymbol u} + d_{\boldsymbol u}t_{\boldsymbol u\cdot}){\rm WordProbability}(\pi(\boldsymbol u), w)$に比例する確率で、$w$を提供する新しいテーブルを作成しそこに追加
• この時親レストラン$\pi(\boldsymbol u)$に対し${\rm AddCustomer}(\pi(\boldsymbol u), w)$
• したがって親レストランでも同様に、新たなテーブルができればさらにその親に対して${\rm AddCustomer}(\pi(\pi(\boldsymbol u)), w)$

のように確率的に客をテーブルに追加します。

### RemoveCustomer($\boldsymbol u$, $w$)

$k$番目のテーブルに客が一人もいなくなった場合はそのテーブルを削除し、親レストラン$\pi(\boldsymbol u)$に対し${\rm RemoveCustomer}(\pi(\boldsymbol u), w)$を実行します。

### ハイパーパラメータの推定

$\theta_{\mid\boldsymbol u\mid}$や$d_{\mid\boldsymbol u\mid}$は初めに適当な初期値を与えておきますが、現在の文脈木のパラメータからサンプリングにより推定します。

まず以下の3つの補助変数を定義します。

これらの補助変数を用いてベータ分布・ガンマ分布からサンプリングします。

$\sum_{\boldsymbol u:\mid u \mid=m,t_{\boldsymbol u\cdot}\geq2}$は深さ$m$であり、かつ$t_{\boldsymbol u\cdot}\geq2$となるような全てのレストランに対する総和です。

その他の$\sum$についても同様に考えます。

またガンマ分布からのサンプリングの実装には注意が必要です。

C++のgamma_distribution関数は${\rm Gamma}(k, \theta)$の方で実装されているため、この関数を用いる場合は式(5)の２つ目のパラメータ$\beta_m + \sum_{\boldsymbol u:\mid u \mid=m,t_{\boldsymbol u\cdot}\geq2}{\rm log}x_{\boldsymbol u}$の逆数をgamma_distributionの2つ目の引数とします。

## 実験

the country s leading school of the royal geological society of america , and on the site of the seat of a parcel of land to the election campaign of the union .
london borough of the series of all the fans of the camp was established in ## , ## .
theoretically supports all games , but has been an important source of the power of the old man , and moved to the island with scrooge following behind .
the white house chief of the year .
of the band had a very large contingent of the waterfall model .
to the hamlet of grangemill .
amendments entered into the microphone to the united states , but the lead and prost took the solemn vows of obedience , win souls for her contribution to american performing groups raagapella and global rhythms , to take .
, the organization has attempted to assassinate king george iii , and after a few missions to investigate alleged frauds in the future when fica contributions will be put forward the completed incidents via paper forms , computer and video games .
was done , and the role of handmaiden is also a member of the heinemann writing in the morning of his death , the bank finally failed .
the most in ## as a visiting professor at the time of the st .
their only loss for the middle school , students will attend streamwood high school was originally part of the parish church near the end of the performance was playing bass guitar in the cdp has a total area of ## .
word comes from the government and the county the population was spread out with ## .
a football club , he quotes the ancient language of economic research .
returned to france , with the truth is the head of house , the remaining ## .
with many of the 3rd class of ## , ## , she was built in a textile design shop .
, he won a scholarship to study an internal wastegate port and turbine housing .
at the age of ## , a powerful weapon that had used the water warms .
key to the world war i , he was eventually taken over by the end of the northern frontier , the regiment simply had a .
died of a part of the census2 of ## , ## households , and their shadow allies .
composed his mass in the music department at northwestern memorial hospital .
and composed what are often expressed through different means .
day was a party of canada .
is the most obvious of these , preferring a few people believed that he had risen again and the upper imbrian epoch .
final words to the second largest population of the oka bay and the rest of the u .
he were to get to the study of the original playground is still alive .
was claimed by the end of the united states to offer women training as aircraft mechanics .
city has a shallow bowl , as well .
was switched to disco and smooth jazz gained popularity .
lies just outside the reported range .
has been some attempts to get catalina to return to dancing .
is located in the film industry .
measure was enacted by the english .
also known as a ## .
were ## housing units at an average density of ## .
then orders sundown and mainframe to keep the proletarians out or to be published in ## .
named for a new version of the largest hammering man is by far the most significant influence came from that of portugal .
inhabited by the new york , new york city .
of the full moon .
members of the kingdom of naples , but the most of his whereabouts , jing ke with it .
has remained silent for almost half the legislation h .
value of a day to the ## london , and gives him a new one is the southern portion of the 19th century , in october ## , ## to ## .
course , and working at the base , a ritual on transforming oneself into a pocket of the new zealand government support her in a similar execution .
cards for the second half of the movement .
arizona feeling disenfranchised .
postmodern artist michael jackson , and orissa in ## , ## , ## and over , there were ## .
quebec city and the next five years .
constituency was created a new suit does actually turn in the greater los angeles , and for all the way .
## inmates , and the group .
can be heard at all , and was named by the river severn floods in a french winery , for the most important contribution of the world .
report also claimed sovereignty over the city has a total of ## to ## as of the liberals ran a total area of ## , ## meter long catwalk in the movie the vikings .
, an advisory role to play the game .
the methodist church and its derivatives .
song , or for the use of the north side , the state in eastern orthodox theology .
day before the first , the lower house of commons , to a form similar to the united states and the narn regime in the direction of the sixties revolution .
became a nazi soldier chained to a severe blow to the next thunderstorm , which is not expressions themselves but what people use computers and websites .
am tempted to make an impact on the new leader of the fill .
tribute , though the book was added .
until the late 1980s and early 20th century .
ones who discovered zinedine zidane .
middle school , and monte cook .
, with the city had conquered the mon capital of the canadian forces , which is often taken to the 1990s .
was promoted to the united states .
they could be less influenced by 20th century .
is endemic to north america and the liverpool philharmonic orchestra and the other regions of the area .
, who regarded mankind as being the most common license sought by the san salvador cathedral was completed in ## he has been forced out of which is said to be overrepresented statistically in virtually every society .
at the sharks and large profits associated with an e .
some secretarial or notarial capacity .
in a unique people with a set of all the dead bodies .
course , and generally melancholy reflections on human development to justify intellectual property rights in the early 1980s , the main camp and a small section of the commission for the .
was heavily involved in a bid to protect her from his children and adults are approximately ## in new york .
was the main source of the 19th century suspension bridge , the european taper is conical and widens towards the end of the american society .
was a member of the golden girdle of gaea that antiope gave to him .
junction is a member of the library , an ancient artifact .
was supposed to be a success , clear weakening of ottoman rule , the black market , and his wife at that time .
slaty antwren , myrmotherula schisticolor , is a total area of the orbits which would become synonymous with judean and if the future in a game .
moved to federal drug charges , and , in person , aphrodite really is a term used to be a successful prosecutor until others learned that he arranged for the ## census , the main language of instruction in the club at the base remained the tallest building in the 1980s and 1990s .
the ## provincial election , when he was also nominated for the masses and were joined by the tigers and it was later to be an angry mob , and ran a full member of the cayman islands have no effect on the national register of historic places .
of the united states senate in the san gabriel valley .
will be a bad thing that the financial statements to the union of families located in the atlantic coast of africa to refer to the earth is not a candidate to evaluate the remainder to withdraw .