ПАРАМЕТРЫ МАРКОВСКИХ МОДЕЛЕЙ ПОРОЖДЕНИЯ ЗАКОНА ЦИПФА
|
ВВЕДЕНИЕ 3
1. Марковская модель порождения закона Ципфа при отсутствии
поглощающего состояния 7
1.1 Формулировка теоретического результата для поиска
мультипликативной константы 7
1.2 Методика экспериментального доказательства 9
1.3 Анализ и расширение Утверждения 1 14
2. Скрытая марковская модель генерации слов 18
2.1 Рассмотрение различных классов сведения скрытой марковской
модели к не скрытой без поглощающего состояния 18
2.2 Теоретический вывод показателя степенного закона 23
2.3 Имитационное моделирование для оценки показателя степенного
закона при наличии поглощающего состояния 27
2.4 Уменьшение размерности задачи 29
ЗАКЛЮЧЕНИЕ 31
СПИСОК ЛИТЕРАТУРЫ 33
ПРИЛОЖЕНИЕ 35
1. Марковская модель порождения закона Ципфа при отсутствии
поглощающего состояния 7
1.1 Формулировка теоретического результата для поиска
мультипликативной константы 7
1.2 Методика экспериментального доказательства 9
1.3 Анализ и расширение Утверждения 1 14
2. Скрытая марковская модель генерации слов 18
2.1 Рассмотрение различных классов сведения скрытой марковской
модели к не скрытой без поглощающего состояния 18
2.2 Теоретический вывод показателя степенного закона 23
2.3 Имитационное моделирование для оценки показателя степенного
закона при наличии поглощающего состояния 27
2.4 Уменьшение размерности задачи 29
ЗАКЛЮЧЕНИЕ 31
СПИСОК ЛИТЕРАТУРЫ 33
ПРИЛОЖЕНИЕ 35
В последние годы идея самоорганизующихся систем - сложных систем, в которых случайные значения организуются в некий порядок, приобретает все большее влияние. Эти случайные величины, могут быть распределены по - разному, но нас будет интересовать именно степенное распределение. Широкое применение степенных законов в real networks, биологии, бизнесе, экономике и лингвистике можно объяснить в рамках различных математических моделей.
Одним из примеров может служить закон Ципфа, который был популяризирован Джорджем Ципфом - лингвистом из Гарвардского университета. Закон Ципфа утверждает, что если упорядочить по частоте встречаемости список словоформ, то частота r-ой словоформы будет обратно пропорциональна её рангу и будет задаваться степенной функцией: f(r) = сг~а , где г - ранг словоформы. Напомним, что такие словоформы как «the», «of» и «and» используются чаще всего в английских текстах. Согласно закону Ципфа слово «the» встречается в два разе чаще, чем слово «of» и в три раза чаще, чем слово «and» [1]. По статистике каждое 16 слово в английском языке - это «the». Для русского языка тройку самых популярных слов составляют: «и», «в», «не» и для них тоже справедлив закон Ципфа.
Мир хаотичен, как нам кажется, и вещи в нем распределены рядами способов и не только степенной зависимостью, но удивительно, что язык, личное и осознанное нами, поддается такому простому, как казалось бы, правилу. Мы можем с уверенностью сказать, что любой язык в мире (даже мертвый язык) ципфичен.
В объяснении почему язык ципфичен нам может помочь еще одно степенное распределение - распределение Парето. А именно принцип Парето, который гласит, что 20% всех усилий, дают 80% результата. Также и в языке 20% самых используемых слов составляют 80% нашей речи. Достаточно 20% языка, чтобы ежедневно понимать друг друга. Наверное, полиглоты знают этот секрет, поэтому выучить новый язык им не составляет труда. Сам Джордж Ципф полагал, что такое интересное распределение слов в языках можно было объяснить принципом наименьшего усилия - тенденции, заставляющие жизнь следовать по пути наименьшего сопротивления. Принцип наименьшего усилия играл большую роль в поведении человека. И когда язык развивался, рассказчики естественно предпочитали извлекать как можно меньше слов для описания своих мыслей. В свою очередь для более точного и лучшего понимания рассказчика слушатели предпочитали больший набор слов для большего разнообразия, чтобы им приходилось тратить меньше усилий на понимание того, что хотел донести до них рассказчик.
Актуальность данной темы также обусловлена тем, что язык сложная система, которую мы всегда хотим измерить и получить количественную оценку. Наши исследования основаны на частотно - ориентированном подходе для изучения динамики лексических конструкций.
Другое объяснение закона Ципфа предложил Бенуа Мандельброт - французский и американский математик. Для нас является интересным, что в дальнейшем он предложил наиболее простое объяснение закона Ципфа в [2], назвав ее моделью обезьяны. Он объяснил закон на основе простой вероятностной модели, где все символы в тексте (в том числе и пробел) набирает мартышка - машинистка, которая не знает алфавит и символы в тексте появляются независимо друг от друга с определенной вероятностью. И оказалось, что с ростом длины слов их количество возрастает экспоненциально. И слова располагались в частотном списке в зависимости от их длины.
Но стоит отметить, что буквы в реальных словах зависимы. И мы попробуем модифицировать и применить различные модели для исследования закона Ципфа для случая зависимых букв.
Также расскажем, что есть более сложные модели - скрытые марковские модели. Рассматривая случай с зависимыми буквами, мы можем предположить, что при наборе текста на клавиатуре, где все буквы зависимы, и мы заранее знаем порядок, человек все же может случайно ошибиться и нажать не на ту клавишу, это и будет тот момент, когда появляется некоторая скрытая случайная величина. Мы также попробуем дойти до случая со скрытой моделью и перенести на нее те методы, который рассмотрим для марковской модели.
В настоящее время, возможности для этого исследования стали намного шире, благодаря появлению новых больших данных и репозиторий, в частности, Google Books Ngram corpus [3]. Анализ больших данных корпусов показывает, что степенная зависимость с показателем, близким к -1, может приближенно описывать только частоты наиболее часто используемых слов [4]. В то же время частоты основных словарей наиболее используемых языков можно приблизительно описать степенным законом, показатель степени которого по модулю больше 1 (его типичные значения лежат в интервале 1,72. Более того, для языков с иероглифическими сценариями асимптотическое уменьшение частот быстрее, чем степенной закон [5]. Разработка модели, объясняющая эти явления, является актуальной проблемой на сегодняшний день.
В скрытой марковской модели, где некоторые скрытые состояния объединяются, чтобы сформировать те же самые видимые буквы интересна тем, что в будущем использование скрытых марковских моделей позволит построить более реалистичные модели генерации текста с учетом слоговой и морфологической структуры. Например, учет наличия опечаток и ошибок в слове для корпусов (согласно [6], до 30% уникальных словоформ в Google Books Ngram появляются в результате ошибочного распознавания).
Другим лингвистическим применением скрытых марковских моделей является статистика различных предложений. В последнем случае графы цепей Маркова представляют синтаксические структуры Хомского, в то время как скрытые марковские модели реализуют их как предложения. Наша цель - изучить асимптотику степенного распределения для определения показателя степенного закона. Из частотного списка траекторий скрытой марковской модели попробовать получить явные формулы для показателя степенного закона.
Все наши исследования будут основываться на вероятностно - частотной генерации текста в лингвистике и на связанном с ней законе Ципфа. Эксперименты связаны с формированием слов какого - либо конечного алфавита. В нашем случае мы рассматриваем задачи с малой размерностью, поэтому алфавит искусственный и не принадлежит какому - то языку. Но мы можем утверждать, что модель будет верна для любого языка.
Цель данной работы исследование параметров в марковских моделях генерации слов конечного алфавита.
Поставленные задачи:
1. Рассмотреть мультипликативную константу для марковской модели.
2. Провести эксперименты по генерации слов для марковской модели и сравнить с теоретическими утверждениями.
3. Рассмотреть параметры для скрытой марковской модели.
4. Провести эксперименты по имитационному моделированию генерации слов для скрытой модели.
5. Сделать выводы на основе теоретических и экспериментальных данных для марковской модели и скрытой марковской модели.
Одним из примеров может служить закон Ципфа, который был популяризирован Джорджем Ципфом - лингвистом из Гарвардского университета. Закон Ципфа утверждает, что если упорядочить по частоте встречаемости список словоформ, то частота r-ой словоформы будет обратно пропорциональна её рангу и будет задаваться степенной функцией: f(r) = сг~а , где г - ранг словоформы. Напомним, что такие словоформы как «the», «of» и «and» используются чаще всего в английских текстах. Согласно закону Ципфа слово «the» встречается в два разе чаще, чем слово «of» и в три раза чаще, чем слово «and» [1]. По статистике каждое 16 слово в английском языке - это «the». Для русского языка тройку самых популярных слов составляют: «и», «в», «не» и для них тоже справедлив закон Ципфа.
Мир хаотичен, как нам кажется, и вещи в нем распределены рядами способов и не только степенной зависимостью, но удивительно, что язык, личное и осознанное нами, поддается такому простому, как казалось бы, правилу. Мы можем с уверенностью сказать, что любой язык в мире (даже мертвый язык) ципфичен.
В объяснении почему язык ципфичен нам может помочь еще одно степенное распределение - распределение Парето. А именно принцип Парето, который гласит, что 20% всех усилий, дают 80% результата. Также и в языке 20% самых используемых слов составляют 80% нашей речи. Достаточно 20% языка, чтобы ежедневно понимать друг друга. Наверное, полиглоты знают этот секрет, поэтому выучить новый язык им не составляет труда. Сам Джордж Ципф полагал, что такое интересное распределение слов в языках можно было объяснить принципом наименьшего усилия - тенденции, заставляющие жизнь следовать по пути наименьшего сопротивления. Принцип наименьшего усилия играл большую роль в поведении человека. И когда язык развивался, рассказчики естественно предпочитали извлекать как можно меньше слов для описания своих мыслей. В свою очередь для более точного и лучшего понимания рассказчика слушатели предпочитали больший набор слов для большего разнообразия, чтобы им приходилось тратить меньше усилий на понимание того, что хотел донести до них рассказчик.
Актуальность данной темы также обусловлена тем, что язык сложная система, которую мы всегда хотим измерить и получить количественную оценку. Наши исследования основаны на частотно - ориентированном подходе для изучения динамики лексических конструкций.
Другое объяснение закона Ципфа предложил Бенуа Мандельброт - французский и американский математик. Для нас является интересным, что в дальнейшем он предложил наиболее простое объяснение закона Ципфа в [2], назвав ее моделью обезьяны. Он объяснил закон на основе простой вероятностной модели, где все символы в тексте (в том числе и пробел) набирает мартышка - машинистка, которая не знает алфавит и символы в тексте появляются независимо друг от друга с определенной вероятностью. И оказалось, что с ростом длины слов их количество возрастает экспоненциально. И слова располагались в частотном списке в зависимости от их длины.
Но стоит отметить, что буквы в реальных словах зависимы. И мы попробуем модифицировать и применить различные модели для исследования закона Ципфа для случая зависимых букв.
Также расскажем, что есть более сложные модели - скрытые марковские модели. Рассматривая случай с зависимыми буквами, мы можем предположить, что при наборе текста на клавиатуре, где все буквы зависимы, и мы заранее знаем порядок, человек все же может случайно ошибиться и нажать не на ту клавишу, это и будет тот момент, когда появляется некоторая скрытая случайная величина. Мы также попробуем дойти до случая со скрытой моделью и перенести на нее те методы, который рассмотрим для марковской модели.
В настоящее время, возможности для этого исследования стали намного шире, благодаря появлению новых больших данных и репозиторий, в частности, Google Books Ngram corpus [3]. Анализ больших данных корпусов показывает, что степенная зависимость с показателем, близким к -1, может приближенно описывать только частоты наиболее часто используемых слов [4]. В то же время частоты основных словарей наиболее используемых языков можно приблизительно описать степенным законом, показатель степени которого по модулю больше 1 (его типичные значения лежат в интервале 1,72. Более того, для языков с иероглифическими сценариями асимптотическое уменьшение частот быстрее, чем степенной закон [5]. Разработка модели, объясняющая эти явления, является актуальной проблемой на сегодняшний день.
В скрытой марковской модели, где некоторые скрытые состояния объединяются, чтобы сформировать те же самые видимые буквы интересна тем, что в будущем использование скрытых марковских моделей позволит построить более реалистичные модели генерации текста с учетом слоговой и морфологической структуры. Например, учет наличия опечаток и ошибок в слове для корпусов (согласно [6], до 30% уникальных словоформ в Google Books Ngram появляются в результате ошибочного распознавания).
Другим лингвистическим применением скрытых марковских моделей является статистика различных предложений. В последнем случае графы цепей Маркова представляют синтаксические структуры Хомского, в то время как скрытые марковские модели реализуют их как предложения. Наша цель - изучить асимптотику степенного распределения для определения показателя степенного закона. Из частотного списка траекторий скрытой марковской модели попробовать получить явные формулы для показателя степенного закона.
Все наши исследования будут основываться на вероятностно - частотной генерации текста в лингвистике и на связанном с ней законе Ципфа. Эксперименты связаны с формированием слов какого - либо конечного алфавита. В нашем случае мы рассматриваем задачи с малой размерностью, поэтому алфавит искусственный и не принадлежит какому - то языку. Но мы можем утверждать, что модель будет верна для любого языка.
Цель данной работы исследование параметров в марковских моделях генерации слов конечного алфавита.
Поставленные задачи:
1. Рассмотреть мультипликативную константу для марковской модели.
2. Провести эксперименты по генерации слов для марковской модели и сравнить с теоретическими утверждениями.
3. Рассмотреть параметры для скрытой марковской модели.
4. Провести эксперименты по имитационному моделированию генерации слов для скрытой модели.
5. Сделать выводы на основе теоретических и экспериментальных данных для марковской модели и скрытой марковской модели.
В ходе работы над магистерской диссертацией экспериментально доказано Утверждение 1 для случая матрицы переходных вероятностей P размерности 2 х 2. При этом было рассмотрено порядка е-300 « 10130 слов (фактически 107 классов).
Проверена справедливость основного утверждения как для матриц, отношение логарифмов элементов которой полностью рационально, так и для матриц, где хотя бы одно отношение логарифмов элементов матрицы иррационально. Сформулировано Утверждение 2. Проведены эксперименты, как с полностью ненулевыми матрицами, так и с матрицами, у которых р11 = 0 или р22 = 0.
Было показано, как с помощью асимптотики частотных списков для скрытой марковской модели и соответствующие ей матрице S можно найти показатель степенного закона и была сформулирована Теорема 4. Таким образом, установлены явные формулы для показателя степенной асимптотики для скрытой марковской модели.
Более того, удалось уменьшить размерность для матрицы S, так что она тоже будет соответствовать условиям Теоремы 4. Это позволит более быстро вычислить показатель теоретически.
Очень часто параметр показателя степенного закона используют как параметр для измерения богатства языка. Поэтому его, как правило, исследуют с большим интересом, чем константу С.
В данной магистерской работе удалось построить марковскую модель порождения закона Ципфа при отсутствии поглощающего состояния и провести эксперименты по оценке мультипликативной константы и сопоставить их результаты с теоретическими гипотезами.
Выдвинута гипотеза о мультипликативной константе в скрытой марковской модели без поглощающего состояния, которая оказалась справедлива в нескольких частных случаях, однако, в общем случае эта гипотеза не подтверждается. Реализован перенос результата поиска мультипликативной константы с марковской модели на случай скрытой марковской модели с рассмотрением различных классов сведения скрытой марковской модели к не скрытой. И была доказана несостоятельность переноса выводов, которые мы сделали в марковском случае. Проведены имитационные эксперименты для небольшой размерности по оценке статистики появления различных слов в рамках скрытой марковской модели при наличии поглощающего состояния. И оценен показатель степенного закона по результатам экспериментов. Программный код представлен в приложении работы.
Также в работе был рассмотрен случай разряженной матрицы вероятностей получения букв в различных состояниях и сведение этих случаев к марковской модели. Таким образом, установлены явные формулы для показателей степенной асимптотики для скрытой марковской модели.
Проверена справедливость основного утверждения как для матриц, отношение логарифмов элементов которой полностью рационально, так и для матриц, где хотя бы одно отношение логарифмов элементов матрицы иррационально. Сформулировано Утверждение 2. Проведены эксперименты, как с полностью ненулевыми матрицами, так и с матрицами, у которых р11 = 0 или р22 = 0.
Было показано, как с помощью асимптотики частотных списков для скрытой марковской модели и соответствующие ей матрице S можно найти показатель степенного закона и была сформулирована Теорема 4. Таким образом, установлены явные формулы для показателя степенной асимптотики для скрытой марковской модели.
Более того, удалось уменьшить размерность для матрицы S, так что она тоже будет соответствовать условиям Теоремы 4. Это позволит более быстро вычислить показатель теоретически.
Очень часто параметр показателя степенного закона используют как параметр для измерения богатства языка. Поэтому его, как правило, исследуют с большим интересом, чем константу С.
В данной магистерской работе удалось построить марковскую модель порождения закона Ципфа при отсутствии поглощающего состояния и провести эксперименты по оценке мультипликативной константы и сопоставить их результаты с теоретическими гипотезами.
Выдвинута гипотеза о мультипликативной константе в скрытой марковской модели без поглощающего состояния, которая оказалась справедлива в нескольких частных случаях, однако, в общем случае эта гипотеза не подтверждается. Реализован перенос результата поиска мультипликативной константы с марковской модели на случай скрытой марковской модели с рассмотрением различных классов сведения скрытой марковской модели к не скрытой. И была доказана несостоятельность переноса выводов, которые мы сделали в марковском случае. Проведены имитационные эксперименты для небольшой размерности по оценке статистики появления различных слов в рамках скрытой марковской модели при наличии поглощающего состояния. И оценен показатель степенного закона по результатам экспериментов. Программный код представлен в приложении работы.
Также в работе был рассмотрен случай разряженной матрицы вероятностей получения букв в различных состояниях и сведение этих случаев к марковской модели. Таким образом, установлены явные формулы для показателей степенной асимптотики для скрытой марковской модели.