Машинная обработка естественных языков Петр Новиков Санкт-Петербург, 13.04.2014. - презентация

1 Машинная обработка естественных языков Петр Новиков Санкт-Петербург,

2 Why Natural Language Processing? Проблема взаимодействия человек- компьютер Проблема автоматизированной обработки неструктурированных баз знаний

3 Языки программирования Не ломимся ли мы в открытую дверь?

4 Что автор хотел сказать? То, что понятно машине, непонятно человеку, и наоборот. Для человека наиболее предпочтительно изъясняться на своем родном языке Человеческий язык неоднозначен и сильно зависит от контекста => Используем вероятностные методы!

5 Вероятностный подход. Наивный байесовский подход Задача классификации документа Предположим, что есть база знаний (корпус), из которых мы можем получить априорные вероятности nltk.download() Предположим, что имеем в распоряжении «стеммер» – средство, позволяющее извлекать основу слова from nltk import stem stem.SnowballStemmer.languages russian_stemmer = stem.SnowballStemmer('russian') print russian_stemmer.stem(u'поиска') print russian_stemmer.stem(u'строим') pymorph?

6 Вероятностный подход. Наивный байесовский метод Томас Байес (1702 – 1761)

7 Вероятностный подход. Наивный байесовский метод Как классифицировать документ? D1: Строим дерево поиска. КОМП -- Компьютерные науки D2: Строим из дерева. СТРО -- Строительство и ремонт P( КОМП | строим дерево поиска ) = > P(СТРО | строим дерево поиска) = = P( КОМП ) = P( СТРО ) * P( строим | КОМП ) * P( строим | СТРО ) * P( дерево | КОМП ) * P( дерево | СТРО ) * P( поиска | КОМП ) * P( поиска | СТРО ) / P( строим дерево поиска ) P( КОМП | строим дом из дерева ) = P( СТРО | строим дом из дерева ) = = P( КОМП ) < = P( СТРО ) * P( строим | КОМП ) * P( строим | СТРО ) * P( дом | КОМП ) * P( дом | СТРО ) * P( из | КОМП ) * P( из | СТРО ) * P( дерева | КОМП ) * P( дерева | СТРО ) / P( строим дом из дерева )

8 Вероятностный подход. Наивный байесовский метод Как классифицировать документ? D1: Строим дерево поиска. КОМП -- Компьютерные науки D2: Строим из дерева. СТРО -- Строительство и ремонт P( КОМП | строим дерево поиска ) = > P(СТРО | строим дерево поиска) = = P( КОМП ) = P( СТРО ) * P( строим | КОМП ) * P( строим | СТРО ) * P( дерево | КОМП ) * P( дерево | СТРО ) * P( поиска | КОМП ) * P( поиска | СТРО ) / P( строим дерево поиска ) P( КОМП | строим из дерева ) = P( СТРО | строим из дерева ) = = P( КОМП ) = = P( СТРО ) * P( строим | КОМП ) * P( строим | СТРО ) * P( из | КОМП ) * P( из | СТРО ) * P( дерева | КОМП ) * P( дерева | СТРО ) / P( строим из дерева )

9 Вероятностный подход. Наивный байесовский метод Как классифицировать документ? D1: Строим дерево поиска. КОМП -- Компьютерные науки D2: Строим из дерева. СТРО -- Строительство и ремонт P( КОМП | строим дерево поиска ) = > P(СТРО | строим дерево поиска) = = P( КОМП ) = P( СТРО ) * P( строим | NULL, КОМП ) * P( строим | NULL, СТРО ) * P( дерево | строим, КОМП ) * P( дерево | строим, СТРО ) * P( поиска | дерево, КОМП ) * P( поиска | дерево, СТРО ) / P( строим дерево поиска ) P( КОМП | строим из дерева ) = P( СТРО | строим из дерева ) = = P( КОМП ) < = P( СТРО ) * P( строим | NULL, КОМП ) * P( строим | СТРО ) * P( из | строим, КОМП ) * P( из | СТРО ) * P( дерева | из, КОМП ) * P( дерева | СТРО ) / P( строим из дерева )

10 Вероятностный подход. Наивный байесовский метод Как правильно перевести слово «дерево»: «arbo» или «ligno»? ARBO -- дерево (растение или структура данных) LIGNO -- дерево (строительный материал) P( ARBO | строим дерево поиска ) = = P(LIGNO | строим дерево поиска) = = P( ARBO ) = P( LIGNO ) * P( строим | ARBO ) * P( строим | LIGNO ) * P( дерево | ARBO ) * P( дерево | LIGNO ) * P( поиска | ARBO ) * P( поиска | LIGNO ) / P( строим дерево поиска ) P( ARBO | строим дом из дерева ) = P( LIGNO | строим дом из дерева ) = = P( ARBO ) < = P( СТРLIGNO ) * P( строим | ARBO ) * P( строим | LIGNO ) * P( дом | ARBO ) * P( дом | LIGNO ) * P( из | ARBO ) * P( из | LIGNO ) * P( дерева | ARBO ) * P( дерева | LIGNO ) / P( строим дом из дерева )

11 Вероятностный подход. Векторная модель документа Дан набор из n документов, в которых встречается m слов. Пусть X=[x ij ], i=1,.., m, j=1,..., n - матрица с m строк и n столбцов, у которой (i,j)-й элемент описывает вероятность встретить слово i в документе j К этой матрице можно относиться, как к матрице ковариаций Для такой ситуации разработаны статистические методы Попробовать использовать спектральное разложение? Метод главных компонент?

12 Чего не хватает «чистым» вероятностным методам Теряется информация о частях речи Никак не используется структура предложения и связи слов в предложении … (дополните)

NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize" title="Контекстно-свободная грамматика import nltk groucho_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize" class="link_thumb"> 13 Контекстно-свободная грамматика import nltk groucho_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize('I shot an elephant in my pajamas') parser = nltk.ChartParser(groucho_grammar) trees = parser.nbest_parse(sent) for tree in trees: print tree for tree in trees: tree.draw() NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) P – preposition (предлог) NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize"> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize('I shot an elephant in my pajamas') parser = nltk.ChartParser(groucho_grammar) trees = parser.nbest_parse(sent) for tree in trees: print tree for tree in trees: tree.draw() NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) P – preposition (предлог)"> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize" title="Контекстно-свободная грамматика import nltk groucho_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det N | Det N PP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' N -> 'elephant' | 'pajamas' V -> 'shot' P -> 'in' """) sent = nltk.word_tokenize">

14 Контекстно-свободная грамматика I saw an elephant in my pajamas. NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) P – preposition (предлог)

NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> '" title="Контекстно-свободная грамматика import nltk badboy_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> '" class="link_thumb"> 15 Контекстно-свободная грамматика import nltk badboy_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> 'shot' | 'made' P -> 'in' JJ -> 'bad' """) sent = nltk.word_tokenize('The bad boy made that mess') parser = nltk.ChartParser(badboy_grammar) trees = parser.nbest_parse(sent) for tree in trees: print tree for tree in trees: tree.draw() NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) P – preposition (предлог) NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> '"> NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> 'shot' | 'made' P -> 'in' JJ -> 'bad' """) sent = nltk.word_tokenize('The bad boy made that mess') parser = nltk.ChartParser(badboy_grammar) trees = parser.nbest_parse(sent) for tree in trees: print tree for tree in trees: tree.draw() NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) P – preposition (предлог)"> NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> '" title="Контекстно-свободная грамматика import nltk badboy_grammar = nltk.parse_cfg(""" S -> NP VP PP -> P NP NP -> Det NP | N | Det N PP | JJ NP | 'I' VP -> V NP | VP PP Det -> 'an' | 'my' | 'The' | 'that' N -> 'elephant' | 'pajamas' | 'boy' | 'mess' V -> '">

16 Контекстно-свободная грамматика The bad boy made that mess. NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) P – preposition (предлог)

17 Категориальная грамматика NP – noun phrase (именная группа) N – noun (существительное) S – sentence (предложение) JJ – adjective (прилагательное) V – verb (глагол) VP – verb phrase (глагольная группа) Det – determiner (определитель) Правила вывода: JJ = N/N V = (NP\S)/N P Det = N P /N

18 Еще пример import nltk sentence = """At eight o'clock on Thursday morning Arthur didn't feel very good.""" tokens = nltk.word_tokenize(sentence) tokens tagged = nltk.pos_tag(tokens) tagged[0:6] entities = nltk.chunk.ne_chunk(tagged) entities from nltk.corpus import treebank t = treebank.parsed_sents('wsj_0001.mrg')[0] t.draw()

19 Проблемы формальных грамматик Даже языки с фиксированным порядком слов (английский, французский) трудно формализуемы, не говоря о языках с произвольным порядком слов (русский, эсперанто) При построении контекстно-свободной грамматики с некоторого момента обнаруживается, что используемые абстракции перестают содержать лингвистический смысл (похоже на проблему современной физики) => В базах знаний ограничимся «легко» формализуемым подмножеством языка!

20 Formal English / Formeel Nederlands / gellish.net Left hand objectRelation typeRight hand object The Eiffel toweris located inParis The Eiffel toweris classified as atower Parisis classified as acity The Eiffel tower is located in Paris. The Eiffel tower is classified as a tower. Paris is classified as a city.

21 Formal English / Formeel Nederlands / gellish.net GELLISH ENGLISH A structured and formalized subset of natural English that is computer interpretable. Its definition includes a Formal English Dictionary-Taxonomy of concepts in which the concepts are arranged in a taxonomy hierarchy and is an ontology as far as required to define the language. The Gellish Formal English Dictionary-Taxonomy contains the following Domain Dictionaries-Taxonomies: Generic concepts and relation types (TOPini) Units of Measures, scales and currencies Activities, Events, Processes and Functions Physical objects of various kinds, such as: - Static equipment, process units and piping - Buildings, civil and structural items - Electrical and Instrumentation, Control and Valves - Rotating equipment, Transport equipment and Solids Handling - Roles of physical objects (applications) Aspects, Properties, Qualities and Roles of aspects Materials of constructions (steel and non-steel), Fluids and Waves Documents and Identification, Information, Symbols and Annotation Geographic objects, including countries Biology Organizations and Procurement Mathematics, Geometry and Shapes Waste water and water treatment

22 В реальности методы комбинируются Например, можно использовать формальные грамматики там, где это применимо, а в остальных частях «догадываться» статистически Несколько машин, работающих по разным алгоритмам, вырабатывают каждая свое решение, а затем вопрос решается «голосованием»

23 Полезные ссылки Сайт автора лекции: Natural Language ToolKit (NLTK) Parsing of Esperanto, диссертация на тему автоматизированного разбора языка эсперанто Онлайн-курсы Natural Language Processing на Coursera: (Jurafsky & Manning) (Collins) Как стать хорошим компьютерным лингвистом? linguist/ linguist/ Gellish English Wolfram Alpha