Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 18
Уберите код в спойлер… все равно укажут на это.
А теперь давайте с помощью этой замечательной реализации попробуем генерировать тексты. В реальности мало когда приходится иметь дело с dense (плотными?) графами, так что представлять граф в виде матрицы неоптимально.
Ну и вообще неясно, в чем суть, вроде же очевидный алгоритм вытекающий из определения цепей Маркова, нет?
Ну и вообще неясно, в чем суть, вроде же очевидный алгоритм вытекающий из определения цепей Маркова, нет?
Спасибо за критику.
Генерировать текст на основе этой реализации можно, вполне. Простые подсчеты говорят, что в тексте из 1000 уникальных (!) слов матрица будет размером 1000x1000, что с точки зрения памяти не такой и большой размер, учитывая, что средний размер слова где-то 7 букв ( байт), то занимаемая память будет 7000 байт ( размер памяти под элементы ) + 1000000 * sizeof(double) байт ( размер под матрицу ), что для современных компьютеров приемлемо. Ведь текст из 1000 неповторяющихся слов — это довольно большой текст, так ведь? Ну а дальше можно накатать алгоритм, который будет составлять матрицу перехода.
А как вы предлагаете представлять граф? Какие у Вас есть предложения?
Генерировать текст на основе этой реализации можно, вполне. Простые подсчеты говорят, что в тексте из 1000 уникальных (!) слов матрица будет размером 1000x1000, что с точки зрения памяти не такой и большой размер, учитывая, что средний размер слова где-то 7 букв ( байт), то занимаемая память будет 7000 байт ( размер памяти под элементы ) + 1000000 * sizeof(double) байт ( размер под матрицу ), что для современных компьютеров приемлемо. Ведь текст из 1000 неповторяющихся слов — это довольно большой текст, так ведь? Ну а дальше можно накатать алгоритм, который будет составлять матрицу перехода.
А как вы предлагаете представлять граф? Какие у Вас есть предложения?
Текст марковскими цепями генерируют обычно учитывая предыдущие 2-4 слова. При этом граф получается очень разреженным, а у вас N^2 памяти. Естественно, граф надо представлять списком смежности (в случае текста это хэш-таблица строка->пары строка+вес)
Цепи, которые учитывают предыдущие состояния называются цепями Маркова 1-го порядка, 2-го порядка ну и т.д
Из определения следует, что не учитывается прошлое, а только ТЕКУЩЕЕ СОСТОЯНИЕ. Состояние может быть не одномерным (из последнего слова), а многомерным — из нескольких слов, да еще и не просто учитывать само слово, но и его морфемы. Вообще такая цепочка будет полезна не только для генерации, но и например для разрешения морфологической омонимии.
Почему одно то? точно так-же несколько.
Маршрут перехода такой:
1 Тогда почему текущее
2 почему текущее состояние
3 текущее состояние это
4 состояние это несколько
5 это несколько слов
Тут веселее с сайдэффектами, к примеру в начале у нас пустой узел, потом однословные и т.п… Или сразу сказать на трехсловное выводя сразу все три слова. Знаки препинания тоже вопросы вызывают.
Но всё это детали реализации. Суть не меняется.
Маршрут перехода такой:
1 Тогда почему текущее
2 почему текущее состояние
3 текущее состояние это
4 состояние это несколько
5 это несколько слов
Тут веселее с сайдэффектами, к примеру в начале у нас пустой узел, потом однословные и т.п… Или сразу сказать на трехсловное выводя сразу все три слова. Знаки препинания тоже вопросы вызывают.
Но всё это детали реализации. Суть не меняется.
Студенческая работа?
Такое расточительство по памяти возможно лишь в учебном примере.
Одномерное состояние с малой выборкой вариантов будет на пределе памяти.
А если взять скажем простой вариант текста — три слова, у каждого собственно слово + две морфемы. На практике варианты конечно доступны не все, но скажем миллион узлов будет точно.
Одномерное состояние с малой выборкой вариантов будет на пределе памяти.
А если взять скажем простой вариант текста — три слова, у каждого собственно слово + две морфемы. На практике варианты конечно доступны не все, но скажем миллион узлов будет точно.
В каждой строке у нас есть ненулевые значения в тех столбцах, чей номер совпадает с последующим событием, а само ненулевое значение — вероятность, что это событие наступит
Вы вероятность в процентах, что ли, измеряете?
В данном случае — да. Программно удобнее генерировать целые числа, нежели дробные.
Я не буду упоминать про классическое определение вероятности — полагаю, оно всем известно.
Но даже из чисто практических соображений матрица смежности должна содержать значения вероятностей от 0 до 1. Потому что, например, вероятность перехода за N шагов — это матрица смежности в N-ной степени, стационарные вероятности — это результат решения САУ на основе матрицы смежности и т.д.
Вы ведь не просто так марковскую цепь моделируете — вы, наверное, хотите эту модель затем как-то исследовать. Для этого, я полагаю, лучше придерживаться классики.
Идея о том, что целые числа генерировать удобнее — вообще непонятна.
Но даже из чисто практических соображений матрица смежности должна содержать значения вероятностей от 0 до 1. Потому что, например, вероятность перехода за N шагов — это матрица смежности в N-ной степени, стационарные вероятности — это результат решения САУ на основе матрицы смежности и т.д.
Вы ведь не просто так марковскую цепь моделируете — вы, наверное, хотите эту модель затем как-то исследовать. Для этого, я полагаю, лучше придерживаться классики.
Идея о том, что целые числа генерировать удобнее — вообще непонятна.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разработка класса для работы с цепями Маркова