НАУЧНЫЕ ОСНОВЫ КОМПЬЮТЕРНОЙ ЛИНГВИСТИКИ

 

 

Логико-математические основы компьютерной лингвистики

  • Современная математика в периодизации А. Колмогорова

  • Логические и лингвистические проблемы современной математики

  • Языки формальной логики

  • Математическая логика

  • Формальные грамматики. Исчисления

  • Предикаты. Нечетка логика

  • Лингвистические вычисления

  • Проблема вычислимости и сложности

  • Математическая лингвистика

  • Компьютер как языковая машина

  • Лингвистические проблемы компьютерных наук

  • Идеи А. Тьюринга, А. Чёрча, А.Н. Колмогорова, А.А. Маркова

  • Математические выражения грамматик Хомского

  • Формальные языки

  • Языки программирования и разметки

 

Языковые и логические проблемы математики

Колмогоров Андрей Николаевич (1903-1987) — советский математик, один из крупнейших математиков ХХ века.

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

К определению падежа по А. Н. Колмогорову

Модельное стиховедение А.Н. Колмогорова

Математические модели текста

Периодизация математики (по Колмогорову А.Н.):

  • Период элементарной математики VI век до Р.Х. - XVII век

  • Период высшей математики XVII-XVIII века

  • Период современной математики XIX—XX века

Период современной математики открыт необходимостью:

  • «отнестись к процессу расширения предмета математических исследований сознательно»

  • Задуматься о логических основаниях математики

  • Задуматься о ее языковых основаниях

В современной математике первостепенное внимание вопросам:

  • "обоснования" математики,

  • ее исходных понятий и аксиом,

  • системы определений и доказательств,

  • алгоритмической (не-) разрешимости.

Колмогоров Андрей Николаевич (великий математик):

Математический метод всегда следует двум принципам:

  1. Обобщение (абстрагирование). Объекты изучения в математике — это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды.

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

Чтобы изучать с помощью математических методов лингвистические объекты (языки, тексты...) , необходимо:

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

  • строго определить эти свойства.

Полученная таким образом абстракция будет математической моделью реального объекта (формальным языком, векторной моделью текста и проч.).

 

Математическая лингвистика:

  • Разрабатывает формальный аппарат для описания строения языков (естественных, искусственных, программирования)

  • Возникла в 50-х г связи с потребностью уточнения основных понятий языкознания

  • Использует идеи и методы алгебры, алгоритмов теории и автоматов теории.

Развитие математики и логики привело в XX в к:

  • постановке вопросов о возможностях и ограничениях языков описания реальности…

  • проблематике их формализации

  • необходимости и возможности языковых вычислений…

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

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

 

Рекомендуется к прочтению:

  • Густаво Эрнесто Пинейро Бесчисленное поддается подсчету. Кантор. Бесконечность в математике

  • Альфред Тарский Семантическая концепция истины  и основания семантики

 

 

 

 

Логика и математика

 

Логика - наука о правильных формах рассуждений.

Основы логики развил Аристотель в IY веке до Р.Х.

Идеи построения математической логики высказал Готфрид Вильгельм Лейбниц в начале XYIII века

Создание математической (символической) логики как универсального научного языка рассматривал Готфрид Вильгельм Лейбниц
в 1666 году в работе «Искусство комбинаторики» (De arte combinatoria).

Джон Буль в 40-х годах XIX в. превратил логику в математическую, создав алгебру, в которой высказывания обозначались буквами...

Бертран Рассел и Альфред Норт Уайтхед в «Началах математики» (1910—1913) доказали:

  • соответствие принципов математики принципам логики

  • возможность определения основных понятий математики в терминах логики

  • Логика изучает формы мышления неразрывно связаного с языком…

Логика - необходимое условие решения научных, технических, информационных задач.

Логика важна практически во всех жизненных ситуациях с технологическом обществе.

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

Логика является инструментом обоснования, осмысления и оценки окружающиго мир и самого себя.

 

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

Основная функция логики - исследовать утверждения и правила умозаключений.

kmp рекомендует: Г.В.Ф. Гегель Наука логики

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

Логика приобретается человеком в процессе его социализации в технологическом обществе и специального обучения.

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

 

Логические умозаключения могут противоречить нравственности и праву.  

Логическое мышление может стать основанием для совершения антигуманных поступков.

 

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

 

 

 

Логика, язык, вычисления

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

Идею о возможности математизации логики высказал еще в XVII веке Г.В.Лейбниц.

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

Однако, подлинный прогресс этой науки был достигнут в середине XIX века прежде всего благодаря трудам Дж.Буля "Математический анализ логики". Он перенес на логику законы и правила алгебраических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В трудах Дж.Буля и Д.Моргана математическая логика оформилась как своеобразная алгебра - алгебра логики (или алгебра высказываний).

В развитии математической логики приняли участие выдающиеся математики и логики конца XIX и XX веков, в том числе К.Гедель (австр.), Д.Гильберт (нем.), С.Клини (амер.), Э.Пост (амер.), А.Тьюринг (анг.), А.Чёрч (амер.), А.Н.Колмогоров, П.С.Новиков, А.А.Марков и многие другие.

Современная математизированная формальная логика находит широкое применение как внутри математики (исследование оснований математики), так и вне ее (автоматическая обработка текста и речи, теоретическая информатика, искусственный интеллект).

Алгоритм решения логических задачпри помощи алгебры высказываний

  1. внимательно изучить условие;

  2. выделить простые высказывания и обозначить их латинскими буквами;

  3. записать условие задачи на языке алгебры логики;

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

  5. упростить формулу;

  6. проанализировать полученный результат;

  7. найти по таблице истинности значения переменных;

  8. проанализировать результаты.

Алгоритм построения таблицы истинности

  1. подсчитать количество переменных n в логическом выражении;

  2. определить число строк в таблице по формуле m=2n, где n - количество переменных;

  3. подсчитать количество логических операций в формуле;

  4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;

  5. определить количество столбцов: число переменных + число операций;

  6. выписать наборы входных переменных;

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

Алгебры высказываний:

  • Логика высказываний… (исчисление, 0 порядок)

  • Логика предикатов (кванторов 1 порядка…)

  • Логики кванторов высших порядков…

  • Многозначные логики

  • Нечеткие логики… (Лотфи Заде)

  • ………………..

  • Алгебра категорий…..

Вычислительная математика - наука о вычислениях.

Вычисления - нахождения решений аналитических моделей средствами формальных преобразований.

Формальные преобразования предполагают использование формальных языков.

 

Алан Тьюринг (1936) ввел понятие абстрактной вычислительной машины – «Машины Тьюринга» и доказал фундаментальную теорему:

  • Для любого "вычислимого" процесса машина Тьюринга  может быть построена; она когда-нибудь остановится и выдаст (однозначное!) решение. Для "невычислимых" процессов …. Неизвестно…

Алан Тьюринг: «Модель математического текста есть машина, а не текст».

Алонзо Чёрч (1936) создал аппарат рекурсивных функций формализовавший понятие алгоритма. 

Все универсальные вычислительные устройства качественно эквивалентны.

 

Рекомендуется к прочтению:

Манин Юрий Иванович (основоположник некоммутативной алгебраической геометрии и квантовой информатики. Член-корр. РАН, член Королевской академии наук Нидерландов, Гёттингенской академии наук, академии «Леопольдина», Французской академии наук, Американской академии искусств и наук, почётный доктор Сорбонны, Университета Осло и проч.):

  • Математика как метафора

 

 

 

Формальные языки и грамматики

Формальный язык — это математическая модель реального языка.

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

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

Формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита.

Алфавит представляет собой конечное непустое множество элементов (символов). Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов.

Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

 

Формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V.

 

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

 

 

Грамматика - любой конечный способ задания языка.

Например, грамматика L = {a^nb^n} (здесь n — натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д.

Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

Грамматика языка описывает законы внутреннего строения его цепочек (синтаксические закономерности).

Грамматика - конечный способ описания синтаксических закономерностей языка.

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

Формальная грамматика — это математическая модель грамматики, описанная в рамках какой-то синтаксической теории.

Таких теорий придумано довольно много.

Самый известный метаязык для задания грамматик — порождающие грамматики Хомского.

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

  • Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» — в противном случае

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

  • Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

 

 

Порождающие грамматики Хомского

Грамматика - конечное описание формального языка.

Формальный язык - произвольным множеством цепочек, составленных из символов некоторого конечного алфавита.

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

Формализм порождающих грамматик Хомского введен Ноамом Хомским в конце 50-х годов 20 века.

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

Порождающая грамматика Хомского задается как множество «правил порождения» (продукций). Каждое правило является просто парой цепочек (w', w'') и задает возможность замены левой цепочки на правую при генерации цепочек языка, задаваемого грамматикой. По этой причине, правила обычно записывают в виде w' --> w'', указывая конкретно, что на что можно заменять. Множество правил в грамматике должно быть непустым и конечным, и обычно обозначается латинской P.

Цепочки в правилах грамматики могут быть составлены из символов двух алфавитов:

  • алфавита терминальных символов (терминалов)

  • алфавита нетерминальных символов (нетерминалов).

Алфавит терминалов обозначают через T. Этот алфавит на самом деле совпадает с алфавитом того формального языка, который задает данная грамматика.

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

Нетерминальные символы используются в промежуточных порождениях цепочек.

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

Один нетерминальный символ всегда имеет один и тот же смысл — он обозначает все цепочки языка. Называется этот нетерминал «начальным нетерминальным символов порождающей грамматики» и обычно обозначается посредством латинского S (start или sentence). В каждой порождающей грамматике обязательно должно быть правило, к которого левая часть состоит из единственного начального нетерминала, иначе в данной грамматике нельзя будет породить даже одной цепочки.

 

Прождающая грамматика Хомского — это четверка G = {N, T, P, S}, где:

  • N — конечный алфавит нетерминальных символов.

  • T — конечный алфавит терминальных символов
    (совпадает с алфавитом языка, задаваемого грамматикой).

  • P — конечное множество правил порождения.

  • S — начальный нетерминал грамматики G.

 

Порождающая грамматика Хомского задает язык посредством конечного числа подстановок цепочек из начального нетерминала грамматики на основе правил порождения.

 

Язык порождающей грамматики G = {N, T, P, S} — это множество цепочек, составленных из терминальных символов и порожденных из начального символа грамматики.

Математическая формула: L = {w | S =>* w}

 

Примеры языков:

  • L = {a}
    я    зык     L состоит из одной цепочки, которая состоит из единственного символа a. .
    Для порождения цепочки     a достаточно одного правила S --> a.

  • A = {a+a, a+a+a, a+a+a+a, ...}.
    Цепочки языка     A представляют собой последовательности символов a, разделенных символами +. Каждая цепочка языка начинается с символа a за которым идет одна или более цепочек +a. Введем нетерминальный символ A и получим грамматику со следующими правилами: S --> aA, A --> +aA, A --> +a.
    Рассмотрим, например, как можно породить цепочку     a+a+a. S => aA => a+aA => a+a+a.
    В этом порождении последовательно были применены все три правила:     S --> aA, A --> +aA, A --> +a.
    Язык     A содержит бесконечное число цепочек, значит, ограничения на длину цепочки в этом языке нет. Единственный способ порождать цепочки неограниченной длины, это использовать рекурсивные правила порождения, т.е. правила, в которых в правой части правила содержится его левая часть. В примере выше это правило A --> +aA. Левая часть — это цепочка из единственного символа A, который также содержится и в правой части. Такая рекурсия позволяет последовательно применять в подстановке одно и то же правила, увеличивая, сколько необходимо, длину порождаемой цепочки. Рекурсия может быть и опосредованной, через промежуточные правила. Например, правила A --> aBc, B --> deA задают опосредованную рекурсию цепочки A.

Ноам Хомский ввел классы грамматик (и соответствующие классы языков) задавая ограничения на вид правил порождающей грамматики. Каждый класс грамматик имеет свою описательную мощность (возможность выражений в правилах грамматики определенных синтаксических отношений).

  • Грамматики типа 3 задают синтаксическое отношение «быть рядом» (непосредственно рядом и опосредованно рядом, через нетерминальные символы в связанных между собой правилах порождения). Грамматика типа 3 похожа на попрождающий автомат, в котором роль состояний играют нетерминальный символы грамматики. Одна из возможных интерпретаций этой грамматики — конечный автомат.

  • Контекстно-свободные грамматики задают два вида синтаксических отношений: отношение «быть рядом» и отношение «быть частью» или отношение иерархии. КС-грамматика может быть проинтерпретирована как категориальная грамматика, т.е. грамматика типов. КС-грамматики часто используется при создании трансляторов языков. Ввиду того, что КС-грамматика является порождающей, она задает алгоритм (строго говоря, не алгоритм, но исчисление — многовариантный алгоритм) порождения цепочек языка. 

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

 

 

 

Цепи Маркова

 

Марков Андрей Андреевич (1856-1922) — выдающийся русский математик, академик, внёсший большой вклад в теорию вероятностей, математический анализ и теорию чисел.

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

Цепь Маркова - последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s-ом испытании наступит событие Aj при условии, что в (s - 1) - ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний

В однородной цепи Маркова условная вероятность pij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность pij называется переходной вероятностью.

О математической модели Цепей Маркова здесь.

Пример использования цепи Маркова

 

Если очень просто:

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

Стишок:

Из-за леса, из-за гор
едет дедушка Егор:
сам на лошадке,
жена на коровке,
дети на телятках,
внуки на козлятках.

Разберем текст на звенья и связки:

из-за [леса, гор]
леса [из-за]
гор [едет]
едет [дедушка]
дедушка [Егор]
Егор [сам]
сам [на]
на [лошадке, коровке, телятках, козлятках]
лошадке [жена]
жена [на]
коровке [дети]
дети [на]
телятках [внуки]
внуки [на]

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

При генерации текста из списка звеньев на первой итерации (организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя):

  • выбирается случайное звено,

  • определяются его связи,

  • из списка связей выбирается случайная и

  • принимается уже как новое звено.

Затем действие повторяется до достижения нужного размера текста. В результате, например, может получиться что-то подобное:

Егор сам на телятках внуки на лошадке жена на коровке дети на коровке

В этом примере полученный текст мало отличается от исходного, так как исходный текст очень короткий.

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

 

 

Алгоритм

 

Загружается файл *.txt с текстом в кодировке Windows-1251.

Из файла удаляются лишние пробелы и все символы, кроме букв и некоторых знаков препинания.

Полученный чистый текст разделяется на отдельные слова (звенья цепи).

Определяются связи слов (их возможные последовательные цепочки).

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

Выполняется генерация текста по алгоритму с проверками от зацикливания.

 

 

 

PHP — рекурсивный акроним (PHP: Hypertext Preprocessor)

PHP — скриптовый язык программирования для разработки веб-приложений и динамических веб-сайтов.

 

 

Код реализации автогенератора текста

 (на PHP с использованием цепей Маркова)

 

 

Code: php

// Прочитать исходный текст, на основе которого будет генерироваться новый
$str=file_get_contents('markov.txt');

// Установить кодировку системы
setlocale(LC_ALL, 'ru_RU.CP1251');

// Убрать из текста символы кроме цифр, букв и некоторых знаков препинания
$str=eregi_replace('[^-a-zа-я0-9 !\?\.\,]',' ',$str);

// Подчистить пробелы перед окончаниями предложений
$str=eregi_replace(' {1,}([!\?\.\,])','\\1',$str);

// Поделить текст на слова
$tmp=preg_split('/[[:space:]]+/is',$str);

// Массив "звеньев"
$words=Array();

// Заполнить звенья
for($i=0; $i<count($tmp); $i++) {
    if ($tmp[$i+1]!='') {
        $words[$tmp[$i]][]=$tmp[$i+1];
    }
}
$words=array_map('array_unique',$words);

// Массив начальных слов в предложениях
$start=Array();

foreach($words as $word=>$links) {
    if (ereg('^[А-Я][а-я]+',$word)) {
        $start[]=$word;
    }
}

// Сгененировать 100 предложений на основе исходного текста
for ($i=0; $i<100; $i++) {
    while (true) {
        $w=$start[rand(0,(count($start)-1))];
        if (ereg('[\.!\?]$',$w)) { continue; }
        $sentence=$w.' ';
        // Количество слов в предложении
        $cnt=1;
        // Сгенерировать предложение
        while(true) {
            $links=$words[$w];
            // Переключить цепочку
            $w=$words[$w][rand(0,(count($words[$w])-1))];
            $sentence.=$w.' ';
            // Если слово находилось в конце предложения
            if (ereg('[\.!\?]$',$w)) { break; }
            $cnt++;
            // Если генератор зациклился, то принудительно выйти
            if ($cnt>19) { break; }
        }
        // Удачным считать  предложение длиной 5-20 слов
        if ($cnt>5 && $cnt<20) { break; }
    }
    // Сгенерированное предложение
    echo $sentence;
}
 

 

 

kmp