1.The Language Modeling Problem

    現(xiàn)在拋開我們之前講的馬爾科夫模型的假設(shè)徘公，對(duì)于一門語言的定義，肯定不能簡(jiǎn)單依賴于每個(gè)單詞的前兩個(gè)單詞研叫，這是常識(shí)锤窑。比如英語中的動(dòng)詞形態(tài)就和主語有關(guān)。那么我會(huì)怎么考慮一個(gè)語言模型呢嚷炉，很可能是下面這樣一個(gè)情況：

  我們之前講的Trigram模型也可以用這樣的形式來表示：

  那么我們要用我們?cè)黾拥囊恍┒x果复，一種naive的方法就是選取一些參數(shù)來生成模型：

可以想象，這是很難駕馭的渤昌。但是我們可以用這樣的模型來理論上地表示一些例子虽抄。
而下面要講的Log-Liner Model就可以加入這些信息，并使其可操作独柑。

2.Log-linear models

 #####2.1 Define

  我們首先用對(duì)Language Model的描述來引入log-linear model迈窟，Log-linear model其實(shí)是可以引入到很多問題里面的。
 這里我先作如下定義：

 然后我們定義feature(參數(shù))忌栅，一個(gè)參數(shù)就是一個(gè)函數(shù)车酣，把x，y映射到一個(gè)具體的值

  一般來講索绪，我們?cè)O(shè)定一個(gè)參數(shù)值選擇為binary的值湖员，要么為1，要么為0
  然后假設(shè)我們有m個(gè)不同的參數(shù)瑞驱，對(duì)于一組(x,y)娘摔，我們就有一個(gè)長度為m的參數(shù)值向量：

  比如在language model中我們有這樣一系列的參數(shù)：

在實(shí)際中，這些參數(shù)的數(shù)量是非常多的唤反，為了方便凳寺，我們常常用簡(jiǎn)便的方式來表示一些類似的參數(shù)：

     其中N(u,v,w)把每一組u,v,w映射為一個(gè)不同的整數(shù)，這一組參數(shù)的數(shù)量就是不同u,v,w的數(shù)量彤侍，其實(shí)這也就是trigram model的定義肠缨，只不過我們用另一種方式表達(dá)出來而已。
  #####2.2 Result

      這樣我們就得到了一組m個(gè)參數(shù)盏阶，同時(shí)我們?cè)俣x一個(gè)長度為m的向量v晒奕，然后我們就可以把(x,y)映射為一個(gè)“score”(得分)了：

      其實(shí)就是數(shù)學(xué)中的向量的點(diǎn)乘。
   #####2.3 Further Define

    我們接下來再進(jìn)一步用log-linear model來表示我們的Language model：
    我們有一個(gè)X是input空間，Y是一個(gè)有限的詞語空間脑慧，我們使：

     這就是我們的log-linear模型下的語言模型了惠窄，注意e的指數(shù)其實(shí)就是我們上面所說的"score"
     為什么叫l(wèi)og linear 模型呢？我們對(duì)兩邊取log看一下：

     一目了然了是吧
  #####2.4 for other problem

      除了Language Model漾橙，log liner的方法還可以用到其他問題上杆融，比如說tagging problem(這個(gè)問題的描述在之前的日志有講：點(diǎn)擊打開)
      我們要做的是重新設(shè)計(jì)feature函數(shù)，以及改變一下 history的的定義(也就是上面的x)霜运，上面我們是使x=w1,w2…wi-1
      在tagging problem中我們使：

     這樣就是 tagging problem 的log linear模型了脾歇，所以說log linear可以應(yīng)用于比較廣的范圍。下面我們會(huì)詳細(xì)講 Tagging Problem中的log-linear model

3.Maximum-Likelihood Estimation for Log-liner Model

#####3.1 introduction

     下面介紹下怎么從訓(xùn)練數(shù)據(jù)中得到參數(shù)淘捡，選擇的方法叫做ML(最大似然估計(jì))
     我們有的就是一系列的x和y
     首先選擇v:

     其中L(v)為：

     它叫做似然函數(shù)藕各。
     有了似然函數(shù)，我們就可以選擇一種叫做Gradient Ascent的方法焦除，也就是求使L函數(shù)最大的v
     這個(gè)其實(shí)就是梯度上升激况，就是在L上對(duì)v求導(dǎo)，得到梯度膘魄，然后一步步用梯度趨近最大值(這其實(shí)和梯度下降是相似的乌逐，具體可以見這里的部分內(nèi)容)

     然后我們每次迭代使v加上 （β乘以這個(gè)導(dǎo)數(shù)），β是學(xué)習(xí)時(shí)選擇的參數(shù)创葡，叫做學(xué)習(xí)速率浙踢。

3.2 Regularization

      如果L只是簡(jiǎn)單地上面那種形式，算法很可能會(huì)過擬合灿渴，一些v會(huì)變成非常大來更好地增大似然函數(shù)洛波，但這種增大是畸形的，叫做overfitting
      解決的方法很多骚露，最簡(jiǎn)單的一種就是加入regularization的部分蹬挤，也就是：

      這樣的話如果v過大就會(huì)招致penalty
      那么：

########下面的課程相對(duì)細(xì)講了log linear model對(duì)于Tagging和Parse問題的方案，我選簡(jiǎn)單的寫一個(gè)=========
########其實(shí)模型都是相似的===============================================================

4棘幸、Log-Linear Models for History-based Parsing

#####4.1回顧下Log-Linear Taggers

      好吧焰扳，這段我懶了，沒有寫log linera tagger的內(nèi)容够话，所以在這補(bǔ)充總結(jié)一下蓝翰，其實(shí)也不是很復(fù)雜

      大概就是這樣的一個(gè)模型光绕，可以看出其實(shí)就是2.4的內(nèi)容女嘲。
#####4.2 History-Based Models

     有了tag以后，我們可能還會(huì)有需求去求的一個(gè)parse诞帐，也就是語法樹欣尼，一步步來。
     假設(shè)我們能夠?qū)⒁活w樹表示為一系列的decisions，假設(shè)為m個(gè)愕鼓，我們有：

     注意這里的m不一定是句子的長度钙态，我們可以做很多decision來表示句子樹的結(jié)構(gòu)
    然后我們定義：

表示這個(gè)句子
那么對(duì)于一棵樹的probability就是：

    Over------就這么簡(jiǎn)單，關(guān)鍵是我們要怎么來設(shè)計(jì)我們的decision
    注意和4.1對(duì)比一下菇晃，我們?nèi)绻裠ecision換成tag的內(nèi)容册倒，就變成了Tagger的問題
#####4.3Ratnaparkhi's Parser:

   再繼續(xù)我們的內(nèi)容之前，先放一個(gè)例子在這磺送，好繼續(xù)描述：

 下面主要講的是一個(gè)叫做Ratnaparkhi的人的model驻子，好吧，又是一個(gè)90后的model……
 他的模型主要分三層：

1. Part-of-speech tags

                    這部分就是簡(jiǎn)單的tag的model估灿，每個(gè)decision就是一個(gè)tag的選擇

2. Chunks

                 Chunks其實(shí)就是短語部分的模型：

                  也就是上面那一排tag崇呵，其正式點(diǎn)的定義就是：所有兒子都是 Part-of-speech tags的節(jié)點(diǎn)
                  如何表示它的decision呢？我們用SART和JOIN來表示

                  一目了然馅袁？再加上第一層的模型域慷，現(xiàn)在我們的decision已經(jīng)有2*n個(gè)了：

3. Remaining structure

                  Remaining structure，我們看一下這顆tree還有什么remaining了呢汗销？更高層的樹的結(jié)構(gòu)
                  我們將用Check來在第二層的基礎(chǔ)上來表示這棵樹：Check=NO 或者 YES
                  首先我們跑一次第二層犹褒，Check一直設(shè)置為NO，不增加什么操作弛针，直到：

                    我們?cè)O(shè)置Check=YES化漆，那么發(fā)生奇跡的時(shí)刻到了，看到?jīng)]钦奋，一組Start和Join消失了座云，取而代之的是一個(gè)Chunk:PP

                    我們?cè)倮^續(xù)，CHECK繼續(xù)為NO：

                看到?jīng)]付材，在選擇Check為YES的時(shí)候就把上一個(gè)start的部分合并成一個(gè)符號(hào)ｋ稀！厌衔！
               這樣繼續(xù)到最后璧帝，我們就得到了最終的decision：

#####4.4 Applying a Log-Linear Model

            其實(shí)比較簡(jiǎn)單，就是di作為輸入富寿，而<d1…di-1,S>作為history

            其中A表示所有可能的action(decision)
            那么現(xiàn)在還有一個(gè)最大的問題睬隶，怎么設(shè)計(jì)我們的 f ？Ｒ承臁苏潜！
           Ratnaparkhi的模型中主要還是關(guān)聯(lián)了decision的部分，我們同樣可以對(duì)decision進(jìn)行trigram或者bigram模型的設(shè)計(jì)变勇，這是和以前的定義一樣的恤左，然后將各部分混雜起來就會(huì)得到很多的f了贴唇。
#####4.5 Search Problem

        在POS tagging問題中我們能夠使用Viterbi algorithm的原因是我們有如下假設(shè)：

        但是現(xiàn)在的decision可能依靠之前的任意一個(gè)decision，動(dòng)態(tài)規(guī)劃是沒轍了飞袋。戳气。。巧鸭。
        這一部分會(huì)在下一周的課程講到瓶您。^_^