A Parallel Parsing Algorithm for Natural Language using Tree Adjoining Grammar.pptx

A Parallel Parsing Algorithm for Natural Language using Tree Adjoining Grammar

1. A Parallel Parsing Algorithm for Natural Language using Tree Adjoining Grammar Tom Nurkkala Vipin Kumar [email protected] [email protected] Department of Computer Science, University of Minnesota, Minneapolis, MN 55455

2. Outline Introduction 1 Tree Adjoining Grammar 2 Sequential Algorithm 3 3 Parallel Algorithm 4 4 Experimental Results 3 5 Future Work 4 6

3. 1.Introduction first sequential parsing algorithm for TAGs. 提出者： Vijay-Shankar and Joshi 採取方式： bottom-up 方法 時間複雜度 ： A parallel parsing algorithm for TAGs. 提出者： Palis , Shende , and Wei 缺點： 只適用於標準化的 TAG A new parsing algorithm for general TAGs. 提出者： Palis and Wei 執行時間： www.themegallery.com 其中 L 是語法和輸入字串之間一個穫得相依性的參數 。 變 化量： 到 平 均運算時間：

4. 2.Tree Adjoining Grammar 在 TAG 中有兩個種類的基本樹： ： (1) 初始樹 (2) 輔助樹 www.themegallery.com 語法節點 內部結點被標記成非終結的節點 ，而 非終端節點為大寫字母或字串 表示 外部 ( 樹葉 ) 節點可被標記成終端或非終結 ，而 終端節點為小寫字母或字串 表示

5. 基本樹由兩種操作組合： (1) substitution (2) Adjunction www.themegallery.com

6. 3.Sequential Algorithm 我們所用的語意分析演算法是基於 Palis and Wei 所提出的 Sequential Algorithm 。 兩個輸入，一個是 TAG “G” 另一個是字串 ”W” 。 演算法的行動原理是維持 index tuple ， ( i,j,k,l ) 是為 4 tuple ， ≦ i ≦ j ≦ k ≦ l ≦ n 。 www.themegallery.com

7. Example: 輸入的字串 “the boy sailed the blue yacht.” 字串被編號 ： “the blue yacht” 被 (3,4,4,6) tuple 生成。 www.themegallery.com Company Logo

8. 下 圖是基本的順序語意分析演算法。 www.themegallery.com Company Logo

9. 4.Parallel Algorithm 下 圖是 平行 語意分析演算法。 www.themegallery.com

10. 5.Experimental Results 實驗環境：一台 Ncube 2 電腦 。 實驗資料來源： Pennsylvania 大學。 實驗資料內容： 資料 包含有隨機生成 語法 和 英文語法 。 下面介紹幾個符號所代表的 意義 ： p ：處理器的數量 ； Tp ：對 p 個處理器平行處理時間 ； S ： speedup ， S=T1/ Tp ； E ： efficiency ， E=S/p 。 www.themegallery.com

11. 5.1.1 Random Grammars 表 1 表示 分析 對 1024 隨機語法基本樹 ( 平均每個樹有八個節點 ) 且 20 個的輸入字串的效能。 www.themegallery.com

12. 5.1.2 English Grammars 表 2 表示分析一個英語語法的效能。 www.themegallery.com

13. 同樣大小的隨機文法和英語文法效能比較 www.themegallery.com Company Logo

14. 5.2.1 Computation 請注意，句子長度跟文法大小比較起來更會影響工作負荷。 www.themegallery.com

15. 5.2.2 Overhead 平行演算法中主要的 overhead 來源： (1) tuple set communication (2) processor idling www.themegallery.com

16. 5.2.3 Scalability 平 行 演 算法，意味著 可以得到 更大的 平行 性和更高的 效 能。 平行演 算法是可擴展的，因為它們提供較大數量的處理器 來達到較好的結果 。 在這個演算法中，是由於兩個因素來增加工作： (1) 語法大小 (2) 句子長度 www.themegallery.com

17. 語法大小 www.themegallery.com

18. 句子長度 www.themegallery.com

19. Future Work 未來在平行 TAG 語意分析上應該考慮兩 個 方向： Dynamic Load Balancing 使用 動態負載平衡來降低效能 空閒 Earley - Style Algorithm 探討 一個 earley -style 語意分析演算法，取得比目前分析方法中還要更好平均複雜度 方法 www.themegallery.com

20. 6.1 Dynamic Load Balancing 當一個處理器空閒，它 會 跟其他處理器要求工作 ， 其他處理器 收到請求時會先去判斷是否有工作，如果有就把工作傳給空閒的處理器做。 如何達到 動態負載平衡 呢 ? 未來預估 使用一個結構化的指標 因此，今後的工作可 放在 當樹上 某 節點執行 substitution 或 adjunction 運作的 預測。 www.themegallery.com

21. 6.2 Earley - Style Algorithm Schabes 介紹一種 earley -style 語意分析演算法來分析 TGA 。 因為它使用自上而下的預測以及自下而上的分析 ，所以 具有較好 時間 複雜 度。 除此之外 Schabes and Joshi 還提出一種 LTGA ，此為 TGA 的變型 。 www.themegallery.com

22. Conclusions 在本篇論文中 我們 介紹 了 一個新 的 使用平 行 運 算 方 法解析 TAG 歸納我們的經驗與 TAG 分析 ， 平 行 演 算法將 產生 非 結構化 問題： ( 1)overhead 的 來源 不一致， 影響整個 執行 效能 ( 2 ) 複雜和意外方式相互作用 ， 影響 overhead (3 ) 因為處理器的負載不平衡，有顯著 overhead www.themegallery.com

23. Thank You !