Привет Хабрахабр,
На основании результата голосования в статье Теория Графов в Игре Престолов, я перевожу обучающий материал Эрика Германи (Erik Germani), который получил социальный граф связей из 5 первых книг серии «Песнь льда и пламени», лёгший в основу вышеупомянутой статьи. Статья не содержит подробного описания методов машинного обучения, а скорее рассказывает как на практике можно использовать существующие инструменты для поиска авторов диалогов в тексте. Осторожно, много букв! Поехали.
Данный обучающий материал нацелен на новичков в машинном обучении, таких как я, когда начинал этот проект год назад. (И коим до сих пор являюсь, хотя сейчас я просто зелёный, а не ярко зелёный в этой теме.) Мы построим модель, способную определить кто говорит строку диалога в книгах Джордж Р.Р. Мартина «Песнь льда и пламени». Для этого, мы будем использовать метод условных случайных полей CRF (прим. от Conditional Random Fields) и замечательную утилиту CRFsuite от Наоаки Оказаки. Для обработки текста воспользуемся Python 2.7 и NLTK (Natural Language Toolkit).
Я хочу быть детальным с этим материалом. Надеюсь, что при описании каждого шага моих действий, вы сможете извлечь для себя новые инструменты и методы, которые будут полезны в ваших собственных проектах. Объяснения кода будут от новичка и для начинающего, того, кто понимает синтаксис Python и знает об абстракции списков, но не более того. Если вы чувствуете, что мои разъяснения кода иссушают вашу душу, пропустите их.
Важно: Если вы хотели найти тут теорию о методе условных случайных полей, то этот материал не для вас. Для меня, CRFsuite — красивый черный ящик, которого я касаюсь своими обезьяньими лапками. Мы потратим некоторое время на повышение эффективности модели, но это окажется ошибочной попыткой. Если это вас расстраивает, имейте ввиду:
- Мне удалось добиться хорошего результата (~75% точности) с CRFsuite из коробки
- Тут не будет LaTeX
Наш план игры прост. Как и с любым другим алгоритмом для машинного обучения, нам нужно подготовить данные для обучения и проверки. Потом мы выберем свойства, которые алгоритм будет использовать для классификации. После того как мы обработаем текст используя эти свойства, мы скормим результат CRFsuite и поздравим себя с хорошо проделанной работой. (либо обременим себя кропотливым трудом по проверке догадок машины).
Давайте начнём.
Загрузка текста
В первую очередь, нам надо найти копию источника текста и я оставлю выбор за вами, будете ли вы платить за него железную цену или нет.
Если вы новичок в области обработки естественного языка, то возможно недооцениваете каким непростым может оказаться исходный текст. У каждого файла .txt есть кодировка, которая определяет как будет описываться каждый символ. ASCII, формат в котором я прочитал прохождения игры Ocarina of Time, был вытеснен UTF-8, который может справиться со всеми специальными символами. (ASCII может представить 128 символов.) Моя копия ПЛИП (прим. Песнь Льда и Пламени) в UTF-8, что доставит небольшие неудобства, но на самом деле является бонусом.
Мы загрузим этот текст в NLTK чтобы легче манипулировать им. NLTK может проделать массу задач, и именно так я изучил Python, если это окажется интересным для вас, то взгляните на их отличную онлайн книгу. В наших целях использовать этот инструмент, чтобы разбить текст на токены. Это подразумевает разделение предложения на слова и знаки препинания, это часто делают в проектах по обработке естественного языка.
import nltk
nltk.word_tokenize("NLTK is ready to go.")['NLTK', 'is', 'ready', 'to', 'go', '.']
В NLTK есть предзагруженные корпуса, но нам нужно загрузить свой.
Создайте папку и вставьте туда текстовые файлы ПЛИП. Так как книги очень большие, то общедоступного текста источника будет почти 10 Мб. Не идеально для поиска и замены в тексте. Я разделил текст на книги, но настоящие профессионалы, которые собираются анализировать больше, скорее разделят ещё каждую книгу по главам и последовательно пронумеруют.
Но не будем сейчас всё усложнять! Как только в папке оказался текст, мы можем запустить следующее:
corpus = nltk.corpus.PlaintextCorpusReader(r'corpus', 'George.*.txt', encoding = 'utf-8')Здесь r указывает не обрабатывать строку. Тут это неважно, т.к. я напрямую обращаюсь к папке «corpus», но если в вашем случае у папки сложное местоположение, лучше не забывать об этом.
Второй аргумент — регулярное выражение, которое указывает NLTK брать все файлы в папке, в названиях которых присутствует «George» и с расширением ".txt".
Параметр кодировки очень важен — если кодировка текста не будет соответствовать указанной, то посыпятся ошибки.
Корпус в NLTK очень полезен, с ним можно получить информацию из текста на разных уровнях.
corpus.words("George R. R. Martin - 01 - A Game Of Thrones.txt")[-5:][u'the', u'music', u'of', u'dragons', u'.']
corpus.words()[0]u'PROLOGUE'
corpus.sents()[1][:6][u'u201c', u'We', u'should', u'start', u'back', u',u201d']
Тут мы слышим обреченного Гареда из пролога Игры Престолов и видим некоторые символы в кодировке Юникод, представленные в Python. Вы видите, что все строки Юникод начинаются с u, и содержат специальные символы. u201c это левая кавычка, u201d правая. Я упоминал что UTF-8 это скорее бонус, и вот почему. Давайте посмотрим что будет если мы откроем этот же файл без указания кодировки.
bad_corpus = nltk.corpus.PlaintextCorpusReader(r'corpus', '.*.txt')
bad_corpus.sents()[1][:9]['xe2', 'x80x9c', 'We', 'should', 'start', 'back', ',', 'xe2', 'x80x9d']
Так же как u указывает на строку в формате Юникод, x указывает на шестнадцатеричную строку, таким образом NLTK даёт нам 3 шестнадцатеричных байта — xe2, x80, x9c — и пытается разбить их. Можно видеть, что он не знает как это сделать.
Мы будем работать с параграфами, поэтому давайте взглянем на один из них:
print corpus.paras()[1][[u'u201c', u'We', u'should', u'start', u'back', u',u201d', u'Gared', u'urged', u'as', u'the', u'woods', u'began', u'to', u'grow', u'dark', u'around', u'them', u'.'], [u'u201c', u'The', u'wildlings', u'are', u'dead', u'.u201d']]
Вы можете заметить, как NLTK структурирует данные. Предложения это список токенов, а параграф список предложений. Достаточно легко!
Метки
Далее нам нужно подготовить данные для обучения, но чтобы сделать это, нужно определиться с метками, которые мы будем использовать. При парсинге текста, алгоритм знает принадлежность любого токена к лексической категории, каждый из которых имеет свою метку. JJ это прилагательное, NN — существительное, IN — предлог. Эти метки играют ключевую роль для достоверности работы нашей модели. The Penn Treebank (прим. проект по метке текста) выделяет 36 таких меток.
Какие же будут наши метки? Простейший вариант это имена персонажей. Это не сработает по нескольким причинам:
- ПЛИП содержит больше тысячи персонажей. Это слишком большой выбор для нашей бедной модели. Нам нужно отсеять как можно больше меток, чтобы правильно классифицировать полагаясь на банальную удачу.
- К персонажам обращаются по разному. Джоффри может быть как «Джоффри», так и «Джофф», «Принц» или даже просто «он».
- Если мы будем использовать имена персонажей в качестве меток, то они должны быть определены в обучающих данных. Иначе, наша модель не будет в курсе о их существовании и поэтому никак не сможет их определить.
- Все персонажи звучат просто напросто одинаково. (Я это понял благодаря другому опыту с машинном обучением, где я пытался разделить персонажей по их словарному запасу). У некоторых есть броские фразы, такие как «прискорбно» (прим. grievous) для Вариса и «Ходор» для Ходора, но это редкость. К тому же, для многих отведено недостаточно времени для разговоров, чтобы различить их от остальных.
Хоть и определение по именам персонажей звучит весьма заманчиво, давайте отбросим эту идею и подумаем над процессом, который происходит в голове у читателя при решении аналогичной задачи.
Возьмите ближайшую к вам книгу, откройте случайную страницу, и попробуйте определить кто там разговаривает. Как вы это сделаете? Вы посмотрите на ближайшие собственные имена рядом с диалогом.
«Уилл видел их» отвечал Гаред.
[...]
Сир Уэймар Ройс поглядел на небо без всякого интереса. «Ночь каждый день приходит примерно в это же время. Неужели тьма лишает тебя мужества, Гаред?»
Хотя не каждая строка диалога бывает помечена. Посмотрите дальше и увидите:
«А ты заметил положение тел?»
Вы взглянете на параграфы сверху и снизу. Вот 2 сверху:
«А оружие?»
«Несколько мечей и луков. У одного был топор, тяжелый такой, с двумя лезвиями… жестокое железо. Он лежал на земле возле этого человека, прямо у руки.»
Ни капли намёка. Два параграфа ниже:
Уилл пожал плечами. «Один сидел возле скалы. Остальные были на земле, попадали, что ли.»
«Или спали,» предположил Ройс.
Мы знаем что Уилл не стал бы спрашивать самого себя, поэтому мы можем сказать что он не автор этой речи, и так как многие диалоги растягиваются на несколько параграфов, мы предположим что автор первых строк Ройс.
Эта схема и поможет помечать нашей модели. Мы научим её определять собственные имена рядом с текстом и если таких не найдётся, искать в близлежащих параграфах. Тогда, нашими метками будут:
PS ±2, FN ±2, NN ±2, Другие.
PS — после говорящий. Если метка параграфа PS -2, то это будет означать что имя, говорящего часть диалога, располагается двумя параграфами выше. Если FN 1, то первое имя в следующем параграфе. NN 0 обозначает как минимум 2 имени предшествуют диалогу и нам нужен ближайший к диалогу.
Я так же буду определять и ADR ±2, для персонажей, к которым обращаются в тексте диалога.
Пометка
Теперь мы подготовим обучающие данные. Поможет нам в этом SublimeText. Я открыл текст «Игра Престолов», выделил левую кавычку, выбрал Find -> Quick Find All, и дважды нажал клавишу Home. Теперь курсор оказался возле начала каждого параграфа с диалогом. Дальше я набрал "{}". Т.к. в тексте нет фигурных скобок, то мы можем использовать их чтобы оставлять заметки, которые будем использовать в будущем.
Мы будем использовать регулярное выражение (?<={)(?=}) чтобы прыгать по фигурным скобкам. Если вы не встречались с данной конструкцией, то они называются положительные ретроспективные и опережающие проверки. Первое выражение в скобках заставит SublimeText начать выделять строки, у которых в начале стоит открывающая фигурная скобка (экранированная обратным слэшем). Следущее выражение скажет остановиться когда найдется закрывающая фигурная скобка. Как вы могли заметить оба выражения состоят из конструкции ?=, только первая содержит еще и <.
Теперь вы можете переходить по скобкам нажимая на F3, что является горячей клавишей для поиска следующего в SublimeText под Windows. Такого рода оптимизация важна, т.к. вы будете помечать приблизительно тысячи диалогов. Как минимум столько сделал я. Это не было столь тяжело и время затратно как я предполагал. (Хотя возможно я вру, т.к. я закончил спустя лишь год).
Прежде чем вы приступите, хочу сделать одно замечание: подумайте над тем, хотите ли вы использовать позиционные метки (PS, FN, NN) или все же имена персонажей. Я знаю, что уже сказал что не будем использовать имена, но если вы решились использовать позиционные метки то вы связываете эти обучающие данные с соответствующей моделью. Если вы пометите диалоги Джона меткой «Jon», то в будущем у вас будет возможность поменять метку на позиционную, либо же использовать другие метки, если найдёт лучше.
Я думаю, что тут нет однозначного ответа. В прошлом году я помечал именами персонажей. Теперь же мне необходимо совершать предварительные манипуляции, которые добавляют неоднозначности. Если имя Эддарда появляется 2 параграфа выше и один параграф ниже, то какой выбрать? Это напрямую затронет поведение модели и совершая это автоматически делает процесс еще больше неточным. Поэтому я не уверен что посоветовать. Мне кажется, что с точки зрения ручной метки, легче написать имя персонажа, но, с точки зрения автоматизации, намного удобнее иметь позиционные метки.
Извлечение свойств
Ну что ж, вы пометили часть текста. Я аплодирую вам за приверженность делу обработки естественного языка. Всё что нам нужно сделать теперь, это написать несколько функций, которые будут принимать параграф в качестве аргумента и помечать их свойствами, которые нам интересны.
Напомни, какие свойства? Рабочими лошадками, ответственными за точность модели являются следующие функции: существуют ли в текущем, либо в соседних параграфах PS, FN или NN.
Поиск имён
Наша первая функция должна находить имена собственные. Это можно сделать с помощью определения частей речи.
sentence = corpus.paras()[33][0]
print " ".join(sentence)
print nltk.pos_tag(sentence)" Such eloquence , Gared ," Ser Waymar observed . [(u'u201c', 'NN'), (u'Such', 'JJ'), (u'eloquence', 'NN'), (u',', ','), (u'Gared', 'NNP'), (u',u201d', 'NNP'), (u'Ser', 'NNP'), (u'Waymar', 'NNP'), (u'observed', 'VBD'), (u'.', '.')]
NPP возле Ser и Waymar означает что это имена собственные. Но тут есть и минусы:
- Случаются ошибки. Заметили как закрывающая кавычка стала именем собственным?
- Определение частей речи занимает время.
%timeit nltk.pos_tag(sentence)100 loops, best of 3: 8.93 ms per loop
asoiaf_sentence_count = 143669
( asoiaf_sentence_count * 19.2 ) / 1000 / 6045.974079999999994
В ПЛИП много параграфов для обработки и 45 с лишним минут для определения частей речи затянет процесс тестирования и рефакторинга. Конечно, можно было бы один раз всё проанализировать и дальше работать с тем, что получилось. Но для этого пришлось бы иметь дело с ещё одной структурой данных и такое определение пришлось бы переделывать каждый раз когда исходный текст меняется. (И это неизбежно.)
К счастью, не обязательно связываться с частями речи для определения имён персонажей. Это одно из преимуществ выбора ПЛИП для анализа: существуют тонны данных которые уже получены. Давайте наскребём некоторые из них.
Существующая информация
Тут оказалась очень полезной Wiki Песни Льда и Пламени, я получил практически исчерпывающий список имён персонажей буквально скопировав страницу со списком героев. Результат можно найти тут. Если этого для вас достаточно, то встретимся в следующей главе статьи. Для тех, кому интересно как можно автоматически извлечь данные со страницы, я приведу пару способов которыми я пользовался в других проектах.
Wget
Отличная утилита которая очень проста, если вам нужно пройтись по заранее известным ссылкам. Не придётся думать как обходить ссылки, нужно лишь создать файл со списком и передать его используя флаг -i, вот так:
wget -i list_of_links.txtRequests
В Python есть библиотека requests, которая хорошо подходит для работы с отдельными страницами.
import requests
r = requests.get("http://awoiaf.westeros.org/index.php/List_of_characters")
html = r.text
print html[:100]<!DOCTYPE html> <html lang="en" dir="ltr" class="client-nojs"> <head> <meta charset="UTF-8"/> <title
Парсинг
После скачивания html, нам нужно отшелушить страницу от лишних тегов, чтобы добраться до ссылок. BeautifulSoup это HTML парсер, который позволит без лишней суеты получить ссылки. После установки и парсинга, найти все ссылки можно просто запустив:
parsed_html.find_all("a")Тут можно почитать об этом больше.
Мне хочется рассказать еще об одном способе, в котором используется библиотека lxml. С помощью этой библиотеки можно работать с Xpath. Я новичок в Xpath, но это мощный способ двигаться по древовидной структуре.
import lxml.html
tree = lxml.html.fromstring(html)
character_names = tree.xpath("//ul/li/a[1]/@title")
print character_names[:5]['Abelar Hightower', 'Addam', 'Addam Frey', 'Addam Marbrand', 'Addam Osgrey']
Если вы косо посмотрели на выражение Xpath сверху, то вот что оно делает:
tree.xpath("//ul # выбирает все не нумерованные списки
/li # выделяет элементы списков
/a[1] # выделяет первую ссылку в элементе.
/@title # возвращает атрибут title
")Теперь, нужно выделить среди результата имена и удалить то, что к имени никакого отношения не имеет. Просто пробежавшись по странице ПЛИП, я заметил элементы вида «Taena of Myr». Мы ведь не хотим чтобы наша модель сопоставляла диалогам частицу «of».
NLTK поможет в этом. В нём есть корпус текста с «плохими» словами — stopwords. Такими, которые встречаются настолько часто, что не несут никакого смысла для характеристики текста.
particles = ' '.join(character_names).split(" ")
print len(set(particles))
stopwords = nltk.corpus.stopwords.words('english')
print stopwords[:5]
particles = set(particles) - set(stopwords)
print len(particles)
# Кое что всё же проскользнёт. Т.к. Aegon I в списке ПЛИП, то римская
# цифра I будет восприниматься как имя. Нужно почистить это вручную.
"I" in particles2167 ['i', 'me', 'my', 'myself', 'we'] 2146 True
И в конце нужно добавить еще некоторые, возможно, упущенные прозвища, такие как Дени, Чёрная Рыба или Джофф. Если вы довольны списком имён, то сохраните его в файле для дальнейшего использования.
Поиск имён. Часть 2
Мы отказались от идеи поиска имён используя части речи и обзавелись списком имён. Мы извлечём последовательности токенов и посмотрим сможем ли найти их в нашем списке имён. Наконец настало время написать код.
import itertools
from operator import itemgetter
particles = [particle.rstrip('n') for particle in open('asoiaf_name_particles.txt')]
tokens = [u'u201c', u'Such', u'eloquence', u',', u'Gared', u',u201d', u'Ser', u'Waymar', u'observed', u'.']
def roll_call(tokens, particles):
speakers = {}
particle_indices = [i for (i, w) in enumerate(tokens) if w in particles]
for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x):
index_run = map(itemgetter(1), g)
speaker_name = ' '.join(tokens[i] for i in index_run)
speakers[min(index_run)] = speaker_name
return speakersЭта функция использует лямбда-выражение, которыми я не мог пользоваться в прошлом году, когда сделал этот проект. Скрипт, который я использовал тогда, настолько ужасен и не читаем что я не решился его публиковать. К тому же, я думаю, что в этом скрипте новички могут научиться чему нибудь новому, поэтому чуть подробнее об этом.
Itertools — инструмент, заслуживающий внимания. Я часто использую его чтобы избавиться от вложенности или для перестановок. В нём нам нужна функция groupby. По причине выхода новой версии этой функции к моменту написания материала, я полностью предпочёл groupby, нежели dropwhile и takewhile, которые я использовал в рекурсивной манере.
При программировании, я подумал, что функция roll_call должна знать позиции имён, которые он нашёл. Поэтому я решил хранить все порядковые номера имён. Это можно заметить в 3-й строке кода функции.
particle_indices = [i for (i, w) in enumerate(tokens) if w in particles]Enumerate очень помог мне при знакомстве с Python. Он принимает список и для каждого элемента возвращает связку порядкового номера и самого элемента.
4-я строка самая хитрая часть кода во всём материале и не я его писал. Она взята прямо из документации к библиотеке.
for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x):Groupby проходит через список и группирует элементы в зависимости от результата лямбда функции. Лямбды — анонимные функции. В отличии от roll_call их не нужно заранее определять. Это лишь часть кода, которая принимает аргументы и возвращает значение. В нашем случае она просто вычитает из порядкового номер число.
Давайте взглянем как это работает.
print tokens
particle_indices = [i for (i, w) in enumerate(tokens) if w in particles]
print particle_indices
for index, location in enumerate(particle_indices):
lambda_function = index-location
print "{} - {} = {}".format(index, location, lambda_function)[u'u201c', u'Such', u'eloquence', u',', u'Gared', u',u201d', u'Ser', u'Waymar', u'observed', u'.'] [4, 6, 7] 0 - 4 = -4 1 - 6 = -5 2 - 7 = -5
В этом и заключается уловка с groupby: индексы пронумерованы последовательно, поэтому если элементы в списке так же идут друг за другом, то результат лямбды будет для них одинаков.
groupby видит -4 и присваивает значение 4 для группы. 6 и 7-й элементы оба имеют -5 и соответственно группируются.
Теперь мы знаем где находятся составные имена и должны использовать их. Что возвращает groupby? Ключ, результат нашей лямбды, и саму группу, объект grouper. Далее воспользуемся функцией map чтобы применить itemgetter(1), извлекающий из связки элемент, ко всем элементам группы и таким образом мы создадим список из позиций имён в исходном списке токенов.
После groupby нам нужно всего лишь извлечь найденные имена и сохранить их в ассоциативном массиве speakers.
roll_call(tokens, particles){4: u'Gared', 6: u'Ser Waymar'}
Оптимизация
Давайте сравним скорость работы этой функции с методом, в котором мы использовали части речи.
%timeit roll_call(tokens, particles)100 loops, best of 3: 3.85 ms per loop
Не плохо, в 5-6 раз быстрее. Но мы можем улучшить результат использовав set. Множества set почти мгновенно проверяют находится ли элемент в списке.
set_of_particles = set(particle.rstrip('n') for particle in open('asoiaf_name_particles.txt'))
%timeit roll_call(tokens, set_of_particles)10000 loops, best of 3: 22.6 µs per loop
Вы понимаете что хороши, когда видите в скорости греческие буквы.
Поиск имён касательно диалогов
Теперь нам надо написать программку, которая будет вызывать вышеописанную функцию в нужных местах, так, чтобы найти имена персонажей перед, в и после текста диалогов. Мы соберём всё это в класс, который сможет собрать нам полный список позиций имён персонажей, который мы дальше передадим другому алгоритму для извлечения свойств и потом уже в CRFsuite.
Но прежде, я бы хотел привести в порядок наши данные.
XML парсер
После успешной одно-строчной команды с Xpath, я решил написать XML парсер для наших текстовых файлов. В выборе этого формата есть тонна смысла. ПЛИП это множество книг, в которых есть главы, которые в свою очередь состоят из параграфов, и некоторые из них содержат диалоги — и нам нужно незаметно их пометить. Если бы я не перевёл текст в XML (и сначала я этого не сделал), то метки бы замусорили сам текст.
Я предпочту умолчать о скрипте ниже: он напоминает мне мои первые шаги в Python, огромные функции, костыли и переменные с длиннющими наименованиями.
from lxml import etree
import codecs
import re
def ASOIAFtoXML(input):
# Каждый элемент input должен быть ассоциативным массивом названий глав с расположением его на диске.
root = etree.Element("root")
for item in input:
title = item["title"]
current_book = etree.Element("book", title=item["title"])
root.append(current_book)
with codecs.open(item["contents"], "r", encoding="utf-8") as book_file:
#Ловушка для глав, названия которых не распознаются регулярным выражением.
current_chapter = etree.Element("chapter", title="Debug")
for paragraph in book_file:
paragraph = paragraph.strip()
if paragraph != "":
title_match = re.match("A[A-ZW ]+Z", paragraph)
if title_match:
current_chapter = etree.Element("chapter", title=title_match.group())
current_book.append(current_chapter)
else:
current_graf = etree.SubElement(current_chapter, "paragraph")
while paragraph != "":
current_dialogue = current_graf.xpath('./dialogue[last()]')
speaker_match = re.search("({(.*?)} )", paragraph)
if speaker_match:
speaker_tag = speaker_match.group(1)
speaker_name = speaker_match.group(2)
paragraph = paragraph.replace(speaker_tag, "")
open_quote = paragraph.find(u"u201c")
if open_quote == -1:
if current_dialogue:
current_dialogue[0].tail = paragraph
else:
current_graf.text = paragraph
paragraph = ""
elif open_quote == 0:
current_dialogue = etree.SubElement(current_graf, "dialogue")
if speaker_name:
current_dialogue.attrib["speaker"] = speaker_name
close_quote = paragraph.find(u"u201d") + 1
if close_quote == 0:
# функция find возвращает -1 в данном случае, поэтому сравнивая с 0
# мы определяем нет ли там больше закрывающей кавычки. Это происходит
# в длинных монологах разбитых по параграфам.
close_quote = len(paragraph)
current_dialogue.text = paragraph[open_quote: close_quote]
paragraph = paragraph[close_quote:]
else:
if current_dialogue:
current_dialogue[0].tail = paragraph[:open_quote]
else:
current_graf.text = paragraph[:open_quote]
paragraph = paragraph[open_quote:]
return root
tree = ASOIAFtoXML([{"title": "AGOT", "contents": "corpus/train_asoiaf_tagged.txt"}])
# Так мы сохраняем дерево в файл.
# et = etree.ElementTree(tree)
# et.write(codecs.open("asoiaf.xml", "w", encoding="utf-8"), pretty_print=True)Суть кода выше: мы используем lxml чтобы создать дерево, потом построчно пробегаемся по тексту. Если строка распознаётся как имя главы (заглавные буквы, пунктуация и пробелы), мы добавляем новую главу в вершину текущей книги. Как только мы оказались в тексте главы, мы пробираемся сквозь параграфы, используя другое регулярное выражение чтобы определить кто говорил диалог и добавить его в соответствующую вершину диалога. Предварительно они должны быть уже помечены, конечно же.
Интересное замечание по XML. Это иерархическая структура, поэтому она по своей природе требует строгого ветвления, вершина в вершине. Но это не так в прозе. В прозе диалоги находятся внутри текста. lxml предоставляет решение: text и tail. Таким образом вершина XML хранит текст, но этот текст прерывается после очередного добавления вершины.
markup = '''<paragraph>Worse and worse, Catelyn thought in despair. My brother is a fool.
Unbidden, unwanted, tears filled her eyes. <dialogue speaker="Catelyn Stark">
“If this was an escape,”</dialogue> she said softly,
<dialogue speaker="Catelyn Stark">“and not an exchange of hostages, why should the Lannisters
give my daughters to Brienne?”</dialogue></paragraph>'''
graf = lxml.etree.fromstring(markup)
print graf.textWorse and worse, Catelyn thought in despair. My brother is a fool. Unbidden, unwanted, tears filled her eyes.
print graf[0].text"If this was an escape,"
Что же произойдёт с оставшимся «she said softly»? Мы сохраним в его в переменной вершины tail.
print graf[0].tailshe said softly,
И так далее, добавляя к каждой вершине диалога оставшуюся часть текста.
Как следствие, это сильно упрощает нам поиск авторов диалогов, когда они нам понадобятся. А понадобятся они нам прямо сейчас!
class feature_extractor_simple:
"""Analyze dialogue features of a paragraph. Paragraph should be an lxml node."""
def __init__(self, paragraph_node, particles, tag_distance=0):
self.paragraph = paragraph_node
self.particles = set(particles)
self.tag_distance = tag_distance
self.raw = ''.join(t for t in self.paragraph.itertext())
self.tokens = self.tokenize(self.raw)
def tokenize(self, string):
return nltk.wordpunct_tokenize(string)
def find_speakers(self, tokens):
speakers = {}
particle_indices = [i for (i, w) in enumerate(tokens) if w in self.particles]
for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x):
index_run = map(itemgetter(1), g)
speaker_name = ' '.join(tokens[i] for i in index_run)
speakers[min(index_run)] = speaker_name
return speakers
def pre_speak(self, prior_tag="FN", near_tag="NN"):
# Имена до диалога.
features = {}
if self.paragraph.text is not None:
speakers = self.find_speakers(self.tokenize(self.paragraph.text))
if len(speakers) > 0:
features.update({"{} {}".format(prior_tag,self.tag_distance): speakers.values()[0]})
if len(speakers) > 1:
features.update({"{} {}".format(near_tag,self.tag_distance): speakers[max(speakers.keys())]})
return features
def dur_speak(self, tag="ADR"):
# Имена адресатов.
features = {}
for dialogue in self.paragraph.itertext("dialogue", with_tail=False):
tokens = self.tokenize(dialogue)
named = self.find_speakers(tokens)
addressed = {k: v for (k, v) in named.items() if tokens[k-1] == "," or tokens[k + 1 + v.count(" ")].startswith(",")}
if len(addressed) > 0:
features.update({"{} {}".format(tag, self.tag_distance): addressed[max(addressed.keys())]})
return features
def post_speak(self, tag="PS"):
features = {}
# Имена после диалогов.
tails = [line.tail for line in self.paragraph.iterfind("dialogue") if line.tail is not None]
for tail in tails:
tokens = self.tokenize(tail)
speakers = {k: v for (k, v) in self.find_speakers(tokens).items() if k <= 1}
if len(speakers) > 0:
features.update({"{} {}".format(tag, self.tag_distance): speakers[min(speakers.keys())]})
break
return featuresПару слов об этих функциях.
Если вы новичок в Python, то не бойтесь классов. Вам просто напросто нужно написать обычные функции, передавая им в качестве аргумента self. Это позволит Python знать с каким объектом функция в данный момент работает. Класс это как фабрика клонов, а объект и есть клон. У всех клонов одинаковый ДНК, это методы и переменные, но из за их жизненного опыта их личности различаются, чем в данном контексте являются переданные им данные.
У классов есть также специальная функция __init__, которая позволяет инициализировать переменные объекта.
Теперь вы можете расслабиться, т.к. ваши данные находятся в руках специализированного класса. И раз вы абстрагировали его поведение, то вы можете по щелчку пальца получить обработанную им информацию.
paragraph = tree.xpath(".//paragraph")[32]
example_extractor = feature_extractor_simple(paragraph, particles)
print example_extractor.raw
print example_extractor.pre_speak()
print example_extractor.dur_speak()
print example_extractor.post_speak()"Such eloquence, Gared," Ser Waymar observed. "I never suspected you had it in you."
{}
{'ADR 0': u'Gared'}
{'PS 0': 'Ser Waymar'}
Если вы смущены работой некоторых функций, я коротко объясню что они делают. Если же всё сверху выглядит для вас приемлемо, то вы знаете что делать, до встречи в следующей главе.
Тут происходит неуклюжая манипуляция с ассоциативным массивом, и это потому, что они не упорядочены в Python. Мне это напоминает чувство, когда выходя из дома вы чувствуете, что в кармане нет ключей, запирая дверь. Мне приходилось постоянно проверять, получаем ли мы первого или последнего персонажа, в зависимости от случая, я смотрю на значение ключей и выбираю минимум/максимум.
pre_speak
Как я уже говорил выше, атрибут text содержит весь текст до первой строки диалога. Нам просто нужно найти в нём имена персонажей.
dur_speak
В случае когда имя находится в теле диалога, который может состоять из множества строк, нам нужно пробежаться по им всем:
for dialogue in self.paragraph.itertext("dialogue", with_tail=False)Функция itertext в lxml позволяет получить весь текст вершины. Мы, так же, поставим флаг with_tail=False чтобы искать только вершины без «хвоста», а значит только текст диалога.
Как только мы найдём имена персонажей, нам нужно выделить в них только те, которые обособлены запятой, что позволит нам найти обращение. (например, «Нед, обещай мне.» / «Обещай мне, Нед.»)
Я нутром чувствую, что последнее имя, найденное в диалоге, с большой вероятностью ответит в следующем параграфе, поэтому мы будем перезаписывать адресата последним упомянутым именем.
post_speak
Для этой функции нам нужен только первый персонаж после диалога. Поэтому мы прерываем цикл как только нашли такого.
Функция смотрит в первые 2 токена после закрывающей кавычки. Так вы найдёте диалоги типа:
«Прощай,» сказал Джон.
Совет для начинающих программистов: можно вызывать функцию выборки при постройке списка.
tails = [line.tail for line in self.paragraph.iterfind("dialogue") if line.tail is not None]Это позволило получить диалоги одной строкой. (нужно просто указать условие, чтобы убрать все результаты без «хвоста»)
CRFsuite
Возможно, это самая любопытная часть для вас. В нём заключены условно случайные поля, что бы они не значили, и запускается с командной строки, но никак не посмотреть как он работает изнутри.
Но по факту, CRFsuite очень простая и интересная часть всего этого. Во время написания материала, я обнаружил, что у него есть библиотека для Python, но сейчас мы не будем всё усложнять и будем пользоваться исполняемым файлом с помощью командной строки.
(я планирую обновить модель, когда следующая книга, «Ветра зимы», увидит свет. Но у меня ведь есть еще пару лет пока это случится)
Всё, что нужно CRFsuite это текст с некоторыми свойствами разделенными табуляцией, как эти например:
FN 0 Graf Sent Len=4 FN 1=True FN -2=True FN 0=True NN 1=True
Это формат для обучающих данных. Первый атрибут это правильный ответ. Все последующие это свойства. Они могут выглядеть как вам захочется, но не используйте двоеточие — это для взвешенных свойств, и поэтому может привести к ложной интерпретации.
Вам нужно открыть командную строку где бы crfsuite.exe не находился и там набрать следующее:
crfsuite learn -m asoiaf.model train.txtЭто создаст модель, что и является всего. Можете назвать её как угодно, я назвал свою asoiaf. Чтобы посмотреть на точность работы модели, наберите это:
crfsuite tag -qt -m asoiaf.model test.txtЧтобы собственно запустить модель для пометки наберите
crfsuite tag -m asoiaf.model untagged.txt
untagged.txt должен выглядеть так же как и train.txt, но без атрибута правильного ответа в начале, т.е. приблизительно так:
NN -1=True FN 0=True FN 2=True FN -1=True NN 0=True
Тут можно узнать про это больше.
Давайте теперь поиграемся со множеством свойств, которые могут повысить точность работы модели. Мы начнём с самого простого: с булевых значений, которые определяют расположение позиционных меток в и возле параграфа.
И снова наш класс для извлечения свойств, только теперь с несколькими новыми функциями в начале.
class feature_extractor:
"""Analyze dialogue features of a paragraph. Paragraph should be an lxml node."""
def __init__(self, paragraph_node, particles, tag_distance=0):
self.paragraph = paragraph_node
self.particles = set(particles)
self.tag_distance = tag_distance
self.raw = ''.join(t for t in self.paragraph.itertext())
self.tokens = self.tokenize(self.raw)
self.speaker = self.xpath_find_speaker()
def features(self):
features = {}
features.update(self.pre_speak())
features.update(self.dur_speak())
features.update(self.post_speak())
return features
def local_features(self):
#Разнообразные свойства живут в этой функции как в комуналке
features = []
if self.tokens.count(u"u201c") == 0:
features.append("NoQuotes=True")
prior = self.paragraph.getprevious()
try:
last_dialogue = list(prior.itertext("dialogue", with_tail=False))[-1].lower()
hits = [w for w in ['who', 'you', 'name', '?'] if w in last_dialogue]
if len(hits) > 2:
features.append("Who Are You?=True:10.0")
except (AttributeError, IndexError):
pass
try:
dialogue = list(self.paragraph.itertext("dialogue", with_tail=False))[0].lower()
for token in ['name', 'i am', u'iu2019m']:
if token in dialogue:
features.append("My Name=True:10.0")
break
except (AttributeError, IndexError):
pass
if self.tokens[0] in self.particles:
features.append("FirstSpeakerIndex0=True")
if self.paragraph.text is not None:
name_precount = len(self.find_speakers(self.tokenize(self.paragraph.text)))
if name_precount > 2:
features.append("Many Names Before=True")
conjunctions = set([w.lower() for w in self.tokenize(self.paragraph.text)]).intersection(set(['and', 'but', 'while', 'then']))
if len(conjunctions) > 0 and self.paragraph.find("dialogue") is not None:
features.append("Conjunction in Head=True")
short_threshold = 10
if len(self.tokens) <= short_threshold:
features.append("Short Graf=True")
dialogue_length = sum(map(len, self.paragraph.xpath(".//dialogue/text()")))
dialogue_ratio = dialogue_length / len(self.raw)
if dialogue_ratio == 1:
features.append("All Talk=True")
elif dialogue_ratio >= 0.7:
features.append("Mostly Talk=True")
elif dialogue_ratio < 0.3 and not self.tokens < short_threshold:
features.append("Little Talk=True")
return features
def feature_booleans(self):
bool_features = []
for tag in ["PS", "FN", "NN", "ADR", ]:
label = "{} {}".format(tag, self.tag_distance)
if label in self.features().keys():
bool_features.append("{}=True".format(label))
else:
bool_features.append("{}=False".format(label))
return bool_features
def tokenize(self, string):
return nltk.wordpunct_tokenize(string)
def find_speakers(self, tokens):
speakers = {}
particle_indices = [i for (i, w) in enumerate(tokens) if w in self.particles]
for k, g in itertools.groupby(enumerate(particle_indices), lambda (i,x): i-x):
index_run = map(itemgetter(1), g)
speaker_name = ' '.join(tokens[i] for i in index_run)
speakers[min(index_run)] = speaker_name
return speakers
def xpath_find_speaker(self):
speakers = self.paragraph.xpath(".//@speaker")
if speakers == []:
return "NULL"
else:
return speakers[0]
def pre_speak(self, prior_tag="FN", near_tag="NN"):
# Имена перед диалогом
features = {}
if self.paragraph.text is not None:
speakers = self.find_speakers(self.tokenize(self.paragraph.text))
if len(speakers) > 0:
features.update({"{} {}".format(prior_tag,self.tag_distance): speakers.values()[0]})
if len(speakers) > 1:
features.update({"{} {}".format(near_tag,self.tag_distance): speakers[max(speakers.keys())]})
return features
def dur_speak(self, tag="ADR"):
# Адресаты в диалоге
features = {}
for dialogue in self.paragraph.itertext("dialogue", with_tail=False):
tokens = self.tokenize(dialogue)
named = self.find_speakers(tokens)
addressed = {k: v for (k, v) in named.items() if tokens[k-1] == "," or tokens[k + 1 + v.count(" ")].startswith(",")}
if len(addressed) > 0:
features.update({"{} {}".format(tag, self.tag_distance): addressed[max(addressed.keys())]})
return features
def post_speak(self, tag="PS"):
features = {}
# Имена поле диалога
tails = [line.tail for line in self.paragraph.iterfind("dialogue") if line.tail is not None]
for tail in tails:
tokens = self.tokenize(tail)
speakers = {k: v for (k, v) in self.find_speakers(tokens).items() if k <= 1}
if len(speakers) > 0:
features.update({"{} {}".format(tag, self.tag_distance): speakers[min(speakers.keys())]})
break
return features
paragraph = tree.xpath(".//paragraph")[-1]
example_extractor = feature_extractor(paragraph, particles)
print example_extractor.raw
print example_extractor.features()
print example_extractor.local_features()
print example_extractor.feature_booleans()And in their hands, the daggers.
{}
['NoQuotes=True', 'Short Graf=True', 'Little Talk=True']
['PS 0=False', 'FN 0=False', 'NN 0=False', 'ADR 0=False']
Прошлой ночью, во время недокументированного безумия с машинным обучением, я пытался улучшить множества свойств. Ниже некоторые наброски, допустимые к публикации.
Вариант 1: только Истинные позиционные булевы значения
Label Count Recall PS 0 207 0.9949 FN 0 185 0.95 NULL 118 0.3492 OTHER 56 0.3939 PS - 2 44 0.5238 Item accuracy: 430 / 678 (0.6342)
Далее мы будем встречать много подобной статистики, и поэтому давайте сразу определим, что они означают.
Представим что мы находимся на обеде, смотрим на людей. Я попросил вас определить, является ли случайный прохожий иллюминатом. Вы, как человек полностью верящий в теории заговора, доедаете пельмени и начинаете помечать прохожих.
Аккуратность (прим. Precision), величина которая не будет тут рассматриваться, показывает частоту ошибок первого рода. Другими словами, как часто вы ошибочно причислили человека к иллюминатам.
Полнота (прим. Recall) измеряет количество меток в проверочных данных, которые модель определила правильно.
И F1 это комбинация обеих меток. Вы можете увидеть, что если причислить всех людей к иллюминатам, то это обеспечит максимальную полноту и ничтожную аккуратность.
Т.к. всё помечено мной, то я не сильно заинтересован в аккуратности модели. Мне нужна полнота и точность.
В первом варианте свойств, я рассматривал только истинные булевы значения. Т.е. в параграфе выше, все наборы были вида «ADR 0=True» и «PS 0=True». Точность (прим. Item accuracy) составила 63.4%.
63.4% это хорошо? Исходя из того, что NULL, PS 0 и FN 0 составляют три четверти наших проверочных данных, и они по природе своей легко находятся, мы определённо можем лучше. Теперь добавим оставшуюся часть позиционных булевых значений, ложных.
Вариант 2: все позиционные булевы значения
Label Count Recall NULL 254 0.9048 PS 0 204 0.9899 FN 0 149 0.975 OTHER 24 0.2273 PS - 2 19 0.2857 Item accuracy: 515 / 678 (0.7596)
Теперь мы отлично определяем простые случаи и получили достойную точность. 75% означают, что вам нужно пометить лишь первую книгу «Игра Престолов» и одну треть «Битва Королей» и модель определить оставшиеся три четверти книг сама. Это требует много часов работы, но в пределах разумного.
И тем не менее, я не вижу причин почему бы не определять теги NULL с полнотой 98%+, поэтому давайте добавим свойство нацеленной на это.
Вариант 3: кавычки?
Label Count Recall PS 0 218 0.9907 NULL 180 0.9119 FN 0 167 0.9118 OTHER 63 0.3784 PS 2 25 0.5 Item accuracy: 550 / 710 (0.7746)
Считаем количество открывающихся кавычек в параграфе.
Я хочу сказать, что удивлен тем, что NULL не стал точнее. Нужно поработать над этим. Дальше я бы хотел улучшить FN 0.
Вариант 4: индекс первого имени?
Label Count Recall PS 0 218 0.9907 NULL 183 0.9057 FN 0 157 0.8971 OTHER 68 0.4189 PS - 2 23 0.5484 Item accuracy: 551 / 710 (0.7761)
Это свойство содержит индекс первого имени.
хмм… возможно чересчур усложнили, давайте снова вернёмся к булевым значениям.
Вариант 5: индекс 0 имя? + избыточность
Label Count Recall PS 0 216 0.986 FN 0 166 0.9265 NULL 160 1 OTHER 85 0.5811 PS 2 32 0.7143 Item accuracy: 578 / 710 (0.8141)
Вот оно! Я не правильно считал количество открывающих кавычек, тем самым портя результат.
Как только я это исправил, NULL определяется идеально… но теперь у нас кончились лёгкие способы улучшения модели. Мне теперь на самом деле нужно изловчиться, чтобы дальше улучшить результат! Посмотрим, сработает ли это…
Вариант 6: После говорящий (PS) + и — 2
Тут мы будем использовать булево значение если говорящий находится двумя параграфами выше или ниже текущего. В теории это должно повысить результат PS -2.
Label Count Recall PS 0 216 0.986 FN 0 166 0.9265 NULL 160 1 OTHER 84 0.5676 PS 2 32 0.7143 Item accuracy: 578 / 710 (0.8141)
Никак не влияет!
Вариант 7: последовательности??
Label Count Recall PS 0 217 0.986 FN 0 168 0.9265 NULL 160 1 OTHER 82 0.5541 PS 2 30 0.6429 Item accuracy: 576 / 710 (0.8113) Instance accuracy: 56 / 142 (0.3944)
Подождите! Выяснилось, что CRF может работать с последовательностями, и на самом деле в этом и есть его смысл. Я игнорировал величину точности экземпляра (прим. Instance accuracy), т.к. она всегда была 0/1, что означает, что модель рассматривала весь текст как один длинный диалог.
Простите, мне нужно дать себе пощёчину. Предполагая что мы повысим точность — и этот открытый вопрос — как мы воспользуемся этим функционалом? Я попробовал указать длину каждой последовательности в 5 параграфов, но это не кажется мне правильным.
Возможно, если встретятся два последовательных NULLа, то это и будет последовательностью, предполагая что разговор завершён.
После того как я поигрался с этим, я так и не смог построить модель, которая бы работала с разговорами. Как я понял, она должна иметь множество специальных переходных весов (прим. transition weights), в зависимости от положения в последовательности. Таким образом, модель будет принимать разные решения, в зависимости от нашего положения, в начале, середине или в конце разговора.
Но ничего в поведении модели не показывает что это случается. В ближайшее время, я еще поиграюсь немного с другими свойствами. Ах да, давайте взглянем на скрипт, который генерирует наши обучающие и проверочные данные. Он не оптимизированный, т.к. высчитывает свойства для каждого параграфа 5 раз. Я оставлю его как есть для этого материала, но имейте ввиду, что его можно ускорить если воспользоваться одним циклом для сохранения булевых свойств параграфов и вторым для добавления к имеющимся.
tree = ASOIAFtoXML([{"title": "ASOIAF", "contents": "corpus/train_asoiaf_pos_tagged.txt"}])
paragraphs = tree.xpath(".//paragraph")
In [29]:
def prep_test_data(paragraphs):
max_index = len(paragraphs)
results = []
for index, paragraph in enumerate(paragraphs):
extractor = feature_extractor(paragraph, set_of_particles)
all_features = extractor.local_features() + extractor.feature_booleans()
for n in [-2, -1, 1, 2]:
if 0 <= n+index < max_index:
neighbor_features = feature_extractor(paragraphs[index + n], set_of_particles, tag_distance = n).feature_booleans()
if neighbor_features:
all_features += neighbor_features
all_features.insert(0, extractor.speaker)
results.append("t".join(all_features))
return results
results = prep_test_data(paragraphs)
In [31]:
max_index = len(results)
with codecs.open(r"new_test.txt", "w", "utf-8") as output:
for line in results[:int(max_index/2)]:
output.write(line + 'n')
with codecs.open(r"new_train.txt", "w", "utf-8") as output:
for line in results[int(max_index/2):]:
output.write(line + 'n')Больше свойств
Я попробовал несколько других свойств:
- Подсчёт количества имён до первой строчки диалога. В теории это место, где больше всего NN. Результата нет.
- Свойство которое отмечает что параграф полностью или частично диалог. Это способствовало улучшению ситуации с PS -2 и FN -2, но разницы была не существенна.
- Короткие/длинные параграфы. Мало пользы.
- «и» либо «но» в тексте до диалога. (в попытке сфокусироваться на NN 0, где они игнорировались)
Я думал, что последний это достаточно ловкий ход, но он не сработал и мы никак не получали точность выше 81%.
Я пытался менять обучающие данные с проверочными и это дало 84%. Вам не следует тратить много времени на совершенствовании множества свойств для определенных данных, т.к. это ведёт к переобучению. По факту, смешивание обучающих данных и проверочных — хорошая идея. Я их не смешивал, т.к. думал что это приведёт к порче последовательностей, но мы же уже не используем их, так почему бы и нет? Мы их смешаем.
Немного смешали данные
Получили 82%.
Ладно! Думаю тут мы достигли предела моих навыков.
А продолжения не будет?
Давайте подведём итоги и поговорим что же можно сделать дальше.
- Улучшить обучающие данные. Сейчас у меня есть 700 параграфов для обучения и проверки. Всего их около 40000. Радует, что я пометил 1.7% и получил в результате 80%. (хотя я сомневаюсь в 80%, на практике это было больше похоже на 75%.) Что произойдёт если мы используем 10000 параграфов для обучения? Ценность дополнительных тренировочных данных не сильно возрастает с увеличением их количества, но для редких меток, как ADR, попросту недостаточно моих 700 параграфов.
- Тщательно изучить документацию CRFsuite. Там наверняка найдутся параметры, которые мне помогут.
- Поэкспериментировать со взвешенными свойствами.
- Действительно попробовать воспользоваться последовательностями.
- Написать оболочку для Python. Кроме как это позволит избежать переброса данных, это так же очень поможет улучшить модель. Например, я могу сделать…
- Запасную метку. Слабым местом моей модели является то, что слишком много меток OTHER. При пометке OTHER, модель как бы говорит, смотри, я знаю что кто то говорит в этом параграфе, но ты не дал мне способа его определить. Поэтому никакой положительной стороны у метки OTHER нет — улучшением будет даже самое нелепое тыканье в темноту.
- Метку пола. Мне нравятся диалоги с именами в конце. Этого не происходит в разговорах мужчин и женщин. Так, много диалогов Кейтилин Старк остались не помеченными потому, что, как правило, она единственная женщина в окружении и поэтому удобнее обращаться к ней просто как «она». Это будет достаточно легко обойти; мы можем искать все «она» в после диалоговой части и потом проверить заголовок главы и если это женское имя, то она нашлась.
Заключение
Хорошо! Я надеюсь, что это было кому то полезно. Спасибо, что прочитали и если вы хотите со мной связаться, то я есть в Твиттере.
Так же, я хотел бы отметить, что всё вышеупомянутое было сделано для большого критического исследования Игры Престолов. Если вы фанат этих книг и хотели бы прочесть анализ, который был возможен благодаря метке диалогов, то я скоро всё опубликую.
Автор: A3a
