(Часть 1) Сегодня мы поговорим об уровнях понимания текстов нашей системой, о том, какие ошибки правописания отловить просто, какие не очень просто, а какие запредельно сложно.
Начнём с того, что текст можно рассматривать с двух точек зрения: либо как простую последовательность слов, пробелов и знаков препинания, либо как сеть связанных между собой синтактико-семантическими зависимостями понятий. Скажем, в предложении «я люблю больших собак» можно расставить слова в любом порядке, при этом структура связей между словами будет одна и та же:
Ошибки тоже могут возникать на разных уровнях. Можно ошибиться в линейной структуре — дважды напечатать одно и то же слово, забыть точку, круглую скобку и тому подобные вещи. То есть ошибка возникает в процессе выстраивания слов в цепочку, и человек вряд ли совершает её по незнанию какого-либо грамматического правила. Вероятно, речь идёт о простой невнимательности. Впрочем, на уровне цепочек можно выявить и некоторые настоящие грамматические ошибки. Скажем, в английском тексте не должно встречаться сочетаний «was been» — должно быть либо «was», либо «has been».
Но всё-таки настоящая грамматика начинается на уровне анализа сети понятий. Скажем, в нашем примере про собак подлежащее «я» должно сочетаться в лице и числе с глаголом «люблю» независимо от взаимного расположения этих слов в предложении. Разумеется, это соображение не отменяет необходимости отлавливать и более простые ошибки, выявленные на уровне линейной структуры.
Немногим сложнее простые правила на основе регулярных выражений, рассматривающие текст как одну большую строку. На сегодняшний день мы отлавливаем регулярными выражениями простые ситуации, связанные с типографическими шероховатостями: пробел(ы) между знаками препинания, лишние пробелы между словами, нестандартные сочетания вроде "!?" и так далее. В принципе, даже на уровне простого поиска подстрок можно найти некоторое количество ошибок, пропускаемых спелл-чекером.
Как и всё в нашем мире, со второго взгляда задача разбиения текста на предложения уже не кажется столь простой. Очевидный алгоритм состоит в поиске завершающего предложение знака препинания, за которым следует заглавная буква. При этом мы будем ошибаться, встретив имя человека: «Как заявил М. Иванов, ...» Аналогичным образом на пути встают сокращения, в которых встречается точка. В принципе, можно добавить в анализатор список имён и сокращений, но это решение всё равно не будет лишено недостатков. Например, его придётся полностью переписывать для любого нового языка, где действуют свои правила окончания предложений. Кроме того, существует очевидная неувязка: мы ведь исходим из того, что входной текст содержит ошибки (в их исправлении и суть нашего модуля); так как же в условиях некорректного входа разбивать текст на предложения? В этом случае мы автоматически теряем возможность увидеть ошибку на стыке предложений. Если считать, что граница пролегает между точкой и заглавной буквой, то ошибка вида «забыли поставить заглавную букву» сразу окажется вне досягаемости, ибо система попросту не поймёт, что в данном месте находится граница предложений.
Сейчас наиболее популярные подходы к разбиению текста на предложения в реальных условиях заключаются в использовании алгоритмов классификации на основе machine learning.
Хрестоматийный пример задачи классификации — определение вида цветка ириса на основе четырёх параметров — длины и ширины лепестка и чашелистика. Существует три вида ириса: Iris setosa, Iris virginica и Iris versicolor. В наборе данных Iris перечислено 50 записей следующего вида:
Алгоритм классификации может изучить эти данные и построить модель соответствия атрибутов ириса тому или иному конкретному виду. Если у меня в саду растёт неизвестный мне ирис, я могу измерить его параметры и спросить у алгоритма, к какому виду мой ирис принадлежит.
Классификатор может использоваться и для других целей: принятие решения на основе таблицы эталонных решений в условиях тех или иных обстоятельств, а также выявление скрытых закономерностей — ещё один хрестоматийный пример предполагает изучение «атрибутов» выживших при крушении Титаника пассажиров с тем, чтобы понять, каковы были шансы различных групп людей (ребёнок/взрослый, мужчина/женщина, пассажир/член команды, владелец билета 1/2/3 класса).
Существует масса различных алгоритмов классификации: decision trees, nearest neighbor, bayesian network, maximum entropy model, linear regression… Каждый имеет свои достоинства и недостатки. Некоторые лучше работают с числовыми данными, другие проще программировать, третьи скоростнее, четвёртые формулируют выявленные правила классификации в удобном для анализа виде.
Применительно к разбиению текста на предложения классификатор работает следующим образом. На вход поступает текст, разбитый на предложения вручную. Система изучает «атрибуты» каждого конца предложения (фактически, смотрит, что находится слева и справа от границы) и строит модель классификации. Теперь на вход алгоритму можно подать любую точку текста и спросить, является ли она границей предложения.
Какие здесь есть тонкости? Во-первых, здесь мы имеем не совсем стандартную постановку задачи классификации. У нас на входе получаются только контексты концов предложения:
(A1, ..., An) -> (конец предложения)
В классической постановке база знаний должна включать в себя все варианты, т.е.:
(A1, ..., An) -> (конец предложения)
(A1, ..., An) -> (не конец предложения)
В нашем случае впихивать в таблицу все примеры не-концов предложения слишком разорительно — база разрастётся неимоверно. Видимо, по этой причине самый часто цитируемый автор machine learning-схемы (применительно к нашей задаче) A. Ratnaparkhi использовал принцип максимальной энтропии. Эта модель позволяет просто спросить вероятность принадлежности объекта к данному классу вне связи с другими возможными классами. Иначе говоря, мы спрашиваем у модели, какова вероятность данного контекста быть концом предложения. Если алгоритм отвечает, что вероятность выше 1/2, можно отметить контекст как границу предложений.
Я думаю, что имеет смысл испробовать и другие алгоритмы классификации. Насколько знаю, этого не было сделано; если руки дойдут — займусь. Эксперименты же Ratnaparkhi показывают точность его алгоритма в районе 98%, то есть из ста концов предложений он угадывает 98 правильно.
К сожалению, в модуле проверки правописания мы снова сталкиваемся с тем, что входной текст может содержать ошибки. Если натренировать модель на разбитых на предложения корректных текстах, компьютер справедливо решит, что предложение всегда начинается с заглавной буквы. Если же выбросить «заглавность» из учитываемых атрибутов, точность модели упадёт. Можно вручную внести несколько ошибок в эталонные тексты (кое-где «забыть» точку, кое-где заменить заглавную букву строчной). Далее, в системе Ratnaparkhi мы сначала должны найти потенциальную границу предложений, а потом уже спросить систему о её мнении относительно этого места. У него это делается просто: ищем точку, восклицательный или вопросительный знак — и спрашиваем, что здесь такое. У нас же пользователь может забыть о точке — и что делать?
На сегодняшний день помимо знаков препинания я проверяю ещё символы перевода строки (по личному опыту — если я где и забываю поставить точку, так это в конце абзаца). Можно попытаться изучать все пробелы между словами, но боюсь, что точность может упасть. В общем, здесь есть о чём подумать :)
Ладно, на сегодня хватит, продолжим в следующий раз.
Начнём с того, что текст можно рассматривать с двух точек зрения: либо как простую последовательность слов, пробелов и знаков препинания, либо как сеть связанных между собой синтактико-семантическими зависимостями понятий. Скажем, в предложении «я люблю больших собак» можно расставить слова в любом порядке, при этом структура связей между словами будет одна и та же:
Ошибки тоже могут возникать на разных уровнях. Можно ошибиться в линейной структуре — дважды напечатать одно и то же слово, забыть точку, круглую скобку и тому подобные вещи. То есть ошибка возникает в процессе выстраивания слов в цепочку, и человек вряд ли совершает её по незнанию какого-либо грамматического правила. Вероятно, речь идёт о простой невнимательности. Впрочем, на уровне цепочек можно выявить и некоторые настоящие грамматические ошибки. Скажем, в английском тексте не должно встречаться сочетаний «was been» — должно быть либо «was», либо «has been».
Но всё-таки настоящая грамматика начинается на уровне анализа сети понятий. Скажем, в нашем примере про собак подлежащее «я» должно сочетаться в лице и числе с глаголом «люблю» независимо от взаимного расположения этих слов в предложении. Разумеется, это соображение не отменяет необходимости отлавливать и более простые ошибки, выявленные на уровне линейной структуры.
Первые уровни
Вполне разумно начинать проверку ошибок с самых простых. Если что-то можно отловить на уровне банального поиска подстрок, зачем подклчюать тяжёлую артиллерию? Самая простая функциональность — это список автозамены, существующий и в MS Word. Речь идёт об очевидных опечатках, исправляемых системой автоматически, даже без подтверждения пользователя: abbout -> about, amde -> made, compleatly -> completely. Быть может, автозамена кажется настолько очевидной функцией, что вроде бы и говорить о ней смысла нет, однако мне как активному пользователю MS Word автозамена частенько помогает, и я буду рад видеть автозамену и в других текстовых процессорах. Для этого и работаем, в конце концов.Немногим сложнее простые правила на основе регулярных выражений, рассматривающие текст как одну большую строку. На сегодняшний день мы отлавливаем регулярными выражениями простые ситуации, связанные с типографическими шероховатостями: пробел(ы) между знаками препинания, лишние пробелы между словами, нестандартные сочетания вроде "!?" и так далее. В принципе, даже на уровне простого поиска подстрок можно найти некоторое количество ошибок, пропускаемых спелл-чекером.
Предложения и токены
Вот теперь мы переходим к более интересным вещам. Для того, чтобы анализировать текст именно как текст, а не как строку символов, необходимо научиться выделять в нём структурные элементы. До структуры связей между словами нам пока ещё далеко, так что начнём с самой простой вещи — с распознавания границ предложений. Для чего нам это нужно? Ну, во-первых, существуют ошибки, характерные именно для начала и конца предложения: забыли начать с заглавной буквы, забыли поставить в конце точку (многоточие, вопросительный/восклицательный знаки). Есть и менее очевидные случаи — например, стилистически недопустимо начинать предложение с числа, записанного цифрами. Во вторых, без имеющейся структуры предложений невозможно перейти к следующему этапу анализа — к выявлению связей между словами предложения.Как и всё в нашем мире, со второго взгляда задача разбиения текста на предложения уже не кажется столь простой. Очевидный алгоритм состоит в поиске завершающего предложение знака препинания, за которым следует заглавная буква. При этом мы будем ошибаться, встретив имя человека: «Как заявил М. Иванов, ...» Аналогичным образом на пути встают сокращения, в которых встречается точка. В принципе, можно добавить в анализатор список имён и сокращений, но это решение всё равно не будет лишено недостатков. Например, его придётся полностью переписывать для любого нового языка, где действуют свои правила окончания предложений. Кроме того, существует очевидная неувязка: мы ведь исходим из того, что входной текст содержит ошибки (в их исправлении и суть нашего модуля); так как же в условиях некорректного входа разбивать текст на предложения? В этом случае мы автоматически теряем возможность увидеть ошибку на стыке предложений. Если считать, что граница пролегает между точкой и заглавной буквой, то ошибка вида «забыли поставить заглавную букву» сразу окажется вне досягаемости, ибо система попросту не поймёт, что в данном месте находится граница предложений.
Сейчас наиболее популярные подходы к разбиению текста на предложения в реальных условиях заключаются в использовании алгоритмов классификации на основе machine learning.
Sentence splitter
Коротко говоря, задача классификации состоит в том, чтобы определить корректный класс объекта C на основе его атрибутов (A1, ..., An). На вход обучающемуся алгоритму даётся большая выборка известных объектов, на основе которой он формирует своё представление о том, как значения атрибутов влияют на принадлежность объекта к тому или иному классу. Затем можно подать на вход алгоритму набор атрибутов неизвестного объекта и получить наиболее вероятный его класс.Хрестоматийный пример задачи классификации — определение вида цветка ириса на основе четырёх параметров — длины и ширины лепестка и чашелистика. Существует три вида ириса: Iris setosa, Iris virginica и Iris versicolor. В наборе данных Iris перечислено 50 записей следующего вида:
Алгоритм классификации может изучить эти данные и построить модель соответствия атрибутов ириса тому или иному конкретному виду. Если у меня в саду растёт неизвестный мне ирис, я могу измерить его параметры и спросить у алгоритма, к какому виду мой ирис принадлежит.
Классификатор может использоваться и для других целей: принятие решения на основе таблицы эталонных решений в условиях тех или иных обстоятельств, а также выявление скрытых закономерностей — ещё один хрестоматийный пример предполагает изучение «атрибутов» выживших при крушении Титаника пассажиров с тем, чтобы понять, каковы были шансы различных групп людей (ребёнок/взрослый, мужчина/женщина, пассажир/член команды, владелец билета 1/2/3 класса).
Существует масса различных алгоритмов классификации: decision trees, nearest neighbor, bayesian network, maximum entropy model, linear regression… Каждый имеет свои достоинства и недостатки. Некоторые лучше работают с числовыми данными, другие проще программировать, третьи скоростнее, четвёртые формулируют выявленные правила классификации в удобном для анализа виде.
Применительно к разбиению текста на предложения классификатор работает следующим образом. На вход поступает текст, разбитый на предложения вручную. Система изучает «атрибуты» каждого конца предложения (фактически, смотрит, что находится слева и справа от границы) и строит модель классификации. Теперь на вход алгоритму можно подать любую точку текста и спросить, является ли она границей предложения.
Какие здесь есть тонкости? Во-первых, здесь мы имеем не совсем стандартную постановку задачи классификации. У нас на входе получаются только контексты концов предложения:
(A1, ..., An) -> (конец предложения)
В классической постановке база знаний должна включать в себя все варианты, т.е.:
(A1, ..., An) -> (конец предложения)
(A1, ..., An) -> (не конец предложения)
В нашем случае впихивать в таблицу все примеры не-концов предложения слишком разорительно — база разрастётся неимоверно. Видимо, по этой причине самый часто цитируемый автор machine learning-схемы (применительно к нашей задаче) A. Ratnaparkhi использовал принцип максимальной энтропии. Эта модель позволяет просто спросить вероятность принадлежности объекта к данному классу вне связи с другими возможными классами. Иначе говоря, мы спрашиваем у модели, какова вероятность данного контекста быть концом предложения. Если алгоритм отвечает, что вероятность выше 1/2, можно отметить контекст как границу предложений.
Я думаю, что имеет смысл испробовать и другие алгоритмы классификации. Насколько знаю, этого не было сделано; если руки дойдут — займусь. Эксперименты же Ratnaparkhi показывают точность его алгоритма в районе 98%, то есть из ста концов предложений он угадывает 98 правильно.
К сожалению, в модуле проверки правописания мы снова сталкиваемся с тем, что входной текст может содержать ошибки. Если натренировать модель на разбитых на предложения корректных текстах, компьютер справедливо решит, что предложение всегда начинается с заглавной буквы. Если же выбросить «заглавность» из учитываемых атрибутов, точность модели упадёт. Можно вручную внести несколько ошибок в эталонные тексты (кое-где «забыть» точку, кое-где заменить заглавную букву строчной). Далее, в системе Ratnaparkhi мы сначала должны найти потенциальную границу предложений, а потом уже спросить систему о её мнении относительно этого места. У него это делается просто: ищем точку, восклицательный или вопросительный знак — и спрашиваем, что здесь такое. У нас же пользователь может забыть о точке — и что делать?
На сегодняшний день помимо знаков препинания я проверяю ещё символы перевода строки (по личному опыту — если я где и забываю поставить точку, так это в конце абзаца). Можно попытаться изучать все пробелы между словами, но боюсь, что точность может упасть. В общем, здесь есть о чём подумать :)
Ладно, на сегодня хватит, продолжим в следующий раз.
