1.1 Половая идентификация

В 4 мы увидели, что мужские и женские имена имеют некоторые отличительные особенности. Имена, оканчивающиеся на a, e и i, вероятно, будут женскими, в то время как имена, заканчивающиеся на k, o, r, s и t, вероятно, будут мужскими. Давайте построим классификатор, чтобы смоделировать эти различия более точно.

Первым шагом в создании классификатор является решение о том, какие свойства входа релевантны и как кодировать эти свойства. Для этого примера мы начнем с заключительной буквы имени. Следующая функция извлечения свойств создает словарь, содержащий соответствующую информацию о данном имени:

>>> def gender_features(word):
...     return {'last_letter': word[-1]}
>>> gender_features('Shrek')
{'last_letter': 'k'}

Возвращенный словарь, известный как набор свойств ставит в соответствие имена свойств и их значения. Названия свойств - это чувствительные к регистру строки, которые обычно предоставляют короткое легко читаемое описание свойства, как в нашем примере 'last_letter'. Значения свойств - это значения с простыми типами, такими как логические значения, числа и строки.

Теперь, когда мы определили экстрактор свойств, нам необходимо подготовить перечень примеров и соответствующие метки классов.

>>> from nltk.corpus import names
>>> labeled_names = ([(name, 'male') for name in names.words('male.txt')] +
... [(name, 'female') for name in names.words('female.txt')])
>>> import random
>>> random.shuffle(labeled_names)

Далее мы используем экстрактор свойств для обработки данных names и разделить полученный список наборов свойств на тренировочный набор и тестовый набор. Тренировочный набор используется для подготовки нового «наивного классификатора Байеса".

>>> featuresets = [(gender_features(n), gender) for (n, gender) in labeled_names]
>>> train_set, test_set = featuresets[500:], featuresets[:500]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set)

Мы узнаем больше о наимвном классификаторе Байеса позже в этой главе. На данный момент давайте просто проверим его на несколько именах, которых не было в обучающих данных:

>>> classifier.classify(gender_features('Neo'))
'male'
>>> classifier.classify(gender_features('Trinity'))
'female'

Заметим, что эти имена персонажей из Матрицы классифицированы правильно. Хотя этот научно-фантастический фильм рассказывает о событиях 2199 года, он все же соответствует нашим ожиданиям об именах и полах. Мы можем систематически оценивать классификатор на гораздо большем количестве невидимых данных:

>>> print(nltk.classify.accuracy(classifier, test_set))
0.77

И, наконец, мы можем исследовать классификатор, чтобы определить, какие из свойств, которые он нашел, наиболее эффективны для различения имен по гендерному признаку:

>>> classifier.show_most_informative_features(5)
Most Informative Features
             last_letter = 'a'            female : male   =     33.2 : 1.0
             last_letter = 'k'              male : female =     32.6 : 1.0
             last_letter = 'p'              male : female =     19.7 : 1.0
             last_letter = 'v'              male : female =     18.6 : 1.0
             last_letter = 'f'              male : female =     17.3 : 1.0

Этот список показывает, что имена в обучающем наборе, которые заканчиваются на "a" являются женскими в 33 раза чаще, чем мужскими, а имена, которые заканчиваются на "k" являются мужскими в 32 раза чаще, чем женскими. Эти соотношения известны как доли вероятности и могут быть полезны для сравнения различных отношений свойство-результат.

При работе с большими корпусами построения единого списка, который содержит в себе свойства всех экземпляров может занимать большой объем памяти. В этих случаях используйте функцию nltk.classify.apply_features, которая возвращает объект, который действует как список, но не хранит все наборы свойств в памяти:

>>> from nltk.classify import apply_features
>>> train_set = apply_features(gender_features, labeled_names[500:])
>>> test_set = apply_features(gender_features, labeled_names[:500])

1.2 Выбор правильных свойств

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

Как правило, экстракторы свойств строятся методом проб и ошибок под руководством интуиций о том, какая информация имеет отношение к этой проблеме. Общераспространенным является начало с подхода "кухонная раковина", когда в дело идут все свойства, которые вы можете придумать, а затем выполняется проверка того, какие свойства, на самом деле, являются полезными. Мы принимаем этот подход гендерных свойств имени в 1.2.

def gender_features2(name):
    features = {}
    features["first_letter"] = name[0].lower()
    features["last_letter"] = name[-1].lower()
    for letter in 'abcdefghijklmnopqrstuvwxyz':
        features["count({})".format(letter)] = name.lower().count(letter)
        features["has({})".format(letter)] = (letter in name.lower())
    return features

>>> gender_features2('John') 
{'count(j)': 1, 'has(d)': False, 'count(b)': 0, ...}

Однако обычно есть ограничения на количество свойств, которые вы должны использовать с заданным алгоритмом обучения - если вы предоставляете слишком много свойств, то алгоритм будет иметь более высокий шанс полагаться на стилистические особенности ваших тренировочных данных, которые плохо обобщают новые примеры. Эта проблема известна как переобученность и может быть особенно проблематичной при работе с небольшими наборами тренировочных данных. Например, если мы тренируем наивный байесовский классификатор, используя экстрактор свойств, показанный в 1.2, он будет переобучен относительно небольшого тренировочного набора, в результате чего будет создана модель, в которой точность составляет около 1% ниже, чем точность классификатора, который только обращает внимание на последнюю букву каждого имени:

>>> featuresets = [(gender_features2(n), gender) for (n, gender) in labeled_names]
>>> train_set, test_set = featuresets[500:], featuresets[:500]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set)
>>> print(nltk.classify.accuracy(classifier, test_set))
0.768

После того, как первоначальный набор свойств был выбран, очень продуктивным методом для уточнения набора свойств является анализ ошибок. Сначала мы выбираем набор для разработки, содержащий данные для создания модели. Этот набор разработки затем делится на тренировочный набор и тестовый (dev-test) набор.

>>> train_names = labeled_names[1500:]
>>> devtest_names = labeled_names[500:1500]
>>> test_names = labeled_names[:500]

Тренировочный набор разработки используется для обучения модели, а тестовый набор разработки (dev-test) используется для выполнения анализа ошибок. Тестовый (test) набор используется в нашей окончательной оценке системы. По причинам, изложенным ниже, важно, чтобы мы использовали отдельный набор для анализа ошибок (dev-test ), а не просто тестовый набор (test set). Разделение данных корпуса на различные наборы показано в 1.3.

Рисунок 1.3: Организация данных корпуса для обучения контролируемых классификаторов. Данные корпуса делятся на две группы: набор разработки и тестовый набор. Набор разработки часто подразделяется на тренировочный набор и тестовый набор разработки.

Разделив корпус на соответствующие наборы данных, мы готовим модель, используя тренировочный набор , а затем прогоняем ее на тестовом наборе разработки.

>>> train_set = [(gender_features(n), gender) for (n, gender) in train_names]
>>> devtest_set = [(gender_features(n), gender) for (n, gender) in devtest_names]
>>> test_set = [(gender_features(n), gender) for (n, gender) in test_names]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set) 
>>> print(nltk.classify.accuracy(classifier, devtest_set)) 
0.75

Используя тестовый набор разработки, мы можем сгенерировать список ошибок, которые классификатор делает при прогнозировании пола имени:

>>> errors = []
>>> for (name, tag) in devtest_names:
...     guess = classifier.classify(gender_features(name))
...     if guess != tag:
...         errors.append( (tag, guess, name) )

Затем мы можем исследовать отдельные случаи ошибок, когда модель предсказала неправильную метку, и попытаться определить, какие дополнительные элементы информации позволили бы ей принять правильное решение (или какие существующие фрагменты информации заставляют ее принять неправильное решение). Набор свойств может быть соответствующим образом скорректирован. Классификатор имен, который мы построили, генерирует около 100 ошибок на на тестовом наборе разработки:

>>> for (tag, guess, name) in sorted(errors):
...     print('correct={:<8} guess={:<8s} name={:<30}'.format(tag, guess, name))
correct=female   guess=male     name=Abigail
  ...
correct=female   guess=male     name=Cindelyn
  ...
correct=female   guess=male     name=Katheryn
correct=female   guess=male     name=Kathryn
  ...
correct=male     guess=female   name=Aldrich
  ...
correct=male     guess=female   name=Mitch
  ...
correct=male     guess=female   name=Rich
  ...

Просматривая этот список ошибок становится ясно, что некоторые суффиксы, состоящие из двух и более букв, могут указывать на мужское или женское имя. Например, имена, заканчивающиеся на yn оказываются преимущественно женскими, несмотря на то, что имена, оканчивающиеся на n имеют тенденцию быть мужскими; а имена, заканчивающиеся на ch обычно мужские, несмотря на то, что имена, которые заканчиваются на h, как правило, женские. Поэтому мы скорректируем наш экстрактор свойств и включим в него свойства для двухбуквенных суффиксов:

>>> def gender_features(word):
...     return {'suffix1': word[-1:],
...             'suffix2': word[-2:]}

Перестроив классификатор с новым экстрактором свойств, мы видим, что результативность на тестовом наборе разработки улучшается почти на 2 процентных пункта (с 76,5% до 78,2%):

>>> train_set = [(gender_features(n), gender) for (n, gender) in train_names]
>>> devtest_set = [(gender_features(n), gender) for (n, gender) in devtest_names]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set)
>>> print(nltk.classify.accuracy(classifier, devtest_set))
0.782

Эта процедура анализа ошибок может быть затем повторена для проверки паттернов ошибок, которые были сделаны недавно улучшенным классификатором. Каждый раз, когда повторяется процедура анализа ошибок, мы должны по-другому поделить данные на тренировочный и тестовый набор разработки, чтобы гарантировать, что классификатор не начинает отражать особенности тестового набора разработки.

Но как только мы использовали тестовый набор разработки для подготовки модели, мы больше не можем верить, что он даст нам точное представление о том, как хорошо модель будет работать на новых данных. Поэтому важно держать тестовый набор отдельно и не использовать его, пока наша разработка модели не будет завершена. Когда разработка будет завершена, мы можем использовать тестовый набор, чтобы оценить, насколько хорошо наша модель будет работать на новых входных данных.

1.3 Классификация документов

В 1 мы видели несколько примеров корпусов, в которых документы были помечены категориями. Используя эти корпусы, мы можем построить классификаторы, которые будут автоматически помечать новые документы соответствующими метками категорий. Сначала мы строим перечень документов, помеченных соответствующими категориями. Для этого примера мы выбрали корпус отзывов на фильмы, который классифицирует каждый обзор как положительный или отрицательный.

>>> from nltk.corpus import movie_reviews
>>> documents = [(list(movie_reviews.words(fileid)), category)
...              for category in movie_reviews.categories()
...              for fileid in movie_reviews.fileids(category)]
>>> random.shuffle(documents)

Далее мы определяем экстрактор свойств для документов, чтобы классификатор знал, на какие аспекты данных следует обратить внимание (1.4). Для идентификации темы документа, мы можем определить свойство для каждого слова, указывающее, содержит ли документ это слово. Чтобы ограничить количество свойств, которые классификатор должен обрабатывать, мы начинаем с построения списка 2000 наиболее частых слов в общем корпусе . Затем мы можем определить экстрактор свойств , который просто проверяет, присутствует ли каждое из этих слов в данном документе.

all_words = nltk.FreqDist(w.lower() for w in movie_reviews.words())
word_features = list(all_words)[:2000] 

def document_features(document): 
    document_words = set(document) 
    features = {}
    for word in word_features:
        features['contains({})'.format(word)] = (word in document_words)
    return features

>>> print(document_features(movie_reviews.words('pos/cv957_8737.txt'))) 
{'contains(waste)': False, 'contains(lot)': False, ...}

Теперь, когда мы определили наш экстрактор свойств, мы можем использовать его, чтобы обучить классификатор помечать новые обзоры фильмов (1.5). Чтобы проверить, насколько надежен полученный классификатор, мы вычислим его точность на тестовом наборе . И снова мы можем использовать show_most_informative_features(), чтобы выяснить, какие из найденных классификатором свойств оказались наиболее информативными .

featuresets = [(document_features(d), c) for (d,c) in documents]
train_set, test_set = featuresets[100:], featuresets[:100]
classifier = nltk.NaiveBayesClassifier.train(train_set)

>>> print(nltk.classify.accuracy(classifier, test_set)) 
0.81
>>> classifier.show_most_informative_features(5) 
Most Informative Features
   contains(outstanding) = True              pos : neg    =     11.1 : 1.0
        contains(seagal) = True              neg : pos    =      7.7 : 1.0
   contains(wonderfully) = True              pos : neg    =      6.8 : 1.0
         contains(damon) = True              pos : neg    =      5.9 : 1.0
        contains(wasted) = True              neg : pos    =      5.8 : 1.0

По-видимому в этом корпусе отзыв, в котором упоминается "Сигал", имеет почти в 8 раз больше шансов быть отрицательным, чем положительным, в то время как отзыв, который упоминает "Дэймона", примерно в 6 раз более вероятно, что будет положительным.

Разметка частей речи

В 5. мы построили разметчик, использующий регулярное выражение, который выбирает метку части речи для слова, глядя на внутреннюю структуру слова. Однако мы должны были сконструировать этот разметчик вручную. Вместо этого мы можем обучить классификатор определять, какие суффиксы являются наиболее информативными. Давайте начнем с выяснения того, какие суффиксы наиболее распространенные:

>>> from nltk.corpus import brown
>>> suffix_fdist = nltk.FreqDist()
>>> for word in brown.words():
...     word = word.lower()
...     suffix_fdist[word[-1:]] += 1
...     suffix_fdist[word[-2:]] += 1
...     suffix_fdist[word[-3:]] += 1

>>> common_suffixes = [suffix for (suffix, count) in suffix_fdist.most_common(100)]
>>> print(common_suffixes)
['e', ',', '.', 's', 'd', 't', 'he', 'n', 'a', 'of', 'the',
 'y', 'r', 'to', 'in', 'f', 'o', 'ed', 'nd', 'is', 'on', 'l',
 'g', 'and', 'ng', 'er', 'as', 'ing', 'h', 'at', 'es', 'or',
 're', 'it', '``', 'an', "''", 'm', ';', 'i', 'ly', 'ion', ...]

Далее мы определим функцию извлечения свойств, которая проверяет данное слово на эти суффиксы:

>>> def pos_features(word):
...     features = {}
...     for suffix in common_suffixes:
...         features['endswith({})'.format(suffix)] = word.lower().endswith(suffix)
...     return features

Функции извлечения свойств ведут себя как тонированные стекла, выделяя некоторые из свойств (цветов) в наших данных и делая невозможным увидеть другие свойства. Классификатор будет опираться исключительно на эти подчеркнутые свойства при определении того, как пометить входы. В этом случае классификатор будет принимать свои решения только на основе информации о том, какие из общих суффиксов (если таковые имеются) имеет данное слово.

Теперь, когда мы определили нашу функцию-экстрактор, мы можем использовать ее для подготовки нового классификатора на основе "дерева решений" (будет обсуждаться в 4):

>>> tagged_words = brown.tagged_words(categories='news')
>>> featuresets = [(pos_features(n), g) for (n,g) in tagged_words]

>>> size = int(len(featuresets) * 0.1)
>>> train_set, test_set = featuresets[size:], featuresets[:size]

>>> classifier = nltk.DecisionTreeClassifier.train(train_set)
>>> nltk.classify.accuracy(classifier, test_set)
0.62705121829935351

>>> classifier.classify(pos_features('cats'))
'NNS'

Одна хорошая особенность моделей на основе дерева решений состоит в том, что их часто довольно легко интерпретировать - мы можем даже поручить NLTK печатать их как псевдокод:

>>> print(classifier.pseudocode(depth=4))
if endswith(,) == True: return ','
if endswith(,) == False:
  if endswith(the) == True: return 'AT'
  if endswith(the) == False:
    if endswith(s) == True:
      if endswith(is) == True: return 'BEZ'
      if endswith(is) == False: return 'VBZ'
    if endswith(s) == False:
      if endswith(.) == True: return '.'
      if endswith(.) == False: return 'NN'

Здесь мы видим, что классификатор начинает с проверки, заканчивается ли слово запятой - если это так, то оно получит специальную метку ",". Далее классификатор проверяет, заканчивается ли слово на "the", в этом случае оно почти наверняка определитель. Этот "суффикс" используется в дереве решений, потому что слово "the" такое распространенное. Продолжая, классификатор проверяет, оканчивается ли слово на "s". Если это так, то , скорее всего, оно получит метку глагола VBZ (если это не слово "is", которое имеет специальную метку BEZ), а если нет, то это, скорее всего, существительное (если только это не знак препинания "."). Реальный классификатор содержит дальнейшие вложенные если-то предложения ниже тех, которые показаны здесь, но аргумент depth=4просто отображает верхнюю часть дерева решений.

1.5 Использование контекста

Путем добавления функции извлечения свойств мы могли бы изменить этот разметчик, чтобы он мог использовать множество других внутренних свойств слова, таких как длина слова, число слогов или его префикс. Однако до тех пор, пока экстрактор свойств просто смотрит на целевое слово, у нас нет никакого способа добавлять новые свойства, которые зависят от контекста, в котором слово появляется. Но контекстные возможности часто предоставляют мощные подсказки о правильной метке - например, при обработке слова "fly" знание о том, что предыдущее слово "a", позволит нам определить, что оно функционирует как существительное, а не глагол.

Для того чтобы учесть свойства, которые зависят от контекста данного слова, мы должны пересмотреть шаблон, который мы использовали для определения нашего экстрактор свойств. Вместо того, чтобы просто передавать слово, мы будем передавать полное (не помеченное) предложение с индексом целевого слова. Такой подход демонстрируется в 1.6, который использует экстрактор контекстно-зависимых свойств, чтобы определить классификатор частей речи.

def pos_features(sentence, i): 
    features = {"suffix(1)": sentence[i][-1:],
                "suffix(2)": sentence[i][-2:],
                "suffix(3)": sentence[i][-3:]}
    if i == 0:
        features["prev-word"] = "<START>"
    else:
        features["prev-word"] = sentence[i-1]
    return features

>>> pos_features(brown.sents()[0], 8)
{'suffix(3)': 'ion', 'prev-word': 'an', 'suffix(2)': 'on', 'suffix(1)': 'n'}

>>> tagged_sents = brown.tagged_sents(categories='news')
>>> featuresets = []
>>> for tagged_sent in tagged_sents:
...     untagged_sent = nltk.tag.untag(tagged_sent)
...     for i, (word, tag) in enumerate(tagged_sent):
...         featuresets.append( (pos_features(untagged_sent, i), tag) )

>>> size = int(len(featuresets) * 0.1)
>>> train_set, test_set = featuresets[size:], featuresets[:size]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set)

>>> nltk.classify.accuracy(classifier, test_set)
0.78915962207856782

Понятно, что использование контекстных свойств повышает результативность нашего разметчика частей речи. Например, классификатор узнает о том, что слово скорее всего является существительным, если оно идет сразу после слова "большой" или слова "губернаторского". Однако он не в состоянии выучить обобщение, что слово, вероятно, существительное, если оно следует за прилагательным, потому что он не имеет доступа к метке части речи предыдущего слова. В целом простые классификаторы всегда рассматривают каждый вход как независимый от всех других входов. Во многих случаях это имеет смысл. Например, решения о том, имеют ли имена тенденцию быть мужскими или женскими, могут быть приняты на основе перебора случаев. Однако часто бывают случаи, такие как разметка частей речи, где мы заинтересованы в решении проблем классификации, тесно связанных друг с другом.

1.6 Классификация последовательности

Для того, чтобы схватить зависимости между связанными задачами классификации, мы можем использовать модели объединенного классификатора, которые выбирают соответствующую маркировку для набора связанных входов. В случае разметки частей речи разнообразие различных моделей классификатора последовательности может быть использовано, для совместного выбора меток части речи для всех слов в данном предложении.

Одна из стратегий классификации последовательности, известная как последовательная классификация или жадные классификация последовательности, заключается в том, чтобы найти наиболее вероятную метку класса для первого входа, затем использовать этот ответ, чтобы найти лучшую метку для следующего входа. Затем процесс может повторяться до тех пор, пока все входные данные не были помечены. Это подход, который был принят биграмм-разметчиком из 5, который начал с выбора метки части речи для первого слова в предложении, а затем определял метку для каждого последующего слова на основе самого этого слова и предсказанной метки для предыдущего слова.

Эта стратегия показана в 1.7. Сначала мы должны усилить нашу функцию извлечения свойств, чтобы она принимала аргумент history, который предоставляет список меток, которые мы уже предсказали для данного предложения. Каждая метка в истории соответствует слову в предложении. Но учтите, что history будет содержать только метки для слов, которые мы уже классифицировали, то есть расположенных слева от целевого слова. Таким образом, в то время как можно посмотреть на некоторые особенности слов справа от целевого слова, не представляется возможным посмотреть на метки для этих слов (так как мы их еще не породили).

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

 def pos_features(sentence, i, history): 
     features = {"suffix(1)": sentence[i][-1:],
                 "suffix(2)": sentence[i][-2:],
                 "suffix(3)": sentence[i][-3:]}
     if i == 0:
         features["prev-word"] = "<START>"
         features["prev-tag"] = "<START>"
     else:
         features["prev-word"] = sentence[i-1]
         features["prev-tag"] = history[i-1]
     return features

class ConsecutivePosTagger(nltk.TaggerI): 

    def __init__(self, train_sents):
        train_set = []
        for tagged_sent in train_sents:
            untagged_sent = nltk.tag.untag(tagged_sent)
            history = []
            for i, (word, tag) in enumerate(tagged_sent):
                featureset = pos_features(untagged_sent, i, history)
                train_set.append( (featureset, tag) )
                history.append(tag)
        self.classifier = nltk.NaiveBayesClassifier.train(train_set)

    def tag(self, sentence):
        history = []
        for i, word in enumerate(sentence):
            featureset = pos_features(sentence, i, history)
            tag = self.classifier.classify(featureset)
            history.append(tag)
        return zip(sentence, history)

>>> tagged_sents = brown.tagged_sents(categories='news')
>>> size = int(len(tagged_sents) * 0.1)
>>> train_sents, test_sents = tagged_sents[size:], tagged_sents[:size]
>>> tagger = ConsecutivePosTagger(train_sents)
>>> print(tagger.evaluate(test_sents))
0.79796012981

1.7 Другие методы классификации последовательности

Один из недостатков этого подхода заключается в том, что мы придерживаемся каждого решения, которое мы приняли. Например, если мы решим пометить слово как существительное, но позже найдем доказательство того, что оно должно было быть глаголом, нет никакого способа вернуться и исправить свою ошибку. Одним из путей решения этой проблемы является принятие трансформационной стратегии. Трансформационные объединенные классификаторы работают путем создания первоначального присвоения меток для входов и последующего итеративного уточнения этого присвоения в попытке исправить несоответствия между связанными входами. Разметчик Брилля, описанный в (1), является хорошим примером этой стратегии.

Другим решением является назначение оценки для всех возможных последовательностей теги частей речи и выбор последовательности, общая оценка которой является самой высокой. Это подход, принятый Скрытыми моделями Маркова. Скрытые модели Маркова аналогичны последовательным классификаторам тем, что смотрят и на входы и на историю предсказанных меток. Однако они не просто находят единственную лучшую метку для данного слова, они генерируют распределение вероятностей по меткам. Эти вероятности затем объединяются для расчета оценки вероятности для последовательностей меток, и последовательность меток с наибольшей вероятностью выбирается. К сожалению, число возможных последовательностей меток достаточно велика. Для набор из 30 меток, есть около 600 триллион (30¹⁰) способов пометить предложение из 10 слов. Для того, чтобы избежать рассмотрения всех этих возможных последовательностей по отдельности, скрытые марковские модели требуют, чтобы экстрактор свойств смотрел только на самую последнюю метку (или на n самых последних меток, где n достаточно мало). Учитывая это ограничение, можно использовать динамическое программирование (4.7), чтобы эффективно найти наиболее вероятную последовательность меток. В частности, для каждого последовательного индекса слова i оценка вычисляется для каждой возможной текущей и предыдущей метки. Этот же базовый подход применяется двумя другими продвинутыми моделями, которые называются модели максимальной энтропии Маркова и линейно-цепные условные модели случайного поля; но другие алгоритмы используются для нахождения оценки последовательностей меток.

2.1 Выделение предложения

Выделение предложения можно рассматривать как задачу классификации для пунктуации: всякий раз, когда мы сталкиваемся с символом, который мог бы положить конец предложения, такие как период или знак вопроса, мы должны решить, прекращает ли предыдущее предложение.

Первый шаг заключается в том, чтобы получить некоторые данные, которые уже были разделены на предложения и преобразовать их в форму, которая является подходящей для извлечения признаков:

>>> sents = nltk.corpus.treebank_raw.sents()
>>> tokens = []
>>> boundaries = set()
>>> offset = 0
>>> for sent in sents:
...     tokens.extend(sent)
...     offset += len(sent)
...     boundaries.add(offset-1)

Здесь tokens - это объединенный список токенов из отдельных предложений, а boundaries - набор, содержащий индексы всех токенов на границе предложений. Далее нам необходимо указать свойства данных, которые будут использоваться для решения вопроса о том, указывает ли пунктуация на границу предложения:

>>> def punct_features(tokens, i):
...     return {'next-word-capitalized': tokens[i+1][0].isupper(),
...             'prev-word': tokens[i-1].lower(),
...             'punct': tokens[i],
...             'prev-word-is-one-char': len(tokens[i-1]) == 1}

На основе этого экстрактора свойств, мы можем создать список помеченных наборов свойств, выбрав все токены пунктуации и пометив, являются ли они граничными токенами или нет:

>>> featuresets = [(punct_features(tokens, i), (i in boundaries))
...                for i in range(1, len(tokens)-1)
...                if tokens[i] in '.?!']

С помощью этих наборов свойств, мы можем обучить и оценить классификатор пунктуации:

>>> size = int(len(featuresets) * 0.1)
>>> train_set, test_set = featuresets[size:], featuresets[:size]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set)
>>> nltk.classify.accuracy(classifier, test_set)
0.936026936026936

Чтобы использовать этот классификатор для выделения предложений, мы просто проверяем каждый знак препинания на предмет того, помечен ли он как граница; и разделяем список слов на знаках, являющихся границами предложений. Листинг в 2.1 показывает, как это можно сделать.

def segment_sentences(words):
    start = 0
    sents = []
    for i, word in enumerate(words):
        if word in '.?!' and classifier.classify(punct_features(words, i)) == True:
            sents.append(words[start:i+1])
            start = i+1
    if start < len(words):
        sents.append(words[start:])
    return sents

2.2 Определение типов акта диалога

При обработке диалога может быть полезно думать о высказываниях как о типе действия, выполняемого говорящим. Эта интерпретация наиболее очевидна для перформативных высказываний, таких как "Я прощаю тебя" или "Держу пари, вы не сможете подняться на этот холм". Но приветствия, вопросы, ответы, утверждения и уточнения - все могут рассматриваться как типы основанных на речи действий. Признание актов диалога, лежащих в основе высказываний в диалоге, может стать важным первым шагом в понимании беседы.

NPS Chat Corpus, который был продемонстрирован в 1, состоит из более чем 10.000 сообщений из сеансов обмена мгновенными сообщениями. Все эти сообщения были помечены одним из 15 типов акта диалога, такими как "Заявление", "Эмоция", "Вопрос" и "Продолжение". Поэтому мы можем использовать эти данные, чтобы построить классификатор, который может идентифицировать типы акта диалога для новых мгновенных сообщений. Первым шагом является извлечение основных данных сообщений. Мы вызовем xml_posts(), чтобы получить структуру данных, представляющую XML аннотацию для каждой записи:

>>> posts = nltk.corpus.nps_chat.xml_posts()[:10000]

Далее мы определим простой экстрактор свойств, который проверяет, какие слова содержит сообщение:

>>> def dialogue_act_features(post):
...     features = {}
...     for word in nltk.word_tokenize(post):
...         features['contains({})'.format(word.lower())] = True
...     return features

Наконец, мы построим данные обучения и тестирования путем применения экстрактор свойств для каждого сообщения (используя post.get('class') для получения типа акта диалога) и создадим новый классификатор:

>>> featuresets = [(dialogue_act_features(post.text), post.get('class'))
...                for post in posts]
>>> size = int(len(featuresets) * 0.1)
>>> train_set, test_set = featuresets[size:], featuresets[:size]
>>> classifier = nltk.NaiveBayesClassifier.train(train_set)
>>> print(nltk.classify.accuracy(classifier, test_set))
0.67

2.3 Признание текстового воплощения

Признание текстового воплощения (ПТВ (RTE)) - это задача определения того, влечет ли за собой данный фрагмент текста T другой текст, который называется "гипотезой" (как уже обсуждалось в 5). До сегодняшнего дня было четыре RTE проблемы с доступными для конкурирующих команд данными для разработки и тестирования. Вот несколько примеров пар текст/гипотеза из набора данных разработки проблемы №3. Метка Истина указывает на то, что воплощение есть, а Ложь на то, что его нет.

Задача 3, пара 34 (Истина)

Т: Парвиз Давуди представлял Иран на встрече Шанхайской организации сотрудничества (ШОС), формирующейся ассоциации, которая связывает вместе Россию, Китай и четыре бывших советских республик Средней Азии для борьбы с терроризмом.

Г: Китай является членом ШОС.

Задача 3, пара 81 (Ложь)

Т: В соответствии с уставом организации NC членами ООО являются Г. Нэльсон Биверс, ИИИ, Г. Честер Биверс и Дженни Биверс Стюарт.

Г: Jennie Биверс Стюарт является акционером Аналитической лаборатории Королины.

Следует подчеркнуть, что не предполагается, что связь между текстом и гипотезой должна быть логической реализацией, скорее речь идет о том, сделает ли человек вывод, что текст содержит разумные доказательства для принятия гипотезы в качестве истины.

Мы можем относиться к RTE как классификационной задаче, в которой мы пытаемся предсказать True/False метку для каждой пары. Хотя вполне вероятно, что успешные подходы к решению этой задачи будут включать сочетание синтаксического разбора, семантики и знаний реального мира, многие ранние попытки RTE достигли достаточно хороших результатов с помощью неглубокого анализа на основе сходства текста и гипотезы на уровне слов. В идеальном случае мы бы ожидали, что если есть воплощение, то вся информация, выраженная гипотезой, должна также присутствовать в тексте. И наоборот, если есть информация, содержащаяся в гипотезе, которая отсутствует в тексте, то воплощения не будет.

В нашем детекторе свойств RTE (2.2), мы позволили словам (т.е. типам слов) служить в качестве представителя информации, а наши свойства подсчитывают степень совпадения слов и степень, до которой слова есть в гипотезе, но не в тексте (схваченная методом hyp_extra()). Не все слова одинаково важны - упоминания именованных субстанций, таких как имена людей, организаций и мест, вероятно, будут более значительными, что побуждает нас извлечь четкую информацию для wordS и neS (именованных субстанций). Кроме того, некоторые высокочастотные функциональные слова отфильтровываются как "стоп-слова".

def rte_features(rtepair):
    extractor = nltk.RTEFeatureExtractor(rtepair)
    features = {}
    features['word_overlap'] = len(extractor.overlap('word'))
    features['word_hyp_extra'] = len(extractor.hyp_extra('word'))
    features['ne_overlap'] = len(extractor.overlap('ne'))
    features['ne_hyp_extra'] = len(extractor.hyp_extra('ne'))
    return features

Чтобы проиллюстрировать содержание этих свойств, мы рассмотрим некоторые атрибуты Пары текста/гипотезы №34, показанной ранее:

>>> rtepair = nltk.corpus.rte.pairs(['rte3_dev.xml'])[33]
>>> extractor = nltk.RTEFeatureExtractor(rtepair)
>>> print(extractor.text_words)
{'Russia', 'Organisation', 'Shanghai', 'Asia', 'four', 'at',
'operation', 'SCO', ...}
>>> print(extractor.hyp_words)
{'member', 'SCO', 'China'}
>>> print(extractor.overlap('word'))
set()
>>> print(extractor.overlap('ne'))
{'SCO', 'China'}
>>> print(extractor.hyp_extra('word'))
{'member'}

Эти свойства указывают, что все важные слова в гипотезе содержатся в тексте, и, таким образом, есть некоторое оправдание для маркировки этой пары как Истины.

Модуль nltk.classify.rte_classify достигает точности чуть более 58% на комбинированных тестовых данных RTE с помощью таких методов. Хотя эта цифра не очень впечатляет, требуются значительные усилия и больше лингвистической обработки, чтобы значительно улучшить результаты.

2.4 Увеличение масштаба до больших наборов данных

Python предоставляет отличную среду для выполнения базовых операций обработки текста и извлечения свойств. Однако он не способен выполнить интенсивные численные вычисления, требуемые методами машинного обучения столь же быстро, как языки низкого уровня, как C. Поэтому, если вы попытаетесь использовать чисто питоновские реализации машинного обучения (например, NLTK.NaiveBayesClassifier) на больших наборах данных, вы можете обнаружить, что алгоритму обучения требуется необоснованно большое количество времени и памяти для завершения.

Если вы планируете обучать классификаторы с помощью большого количества обучающих данных или большому количеству свойств, мы рекомендуем вам изучить возможности NLTK для взаимодействия с внешними пакетами машинного обучения. После того, как были установлены эти пакеты, NLTK может прозрачно вызывать их (с помощью системных вызовов) для обучения моделей классификаторов значительно быстрее, чем чисто питоновские реализации. Посетите веб-страницу NLTK для получения списка рекомендуемых пакетов машинного обучения, которые поддерживаются NLTK.

3.1 Тестовый набор данных

Большинство методов оценки рассчитывают балл модели путем сравнения меток, которые она генерирует для входов в тестовом наборе (или оценочном наборе) с правильными метками для этих входов. Этот тестовый набор, как правило, имеет такой же формат, как и обучающий набор. Однако очень важно, чтобы тестовый набор отличался от учебного корпуса: если бы мы просто повторно использовали учебный набор в качестве тестового набора, то модель, которая просто запомнили свой вход, без обучения тому, как обобщить учебный набор для новых примеров, мы бы получили обманчиво высокий балл.

При построении тестового набора, зачастую существует компромисс между количеством данных доступных для тестирования и количеством данных доступных для обучения. Для задач классификации, которые имеют небольшое количество хорошо сбалансированных меток и разнообразный тестовый набор, значимая оценка может быть выполнена с помощью всего лишь 100 экземпляров оценки. Но если задача классификации имеет большое количество меток или включает в себя очень редкие метки, то размер тестового набора должен быть выбран таким образом, чтобы гарантировать, что наименее частая метка встречается по меньшей мере 50 раз. Кроме того, если тестовый набор содержит множество тесно связанных экземпляров - таких, как экземпляры, выбираемые из одного документа - то размер тестового набора должен быть увеличен, чтобы гарантировать, что это отсутствие разнообразия не искажает результаты оценки. Когда доступно большое количество аннотированных данных, обычное дело заблуждаться "на стороне безопасности" используя 10% от общего объема данных для оценки.

Еще одно соображение при выборе тестового набора - это степень сходства между экземплярами в тестовом наборе и наборе разработки. Чем более схожи эти два набора данных, тем менее уверенными мы можем быть, что результаты оценки будут обобщать результаты на других наборах данных. Например, рассмотрим задачу частеречной разметки. На одном полюсе мы могли бы создать обучающий набор и тестовый набор, назначая в случайном порядке предложения из источника данных, который отражает единственный жанр (новости):

>>> import random
>>> from nltk.corpus import brown
>>> tagged_sents = list(brown.tagged_sents(categories='news'))
>>> random.shuffle(tagged_sents)
>>> size = int(len(tagged_sents) * 0.1)
>>> train_set, test_set = tagged_sents[size:], tagged_sents[:size]

В этом случае наш тестовый набор будет очень похож на наш тренировочный набор. Обучающий набор и набор для тестирования взяты из одного и того же жанра, поэтому мы не можем быть уверены в том, что результаты оценки будут обобщать результаты для других жанров. Что еще хуже, из-за вызова random.shuffle(), тестовый набор содержит предложения, которые взяты из тех же документов, которые были использованы для обучения. Если есть какая-либо закономерность в пределах документа - скажем, если данное слово появляется с определенной меткой части речи особенно часто - то эта особенность будет отражена как в наборе разработки, так и в тестовом наборе. Несколько лучший подход состоит в том, чтобы тренировочный и тестовый набор были взяты из различных документов:

>> file_ids = brown.fileids(categories='news')
>>> size = int(len(file_ids) * 0.1)
>>> train_set = brown.tagged_sents(file_ids[size:])
>>> test_set = brown.tagged_sents(file_ids[:size])

Если мы хотим выполнить более жесткие оценки, мы можем составить тестовый набор из документов, которые менее тесно связаны с документами в тренировочном наборе:

>>> train_set = brown.tagged_sents(categories='news')
>>> test_set = brown.tagged_sents(categories='fiction')

Если мы построим классификатор, который хорошо работает на этом тестовом наборе, то мы можем быть уверены в том, что он имеет способность хорошо обобщать далеко за пределами данных, на которых он был обучен.

3.2 Точность

Наиболее простой показатель, который может быть использован для оценки классификатора, точность, измеряет процент входов в тестовом наборе, которые были правильно помечены классификатором. Например, классификатор пола имени, который предсказывает правильное название 60 раз в тестовом наборе, содержащем 80 имен, будет иметь точность 60/80 = 75%. Функция nltk.classify.accuracy() рассчитает точность модели классификатора на данном тестовом наборе:

>>> classifier = nltk.NaiveBayesClassifier.train(train_set) 
>>> print('Accuracy: {:4.2f}'.format(nltk.classify.accuracy(classifier, test_set))) 
0.75

При интерпретации балла точности классификатора важно учитывать частоты меток отдельных классов в тестовом наборе. Например, рассмотрим классификатор, который определяет правильно смысл слова для каждого вхождения слова bank. Если мы оцениваем этот классификатор по тексту финансовой ленте новостей, то мы можем обнаружить, что значение финансовое учреждение появляется 19 раз из 20. В этом случае точность 95% вряд ли впечатляет, так как мы могли бы достичь такой точности с моделью, которая всегда возвращает значение финансовое учреждение. Однако, если мы напротив оцениваем классификатор на более сбалансированном корпусе, где самое распространенное значение слова имеет частоту 40%, тогда 95% оценка точности будет гораздо более позитивный результат. (Аналогичная проблема возникает при измерении согласия между аннотаторами в 2.)

3.3 Точность и охват

Другой случай, когда баллы точности могут ввести в заблуждение, - задачи "поиска", такие как поиск информации, где мы пытаемся найти документы, которые имеют отношение к конкретной задаче. Поскольку число несоответствующих документов значительно превышает число соответствующих документов, оценка точности модели, которая маркирует каждый документ как несоответствующий была бы очень близка к 100%.

Рисунок 3.1: Истинные и ложные позитивы и негативы

Поэтому обычно используется другой набор мер для задач поиска, основанный на количестве элементов в каждой из четырех категорий, показанных на Рисунке 3.1:

• Истинные позитивы - это релевантные элементы, которые мы правильно определили как релевантные.
• Истинные негативы - это нерелевантные элементы, которые мы правильно определили как нерелевантные.
• Ложные позитивы (или Тип I ошибки) - это нерелевантные элементы, которые мы неправильно идентифицировали как релевантные.
• Ложные негативы (или Тип II ошибки) - это релевантные элементы, которые мы неправильно идентифицировали как нерелевантные.

Учитывая эти четыре числа, мы можем определить следующие показатели:

• Точность, которая указывает на то, сколько элементов, которые мы определили, были релевантны, TP/(TP + FP).
• Охват, который указывает, сколько релевантных элементов мы идентифицировали TP/(TP+FN).
• F-Мера (или F-балл), который сочетает в себе точность и охват, чтобы выразить единый балл, определяется как среднее гармоническое точности и охвата: (2×Точность×Охват)/(Точность + Охват).

3.4 Матрицы ошибок

При выполнении задач классификации с более, чем тремя метками, может быть информативным подразделять ошибки, сделанные моделью, по типу ошибки. Матрица ошибок представляет собой таблицу, где каждая ячейка [i, j] указывает на то, как часто метка j была предсказана, когда правильной был метка i. Таким образом, диагональные элементы (т.е. ячейки |ii|) указывают на метки, которые были предсказаны правильно, а недиагональные элементы указывают на ошибки. В следующем примере мы создаем матрицу ошибок для биграмм-разметчика, разработанного в 4:

>>> def tag_list(tagged_sents):
...     return [tag for sent in tagged_sents for (word, tag) in sent]
>>> def apply_tagger(tagger, corpus):
...     return [tagger.tag(nltk.tag.untag(sent)) for sent in corpus]
>>> gold = tag_list(brown.tagged_sents(categories='editorial'))
>>> test = tag_list(apply_tagger(t2, brown.tagged_sents(categories='editorial')))
>>> cm = nltk.ConfusionMatrix(gold, test)
>>> print(cm.pretty_format(sort_by_count=True, show_percents=True, truncate=9))
    |                                         N                      |
    |      N      I      A      J             N             V      N |
    |      N      N      T      J      .      S      ,      B      P |
----+----------------------------------------------------------------+
 NN | <11.8%>  0.0%      .   0.2%      .   0.0%      .   0.3%   0.0% |
 IN |   0.0%  <9.0%>     .      .      .   0.0%      .      .      . |
 AT |      .      .  <8.6%>     .      .      .      .      .      . |
 JJ |   1.7%      .      .  <3.9%>     .      .      .   0.0%   0.0% |
  . |      .      .      .      .  <4.8%>     .      .      .      . |
NNS |   1.5%      .      .      .      .  <3.2%>     .      .   0.0% |
  , |      .      .      .      .      .      .  <4.4%>     .      . |
 VB |   0.9%      .      .   0.0%      .      .      .  <2.4%>     . |
 NP |   1.0%      .      .   0.0%      .      .      .      .  <1.8%>|
----+----------------------------------------------------------------+
(row = reference; col = test)

Матрица ошибок показывает, что наиболее часто встречающиеся ошибки включают замену NN на JJ (для 1,6% слов) и NN на NNS (для 1,5% слов). Обратите внимание, что точки (.) указывают на ячейки, значение которых равно 0, а диагональные элементы - которые соответствуют правильным классификациям - отмечены угловыми скобками. .. XXX объясняет использование "референса" в приведенной выше легенде.

3.5 Перекрестная проверка

Для того, чтобы оценить наши модели, мы должны зарезервировать часть аннотированных данных для тестового набора. Как мы уже упоминали, если тестовый набор слишком мал, то наша оценка не может быть точной. Однако обычно увеличение тестового набора означает уменьшение учебного набора, что может оказать существенное влияние на результативность, если ограниченное количество аннотированных данных доступно.

Одним из решений этой проблемы является выполнение нескольких оценок на различных тестовых наборах и объединение баллов от этих оценок - метод, известный как перекрестная проверка. В частности, мы делим оригинальный корпус на N наборов, называемых складками. Для каждой из этих складок мы готовим модель, используя все данные за исключением данных в этой складке, а затем проверяем эту модель в этой складке. Даже если отдельные складки возможно слишком маленькие, чтобы дать точные баллы оценки сами по себе, комбинированный балл оценки основан на большом количестве данных, поэтому вполне надежен.

Второе и не менее важное преимущество использования кросс-проверки является то, что она позволяет нам исследовать, насколько широко результативность варьируется в зависимости от различных наборов обучения. Если мы получим очень похожие оценки для всех обучающих наборов N, то мы можем быть достаточно уверены в том, что оценка является точной. С другой стороны, если баллы оценки для каждого из N учебных наборов сильно отличаются, то нам, вероятно, следует скептически относиться к точности оценочного балла.

4.1 Энтропия и информационный выигрыш

Как уже упоминалось ранее, существует несколько методов для определения наиболее информативного свойства для пня решения. Один из популярных вариантов, который называется информационный выигрыш, измеряет, насколько более организованными становятся входные значения, когда мы разделяем их, используя данное свойство. Для того, чтобы определить, насколько дезорганизован исходный набор входных значений, мы вычисляем энтропию их меток, которая будет высокой, если входные значения имеют весьма разнообразные метки, и низким, если много входных значений имеют одинаковую метку. В частности, энтропия определяется как сумма вероятностей всех меток умноженных на логорифм вероятности той же метки по основанию 2:

(1)

H = −Σl |in| labelsP(l)×log2P(l).

Рисунок 4.2: Энтропия меток в задаче предсказания пола имени в зависимости от процентного содержания мужских имен в данном наборе.

Например, 4.2 показывает, как энтропия меток в задаче предсказания половой принадлежности имени зависит от соотношения мужских и женских имен. Обратите внимание, что если большинство входных значений имеют одинаковую метку (например, если Р(мужское) близок к 0 или около 1), то энтропия мала. В частности, метки, которые имеют низкую частоту, не вносят большой вклад в энтропию (так как Р(l) мало) и метки с высокой частотой не вносят большой вклад в энтропию (так как log₂P(l) мало). С другой стороны, если входные значения имеют большое разнообразие меток, тогда есть много меток со "средней" частотой, где ниР(l), ни log₂P(l) не малы, поэтому энтропия высокая. 4.3 показывает, как вычислить энтропию списка меток.

import math
def entropy(labels):
    freqdist = nltk.FreqDist(labels)
    probs = [freqdist.freq(l) for l in freqdist]
    return -sum(p * math.log(p,2) for p in probs)

>>> Печать (энтропия ([ 'мужской', 'мужской', 'мужской', 'мужчина'])) 0.0  >>> Печать (энтропия ([ 'мужской', 'женский', 'мужской', 'мужчина'])) 0,811 ...
 >>> Печать (энтропия ([ 'женский', 'мужской', 'женский', 'мужчина'])) 1,0  >>> Печать (энтропия ([ 'женский', 'женский', 'мужской', 'женский'])) 0,811 ...
 >>> Печать (энтропия ([ 'женский', 'женский', 'женский', 'женский'])) 0.0

После того, как мы рассчитали энтропию исходного набора меток входных значений, мы можем определить, насколько более организованными стали метки после применения пня решения. Для этого мы вычисляем энтропию для каждого из листьев пня решения и берем среднее значение величин энтропии этих листьев (взвешенных по количеству образцов в каждом листе). Информационный выигрыш тогда равен разности между величинами исходной и новой, уменьшенной энтропии. Чем больше информационная выгода, тем лучше пень решения выполняет работу по разделению входных значений на целостные группы, поэтому мы можем строить деревья решений путем выбора пней решений с самым высоким информационным выигрышем.

Еще одно соображение относительно деревьев решений - это эффективность. Простой алгоритм выбора пней решений, описанный выше, должен построить кандидата на пень решения для каждого возможного свойства, и этот процесс должен быть повторен для каждого узла в построенном дереве решений. Ряд алгоритмов были разработаны, чтобы сократить время на обучение за счет хранения и повторного использования информации о ранее оцененных примерах.

Деревья решений имеют ряд полезных качеств. Начнем с того, что они просты для понимания и их легко интерпретировать. Это особенно актуально в верхней части дерева решений, где алгоритм обучения обычно может найти очень полезные свойства. Деревья решений особенно хорошо подходят для случаев, когда могут быть сделаны многие иерархические категориальные различия. Например, деревья решений могут быть очень эффективными для схватывания филогенетических деревьев.

Однако деревья решений также имеют несколько недостатков. Одной из проблем является то, что, так как каждая ветвь в дереве решений расщепляет тренировочные данные, количество тренировочных данных доступных для подготовки нижних узлов дерева может стать недостаточным. В результате эти нижние узлы решений могут

переучиться на тренировочном наборе, извлекая паттерны, которые отражают характерные особенности обучающего набора, а не лингвистически значимые закономерности базовой проблемы. Одно из решений этой проблемы состоит в том, чтобы остановить деление узлов как только количество обучающих данных становится слишком мало. Другим решением является вырастить полное дерево решений, но потом подрезать узлы решений, которые не улучшают результативность на тестовом наборе разработки.

Вторая проблема с деревьями решений заключается в том, что они навязывают определенную последовательность проверки свойств, даже когда они могут действовать относительно независимо друг от друга. Например, при классификации документов по темам (таким как спорт, автомобилестроение или загадочные убийства), свойства, такие как hasword(football) являются весьма показательными для конкретной метки независимо от того, каковы другие значения свойства. Так как в верхней части дерева решений пространство ограничено, большинство из этих свойств должны повторяться на многих других ветвях дерева. А так как число ветвей увеличивается в геометрической прогрессии по мере продвижения вниз по дереву, количество повторений может быть очень большим.

Связанная с этим проблема заключается в том, что деревья решений не очень хорошо используют свойства, которые слабо предсказывают правильную метку. Так как эти свойства делают относительно небольшие постепенные улучшения, они, как правило, возникают очень низко в дереве решений. Но к тому времени, как обучающий компонент спустился достаточно глубоко, чтобы использовать эти свойства, уже нет достаточного количества тренировочных данных, чтобы достоверно определить, какой эффект они должны иметь. Если бы мы могли вместо этого посмотреть на эффект этих свойств на всем тренировочном наборе, то мы могли бы сделать некоторые выводы о том, как они должны влиять на выбор метки.

Тот факт, что деревья решений требуют, чтобы свойства проверялись в определенном порядке, ограничивает их способность использовать свойства, которые являются относительно независимыми друг от друга. Наивный метод классификации Байеса, который мы обсудим далее, преодолевает это ограничение, позволяя всем свойствам действовать "параллельно".

5.1 Базовая вероятностная модель

Другой способ понимания наивного байесовского классификатора заключается в том, что он выбирает наиболее вероятную метку для входа, предполагая, что каждое входное значение генерируется сначала выбором метки класса для этого входного значения, а затем созданием каждого свойства, совершенно не зависимо от любого другого свойства. Конечно, это предположение нереально; свойства часто сильно зависят друг от друга. Мы вернемся к некоторым следствиям этого предположения в конце этого раздела. Это упрощающее предположение, известное как наивное байесовское предположение (или предположение независимости) делает гораздо проще объединение вклада различных свойств, так как нам не нужно беспокоиться о том, как они должны взаимодействовать друг с другом.

Рисунок 5.3: Байесовской сетевой график, иллюстрирующий генеративный процесс, который предполагается наивным байесовскоим классификатором. Для создания помеченного входа модель сначала выбирает метку для входа, затем генерирует каждое свойство входа на основе этой метки. Предполагается, что каждое свойство совершенно не зависит от любого другого свойства данной метки.

Исходя из этого предположения, можно вычислить выражение для P(метка | свойство), вероятность того, что вход будет иметь определенную метку при условии, что он имеет определенный набор свойств. Чтобы выбрать метку для нового входа, мы можем просто выбрать метку для нового входа l, которая максимизирует P(L | свойства).

Прежде всего, отметим, что P (метка | свойства) равна вероятности того, что вход имеет определенную метку и определенный набор свойств, деленной на вероятность того, что он имеет определенный набор свойств:

(2)

В (метка | свойства) = В (свойства, метка) / В (свойства)

Далее, мы замечаем, что P (свойства) будет одинаковым для каждого выбора метки, поэтому, если мы просто заинтересованы в нахождении наиболее вероятной метки, достаточно вычислить P (свойства, метка), которую мы будем называть вероятность метки.

Вероятность метки может быть представлена как вероятность метки умноженная на вероятность свойств данной метки:

(4)

В (свойства, метка) = В (метка) × В (свойства | метка)

Кроме того, поскольку все свойства не зависят друг от друга (для данной метки), мы можем выделить вероятность каждого отдельного свойства:

(5)

В (свойства, метка) = В (метка) × Prod с в | свойства В (с | метка)`

Это именно то уравнение, которое мы обсуждали выше для вычисления вероятности метки: В (метка) является априорной вероятностью для данной метки, а каждый из В (с | метка) представляет собой вклад одного свойства в вероятность метки.

5.2 Нулевые количества и сглаживание

Самый простой способ вычислить В (с | метка), вклад свойства с в вероятность метки для метка, состоит в том, чтобы взять процент учебных экземпляров с данной меткой, которые также имеют данное свойство:

(6)

В (с | метка) = кол-во (с, метка) / кол-во (метка)

Однако этот простой подход может стать проблематичным, когда свойство никогда не появляется с заданной метки в обучающем наборе. В этом случае наша расчетная величина для В (с | метка) будет равна нулю, что приведет к нулевой вероятности метки для данной метки. Таким образом, входу никогда не будет присвоен эта метка независимо от того, насколько хорошо другие свойства подходят этой метке.

Основная проблема здесь заключается в нашем расчете В (с | метка), вероятности того, что вход будет иметь некоторое свойство для данной метки. В частности, только то, что мы не видели сочетание свойство / метка в тренировочном наборе, не означает, что это сочетание невозможно. Например, мы не видели никаких документов о загадочных убийствах, содержащих слово "футбол", но мы не хотели бы сделать вывод, что это такие документы не могут существовать.

Таким образом, несмотря на то, что кол-во (с, метка) / кол-во (метка) является хорошей оценкой для В (с | метка), если кол-во (с, метка) является относительно большим, эта оценка становится менее надежной, когда кол-во (с) становится меньше. Таким образом, при построении наивных моделей Байеса для вычисления В (с | метка), вероятности свойства для данной метки, мы обычно используем более сложные методы, известные как методы сглаживания. Так, например, Ожидаемая Оценка Правдоподобия для вероятности свойства данной метки добавляет базовые 0,5 к каждому значению кол-во (с, метка), а Растянутая Оценка использует растянутый корпус для вычисления отношения между частотами свойств и их вероятностями. Модуль nltk.probability обеспечивает поддержку широкого спектра методов сглаживания.

5.3 Небинарные свойства

Мы предположили, что каждое свойство бинарно, то есть, что каждый вход либо имеет свойство, либо нет. Свойства с небинарными значениями (например, цветовое свойство, которое может быть красным, зеленым, синим, белым или оранжевым) могут быть преобразованы в бинарные свойства путем замены их бинарными свойствам, такими как "цвет-красный". Числовые свойства могут быть преобразованы в двоичных свойства с помощью биннинга, который заменяет их такими свойствами, как "4 <х <6".

Другой альтернативой является использование методов регрессии для моделирования вероятностей числовых свойств. Например, если мы предположим, что функция высоты имеет колоколообразную кривую распределения, то мы могли бы оценить В (высота | метка) нахождением среднего значения и дисперсии высот входов для каждой метки. В этом случае B (c = д | метка) не будет фиксированным значением, но будет изменяться в зависимости от значения д.

5.4 Наивность независимости

Причина, по которой наивные классификаторы Байеса называют "наивным", заключается в том, что они необоснованно предполагают, что все свойства независимы друг от друга для данной метки. В частности, почти все реальные проблемы содержат свойства с различной степенью зависимости друг от друга. Если бы мы должны были избегать каких-либо свойств, которые зависят друг от друга, было бы очень трудно построить хорошие наборы свойств, которые обеспечивают необходимую информацию для алгоритма машинного обучения.

Так что же происходит, когда мы игнорируем предположение о независимости и используем наивный байесовский классификатор со свойствами, которые не являются независимыми? Одна из проблем заключается в том, что классификатор может прийти к "двойному счету" - эффекту сильно связанных свойств, толкающему классификатор ближе к данной метке, чем это оправдано.

Чтобы увидеть, как это может произойти, рассмотрим классификатор пола имени, который содержит два идентичных свойства, с₁ и с₂. Другими словами, с₂ является точной копией с₁ и не содержит новой информации. Когда классификатор рассматривает входной сигнал, он будет учитывать вклад и с₁ и с₂ при выборе того, какую метку выбрать. Таким образом, информационному содержанию этих двух свойств будет придано больше веса, чем оно заслуживает.

Конечно, мы обычно не строим наивные классификаторы Байеса, которые содержат два одинаковых свойства. Однако мы строим классификаторы, которые содержат свойства, которые зависят друг от друга. Например, свойства заканчивается-на(а) и заканчивается-на(гласную) зависят друг от друга, потому что если входное значение имеет первое свойство, то оно должна также иметь и второе. Из-за свойств подобных этим дублированная информация может иметь больший вес, чем это оправдано обучающим набором.

5.5 Причина двойного счета

Причиной проблемы двойного счета является то, что в процессе обучения, вклады свойств вычисляются по отдельности; а при использовании классификатора для выбора метки нового входа эти вклады свойств объединяются. Одно из решений поэтому заключается в том, чтобы рассмотреть возможные взаимодействия между вкладами свойств во время обучения. Тогда мы могли бы использовать эти взаимодействия для корректировки вкладов отдельных свойств.

Для того, чтобы сделать это более точным, мы можем переписать уравнение для расчета вероятности метки, выделяя вклад каждого свойства (или метки):

(7)

В (свойства, метка) = w [метка] × Prod с | в | свойствах w [с, метка]

Здесь w [метка] - это "стартовый счет" для данной метки, а w [с, метка] - вклад данного свойства в вероятность этикетки. Мы называем эти значения w [метка] и w [с, метка] параметрами, или весами для данной модели. Используя наивный алгоритм Байеса, мы устанавливаем каждый из этих параметров независимо друг от друга:

(8)

w [метка] = В (метка)

(9)

ж [с, метка] = В (с | метка)

Однако в следующем разделе мы рассмотрим классификатор, который рассматривает возможные взаимодействия между этими параметрами при выборе их значений.

6.1 Модель максимальной энтропии

Модель классификатора на основе максимальной энтропии является обобщением модели, используемой наивным байесовским классификатором. Подобно наивной модели Байеса, классификатор максимальной энтропии вычисляет вероятность каждой метки при заданном значении входного значения путем перемножения параметров, которые применимы для входного значения и метки. Модель наивного классификатора Байеса определяет параметр для каждой метки, указав его априорную вероятность и параметр для каждой пары (свойство, метка) с указанием вклада индивидуальных свойств в вероятность метки.

В отличие от этого, модель классификатора максимальной энтропии оставляет пользователю решить, какие комбинации меток и свойств должны получать свои собственные параметры. В частности, можно использовать один параметр, чтобы связать свойство с более чем одной меткой; или связать более одного свойства с заданной меткой. Это иногда позволит модели "обобщать" некоторые различия между связанными метками или свойствами.

Каждая комбинация меток и свойств, которая получает свой собственный параметр называется совместным свойством. Обратите внимание, что совместные свойства - это особенности помеченных значений, в то время как (простые) свойства - это особенности непомеченых значений.

Как правило, совместные свойства, которые используются для построения модели максимальной энтропии, точно отражают те, которые используются наивной моделью Байеса. В частности, совместное свойство определено для каждой метки, что соответствует w[label], и для каждой комбинации (простого) свойства и метки, что соответствует w[f, label]. Для данных совместных свойств модели максимальной энтропии, оценка, которая присваивается метке для данного входа, - это просто произведение параметров, связанных с совместными свойствами, которые применяются к этому входу и метке:

(12)

P (вход, метка) = Prod совместные функции (вход, этикетка) ш [совместное особенность]

6.2 Максимизация Энтропия

Интуицией, которая мотивирует классификацию максимальной энтропии, является то, что мы должны построить модель, которая схватывает частоты отдельных совместных свойств не делая каких-либо необоснованных предположений. Пример поможет проиллюстрировать этот принцип.

Предположим, что нам поставлена ​​задача выбора правильного слова для смысла данного слова из списка десяти возможных смыслов (помеченных A-J). Сначала нам ничего больше не сказали об этом слове или этих смыслах. Есть много распределения вероятностей, которые мы могли бы выбрать для десяти значений, таких как:

Хотя любое из этих распределений могло бы быть правильным, мы, скорее всего, чтобы выберем распределение (i), потому что без какой-либо дополнительной информации нет никаких оснований полагать, что какое-либо значение слова более вероятно, чем другое. С другой стороны, распределения (ii) и (iii) отражают предположения, которые не поддерживаются тем, что мы знаем.

Один из способов схватить эту интуицию, сообщающую что распределение (i) является более "справедливым", чем два других, - сослаться на понятие энтропии. При обсуждении деревьев решений мы описали энтропию как меру "дезорганизованности" набора меток. В частности, если одна метка доминирует, то энтропия мала, но если метки распределены более равномерно, то энтропия высока. В нашем примере мы выбрали распределение (i), так как вероятности его меток равномерно распределены, другими словами, так как его энтропия высока. В общем случае, принцип Максимальной Энтропии гласит, что среди распределений, которые согласуются с тем, что мы знаем, мы должны выбрать распределение, энтропия которого является самой высокой.

Далее, предположим, что нам говорят, что значение A появляется с частотой 55%. Опять же есть много распределений, которые согласуются с этой новой информацией, таких как:

Но опять же, мы, скорее всего, выберем распределение, которое делает наименьшее количество необоснованных допущений - в данном случае распределение (v).

Наконец, предположим, что нам говорят, что слово «up» появляется в соседнем контекст 10% времени, и что, когда оно появляется в этом контексте, есть 80% вероятность того, что значение A или C будет использоваться. В этом случае мы придумать распределение "в ручную" будет труднее; однако мы можем убедиться, что следующее распределение выглядит соответствующим образом:

В частности, распределение согласуется с тем, что мы знаем: если мы сложим вероятности в колонке А, мы получаем 55%; если сложить вероятности строки 1, мы получаем 10%; и если мы складываем ячейки для значений А и С в строке +up, мы получаем 8% (или 80% +up случаев). Кроме того, остальные вероятности "равномерно распределены".

На протяжении этого примера мы ограничились распределениями, которые согласуются с тем, что мы знаем; среди них мы выбрали распределение с самой высокой энтропией. Это именно то, что делает классификатор максимальной энтропии. В частности, для каждого совместного свойства модель максимальной энтропии вычисляет "эмпирическую частоту" этого свойства - т. е. частоту, с которой он встречается в обучающем наборе. Затем он осуществляет поиск распределения, которое максимизирует энтропию, в то же время предсказывая правильную частоту для каждого совместного свойства.

6.3 Генеративные против условных классификаторов

Важное различие между наивным байесовским классификатором и классификатором максимальной энтропии связано с типом вопросов, для ответа на которые они могут быть использованы. Наивный байесовский классификатор является примером порождающего классификатора, который строит модель, которая предсказывает P (input, label), совместную вероятность пары (вход, метка). Поэтому порождающие модели могут быть использованы, чтобы ответить на следующие вопросы:

1. Какая метка является наиболее вероятной для данного входа?
2. Насколько вероятна данная метка для данного входа?
3. Каково наиболее вероятное значение входного сигнала?
4. Насколько вероятно заданное значение входного сигнала?
5. Насколько вероятно данное входное значение для данной метки?
6. Какова наиболее вероятная метка для входа, который мог бы иметь одно из двух значений (но мы не знаем какое)?

Классификатор максимальной энтропии, с другой стороны, является примером условного классификатора. Условные классификаторы строят модели, предсказывающие P (label | input) - вероятность метки для данного входного значения. Таким образом, условные модели также могут быть использованы для ответа на вопросы 1 и 2. Однако условные модели не могут быть использованы, чтобы ответить на оставшиеся вопросы 3-6.

В целом порождающие модели строго мощнее условных моделей, так как мы можем вычислить условную вероятность В (метка | вход) от совместной вероятности В (вход, метка), но не наоборот. Однако эта дополнительная мощность поставляется по определенной цене. Поскольку модель является более мощной, она имеет более "свободные параметры", которые должны быть изучены. Однако размер обучающего набора фиксирован. Поэтому при использовании более мощной модели мы в конечном итоге оказываемся с меньшим количеством данных, чем может быть использовано для обучения, что делает труднее нахождение оптимальных значений параметров. В результате порождающая модель может работать не так хорошо при ответе на вопросы 1 и 2, как условная модель, так как условная модель может сосредоточить свои усилия на этих двух вопросах. Однако если нам действительно нужны ответы на такие вопросы, как 3-6, то у нас нет иного выбора, кроме как использовать порождающую модель.

Различие между порождающей моделью и условной моделью аналогична различию между топографической картой и изображением горизонта. Хотя топографическая карта может быть использована, чтобы ответить на более широкий круг вопросов, сформировать точную топографическую карту значительно труднее, чем создать точную линию горизонта.

7.1 Что модели говорят нам?

Важно понять, что мы можем узнать о языке из автоматически построенной модели. Одним из важных моментов при работе с моделями языка является различие между описательными моделями и объясняющими моделями. Описательные модели схватывают закономерности в данных, но они не дают никакой информации о том, почему данные содержат эти закономерности. Например, как мы видели в разделе 3.1, синонимы absolutely и definitely не являются взаимозаменяемыми: мы говорим absolutely adore, а не definitely adore и definitely prefer, а не absolutely prefer. В противоположность этому, объясняющие модели пытаются схватить свойства и отношения, которые вызывают языковые закономерности. Например, мы могли бы ввести абстрактное понятие "полярного глагола", как такого, который имеет экстремальное значение, и классифицировать некоторые глаголы, как adore и detest, как полярные. Наша объясняющая модель содержала бы ограничение, что absolutely можно комбинировать только с полярными глаголами, а definitely можно комбинировать только с неполярными глаголами. Таким образом описательные модели предоставляют информацию о корреляциях в данных, в то время как объясняющие модели идут дальше, чтобы постулировать причинно-следственные связи.

Большинство моделей, которые автоматически построены из корпуса, являются описательными моделями; другими словами, они могут сказать нам, какие свойства имеют отношение к заданному паттерну или конструкции, но они не всегда могут сказать нам, как эти свойства и паттерны связаны друг с другом. Если наша цель состоит в том, чтобы понять языковые закономерности, то мы можем использовать эту информацию о том, какие свойства связаны, в качестве отправной точки для дальнейших экспериментов, сконструированных для выискивания отношений между свойствами и закономерностями. С другой стороны, если мы просто заинтересованы в использовании модели для прогнозирования (например, как части системы обработки языка), то мы можем использовать модель для составления прогнозов о новых данных, не заботясь о деталях лежащего в основе причинно-следственного отношения.