演算法筆記 - Language

Natural Language(Under Construction!)

Natural Language

自然語言是人類所說的語言,與制式語言相對應。

人類語言龐大複雜、人類文法缺乏規律。工程師放棄教條式的文法,改為觀察詞彙與詞彙之間的關聯,判斷最佳詞彙組合。這群人只碰計算機科學、不碰語言學,於是創造了新稱呼「自然語言處理」。

語言學旨在研究人類的文字文法、發音韻律、說話溝通、寫作翻譯、……。語言學的分支之中,語意學、語用學與自然語言有關。

使用現成工具處理自然語言

知名工具為NLTKCoreNLP繁體中文的語料庫

Text Analysis(Under Construction!)

簡介

文字的統計與分析。

Text Tokenization

分詞。英文句子,斷開成許多單字。

tokenization  英文句子去除標點符號,打散成單字
lemmatisation 英文單字的變化型,變成原型
stemming      英文單字的變化型,去除字尾
http://tartarus.org/martin/PorterStemmer/
part-of-speech tagging     英文單字標註詞類,例如名動形副介
shallow parsing / chunking 英文單字標註句型,例如主詞受詞補語
named-entity recognition   英文單字標註義類,例如人時地事物
constituent parser 得到詞類樹狀結構
dependency parser  得到句型樹狀結構
http://nlp.stanford.edu:8080/parser/

Text Tokenization

分詞。中文句子,斷開成許多詞彙。

將一句話斷開成許多詞彙 ---> 將 一句 話 斷開 成 許多 詞彙

讀者可以先玩玩看中研院的斷詞系統谷歌書籍詞彙統計

人類在對談時,大腦一瞬間綜合了聲調、文法、情境、表情、肢體動作、認知、知識,藉此正確地分詞。每個人出生的前十年,大腦不斷地發展這個能力,但是我們至今仍然不知道這個能力的詳細內容。目前計算機科學家所能掌握的,僅僅是文法而已。

一、建立「常見詞彙大全」。
  窮舉所有的詞語組合方式,找到最好的詞語組合。
  甲、greedy method:令長詞優先配對。
  乙、dynamic programming:計算出現次數總和(或機率乘積)最大的詞語組合。
  優點:計算速度飛快而且精準。
  缺點:無法處理未知詞彙。

二、n-gram,n是一個變數。此處以2-gram為例:

            2-gram
    常見詞彙何其多 ------> 常見、見詞、詞彙、彙何、何其、其多

  蒐集大量文章,統計所有2-gram的出現次數即可。就這麼簡單。
  教科書習慣表示成機率:出現次數再除以總次數。
  缺點:完全沒有參考中文文法,經常得到莫名其妙的詞彙。
  優點:採用機率模型,可以容忍人類亂無章法的句法!

三、剖析樹。
  依照文法,分解句子變成樹狀圖,並且判斷詞性。
  然而人類講話亂無章法,窮舉各種狀況的時間複雜度極高。

四、有向無環圖DAG。
  比樹狀圖還有彈性。

Text Segmentation

分段。一篇文章,自動切割出適當段落。

TextTiling algorithm

Text Prediction(Predictive Text)

預測。推測接下來的文字。

Text Correction(Spell Check)

校正。修正拼字錯誤、文法錯誤。

Text Categorization

分類。區分文章類型,有如報紙版面分類。

進階應用有情感分析防垃圾郵件

topic model:觀察每份文章的詞彙,根據詞彙們的出現次數、比重,判斷文章類型。將文章涵義以數值形式記錄下來。

Latent Semantic Analysis, LDS
vector space model + SVD
(跟eigenxxxxx不太一樣,沒有先求兩兩共變異數)

Probabilistic Latent Semantic Analysis, PLDS
document->topic->word
http://blog.csdn.net/yangliuy/article/details/8330640

LDA, Latent Dirichlet Allocation
http://cos.name/2013/01/lda-math-gamma-function/
http://cos.name/2013/01/lda-math-beta-dirichlet/

Text Compression

壓縮。減少儲存容量。

ACB Compression(Associative Coder of Buyanovsky)
http://www.stringology.org/DataCompression/acb/index_en.html
http://www.cs.brandeis.edu/~fabricio/files/cosci170.htm
PPM Compression(Prediction by Partial Matching)
http://www.stringology.org/DataCompression/ppmc/index_en.html
http://en.wikipedia.org/wiki/Prediction_by_Partial_Matching

Natural Language Understanding(Under Construction!)

簡介

https://www.zhihu.com/question/19895141/answer/401968633

Natural Language Generation

生成。自動寫作,生成文章。

http://en.wikipedia.org/wiki/SCIgen
http://en.wikipedia.org/wiki/Article_spinning
http://images3.wikia.nocookie.net/__cb20120321065110/hunterx/images/9/92/Neon%27s_Lovely_Ghostwriter.jpg
Automated Content Authorship
http://wordai.com/
http://mag.udn.com/mag/digital/storypage.jsp?f_ART_ID=131873
http://www.insead.edu/facultyresearch/faculty/profiles/pparker/
http://www.insead.edu/facultyresearch/faculty/personal/pparker/
Report Generator
http://narrativescience.com/
http://mag.udn.com/mag/digital/printpage.jsp?f_ART_ID=389334
lyrics generator
http://arxiv.org/abs/1505.04771   DopeLearning
Automatic Rhyme Detection
http://mining4meaning.com/2015/02/13/raplyzer/
Neural Storyteller
http://www.cs.toronto.edu/~mbweb/
Political Speech Generation
http://arxiv.org/abs/1601.03313

Natural Language Paraphrasing

釋義。換句話說、重新闡釋,有如查字典。

Natural Language Summarization

摘要。歸納文章重點,生成文章。

Story Understanding
http://alumni.media.mit.edu/~mueller/storyund/storyres.html

Natural Language Comprehension(Question Answering)

理解。給定一篇文章、一些提問,根據文章內容產生正確答案。

知名數據集SQuAD

Natural Language Communication(Dialog Modeling)

溝通。給定一句話,產生適當的回話。

知名軟體如Eugene Goostman、Akinator掰噗

Natural Language Translation(Machine Translation)

翻譯。一份文章,翻譯成另外一種語言。

知名軟體如Google Translate有道翻译Dr.eye

http://www.statmt.org/book/
http://mt-class.org/
http://104.131.78.120/

Natural Language Identification

鑑定。一份文章,判斷所屬語言。

Natural Language Programming

編程。靠一張嘴寫程式。