在高人的指點之下準備開始海量讀論文，計劃本系列完成ACL,EMNLP,NAACL最近五年來的全部論文添坊。希望有所收獲圆到，啦啦啦！
1. Learning Ensembled for Structured Prediction Rules
1.1 -1st PASS
①論文類型
??嘖嘖揍拆，第一篇論文就不是熟悉的領域。這篇論文提出了新的算法茶凳，并且對老算法進行了調研和比較嫂拴。
②問題領域
??這篇論文是針對集成學習提出的新算法播揪。試圖通過新的算法，將集成學習能夠應用到新的研究潮流中筒狠。
③假設正確性討論
??該論文最重要的假設就是將一類任務統(tǒng)一看做是結構化輸出的任務猪狈，集成學習僅僅針對這個結構化的輸出結果，而和前面的模型訓練過程無關辩恼。這個假設大大的簡化了集成學習的難度雇庙。有了這個前提，統(tǒng)一的集成學習的框架將會成為可能灶伊。其實這個假設可以進行一下擴展疆前，我們知道啊，在現(xiàn)在的問題中聘萨，比如序列標注竹椒，我們高大上的訓練模型不僅僅可以給出標注的結果，甚至是可以給出標注的概率的匈挖。那么我們如果采用論文中的假設的話，就沒有辦法充分利用這一部分信息咯康愤。
??另外一個假設是輸出的整體損失是子結構的損失之和儡循。這個假設在大多數(shù)結構化輸出的任務中都是成立的。
??還有一個隱藏的假設征冷，就是我們用于集成學習的模型（專家）是各有所長的择膝。每個人對于某一個子結構的預測能力是不一樣的。這個假設就要求我們在構造這些專家的時候盡量采用不同的模型检激，模型的差距越大越好肴捉。
??還有一個小假設吧，就是每個輸出的子結構的個數(shù)都是一樣的叔收。這個呢是為了方便說明問題才做這樣的假設的齿穗，完全可以采用不等長的子結構。算法的過程是完全一樣的饺律。
④主要貢獻
??本文的基本思想是：在當今的研究潮流中窃页，預測問題的結果已經不再是原本的分類或者回歸問題了。而是更多的涉及到結構化的結果复濒，比如語音識別和序列標注等等脖卖。以序列標注為例，我們如今面臨的任務是給整個序列每個基本單元都貼上標簽巧颈。
??想象一下畦木，如果我們采用原本的集成學習的方法，把這個問題當做分類問題砸泛，那么預測空間將會非常龐大十籍。集成策略如果采用傳統(tǒng)的“投票”的方式的話蛆封，訓練5個模型，每個模型對這個序列進行一下標注妓雾，然后把標注的結果進行投票娶吞。這是沒有意義的，因為從結果來說械姻，很有可能最終每個模型都給出了不同的標注方案妒蛇，一人一票，沒有意義楷拳。但是绣夺，同時我們注意到，每個模型雖然標注的結果都不一樣欢揖，但是每個模型的標注都是有意義的陶耍，就像5個專家，說的雖然不一定一致吧她混，但是各有各的道理烈钞，所以急需一種新的算法能夠將集成學習應用到這類新問題上來，將每個“專家”的意見取其精華去其糟粕坤按。
??在這樣的背景下毯欣，這篇論文提出了新的算法，主要具有以下幾個貢獻：
????1.歸一處理臭脓。將不同的任務泛化成同樣的抽象任務酗钞，該論文在不了解任何任務背景的情況下建立起一套統(tǒng)一的集成學習框架，因此可以說是徹底的任務無關的来累。以前的隨機森林等方法砚作，都是只能針對特定的任務，或者說是特定的學習模型嘹锁，在該論文提出的方法中將不存在這種限制葫录。
????2.充分利用子結構信息的集成。正如前面提到的领猾，這篇論文充分利用了結構化的輸出中的子結構的信息压昼，即從各個專家的話中獲取有用的信息進行集成，而不是像傳統(tǒng)的方法一樣進行粗粒度的簡單集成瘤运。同時窍霞，區(qū)別貪心算法，貪心算法并沒有辦法保證整個序列的最優(yōu)性拯坟。
????3.非基于概率的但金。傳統(tǒng)的集成學習大多是基于概率的模型，而一旦基于概率郁季，該模型將會變得非常復雜冷溃。在該論文中并沒有任何和概率相關的內容钱磅。
1.2 -2nd PASS
??啊哈哈哈。似枕。盖淡。這個圖叫“線上學習”(on-line)哎。凿歼。差點被忽悠了褪迟！這個模型的大概意思呢是很簡單的。我們認為呀答憔，每個專家對不同的子結構的預測能力是不一樣的味赃，那么就各司其職唄。我們從這些專家的話中綜合出來一個path_expert.舉例來說虐拓，有五個專家心俗，有六個子結構，每個專家都對序列做了標注蓉驹，那么就會最多可以出現(xiàn)6的5次方種不同的標注方法(說是最多因為可能存在意見相同的時候)城榛，然后根據(jù)損失函數(shù)進行選擇一個就好啦。文章中還提到啦态兴，這樣的模型能夠做到綜合各個專家的意見狠持，而不是最后就是選了某一個人的意見作為判別啦。
??這個方法簡單吧诗茎。但是效率低哇工坊！怎么辦献汗？敢订？論文提出了batch方法，包括基于WMWP和基于FPL方法的兩種方案罢吃。其中前者是該論文的研究重點楚午。
??基于WMWP的方法呢也很簡單。既然不能遍歷的話就引入概率唄尿招。這就簡單啦矾柜。按照指定的概率選擇path_expert作為最終的標注序列【兔眨可以看出來啦怪蔑，這里最關鍵的就是這個概率啦。不說也知道丧荐，這個概率一定和預測的好壞程度成正比 咯缆瓣。猜的越好我們就優(yōu)先按這個來，損失越小就是猜的越好虹统。但是這樣的話效率沒有提高弓坞，這時使用了關鍵的轉換,序列的損失是單個子結構損失之和隧甚。所以我們只需要計算有限數(shù)量的單個損失，然后把每個序列的損失加出來就行了渡冻。這樣就從指數(shù)復雜度O(n2)變成了線性復雜度O(n)戚扳。
1.3 -3rd PASS
??這個算法可以說是很簡單啦,具體的思維重現(xiàn)結果如下。需要注意族吻，算法輸入是黑箱訓練模型提供的標注帽借，輸出是集成之后的序列標注。
