Цепи Маркова – один из наиболее распространенных и простых способов моделирования случайных событий. Он нашел применение практически во всех областях деятельности человека. Google указывает на то, что соответствующий подход подойдет как для генерации теста, так и для финансового моделирования.
Далее предстоит познакомиться с цепями Маркова поближе. Необходимо выяснить, что они собой представляют, какими свойствами обладают. Также нужно ознакомиться с алгоритмом PageRank, который лег в основу работы Google, рассмотреть использование марковских цепей для ранжирования узлов заданного графа, а также в SEO.
Представленная информация ориентирована широкую публику. Для ее понимания требуются поверхностные знания основ вероятности и линейной алгебры.
Определение
Цепи Маркова – это некая математическая модель, с помощью которой описывается последовательность событий. В этой цепочке вероятность каждого исхода (события) зависит только от предыдущего события. Это метод предсказания будущих результатов на основе прошлых событий.
Google указывает на то, что цепи Маркова – это последовательность случайных событий с конечным или счетным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем.
Случайные величины и процессы
Перед тем как рассматривать графы цепи Маркова, стоит запомнить несколько ключевых определений из теории вероятностей:
- Случайная величина X – это переменная. Ее значение будет определяться как результат случайного явления. Он может выражаться числом (включая векторы) или нет.
- Случайный (стохастический) процесс – набор некоторых случайных величин, индексируемых множеством T, представляющих различные моменты времени. Самыми распространенными являются две ситуации: когда T – это множество натуральных чисел (случайный процесс с дискретным временем), и когда T – множество вещественных чисел (случайный процесс с непрерывным временем).
Эти два определения помогут быстрее разобраться с рассматриваемыми цепями. Теперь можно рассмотреть их более детально.
Свойство Маркова
Случайные процессы делятся на несколько известных семейств:
- гауссовы процессы;
- модели авторегрессии;
- модели скользящего среднего;
- процессы Пуассона;
- цепи Маркова и другие.
Каждый из них предусматривает свои специфические свойства, о которых необходимо знать. Эти самые «особенности» позволяют лучше и быстрее понять принцип работы случайных процессов в том или ином случае.
Google называет «свойство Маркова» одним из параметров, значительно упрощающий изучение случайных событий. В неформальном виде оно говорит, что, если известно значение, которое принимает процесс в текущий момент времени, никакой дополнительной информации о его будущем поведении получиться не удастся, если собрать больше знаний о прошлом.
Google подчеркивает, что в математическом смысле «свойство Маркова» звучит так: для любого данного времени условное распределение будущих состояний процесса с учетом текущего и прошлого состояний зависит только от настоящего его «положения» и абсолютно не зависит от прошлого. Такое положение называется беспамятностью. Случайный процесс, обладающий свойством Маркова – это марковский процесс.
Цепь Маркова – это марковский процесс с дискретным временем и дискретным пространством состояний. Google также называет их однородными. Рассматриваемый процесс – это дискретная последовательность состояний, каждое из которых берется из дискретного пространства состояний (как конечного, так и нет), следующая свойству Маркова.
Свойства цепей
Google указывает, что изучаемые цепи имеет ряд основных свойств и характеристик. Они будут рассмотрены без углубления в математические аспекты для того, чтобы каждому была понятная соответствующая информация.
Марковские цепи, согласно Google, могут быть представлены в виде графа. Для некоторых представленных далее свойств предстоит использовать графическую интерпретацию. Также предстоит запомнить – указанные характеристики не всегда (и не обязательно) будут ограничиваться случаем конечного пространства состояний.
К основным свойствам метода Маркова относят:
- периодичность;
- рекуррентность;
- изменяемость;
- переходность.
Далее эти характеристики будут изучены более подробно, но описаны простым языком.
Несводимость
Цепь Маркова обладает свойством несводимости, если из любого состояния можно получить любое другое состояние. Результат не обязательно выводится за один по времени шаг. Google подчеркивает – если пространство состояний конечное и цепь может быть представлена в виде графа, то можно говорить о том, что граф несводимой цепи Маркова сильно связный.
Выше можно увидеть наглядный пример свойства несводимости. Цепь слева не является несводимой: из 3 и 4 попасть в 1 или 2 не получится. Цепь справа – несводимая. Это связано с тем, что в каждое состояние получится попасть из любого другого состояния.
Периодичность
Состояние, согласно Google, обладает периодом k, если при выходе из него любой возврат обратно требует количества временных шагов, кратного k. Здесь k – это наибольший общий делитель всех предусматриваемых путей возврата.
Если k = 1, состояние будет называться апериодическим. Если все состояния цепи Маркова являются таковыми, цепь называется апериодической. Нередуцируемая цепь, согласно Google, имеет важную характеристику: если одно состояние апериодично, то все состояния будут такими же.
Изображение выше наглядно объясняет свойство периодичности. Цепь слева является 2-периодичной. В ней при выходе из любого состояния для возвращения в него же при любых ситуациях требуется 2-кратное количество шагов. Справа изображена 3-периодичная цепочка.
Рекуррентность/транзитивность
Google указывает на то, что у рассматриваемого «метода» есть еще одна характеристика – переходность. Состояние будет переходным, если при выходе из него существует нулевая вероятность того, что возврат туда не будет осуществлен никогда.
Повторяющееся состояние, согласно Google – это ситуация, когда известно с вероятностью 1, что, после выхода из нее через некоторое время предстоит вернуться обратно (если соответствующее состояние не переходное).
Выше можно увидеть наглядный пример цепей Маркова со свойством транзитивности/рекуррентности. Слева изображена цепочка, в которой 1, 2 и 3 – это переходные состояния (выходя из этих точек, нет абсолютной уверенности в том, что в них будет осуществлен возврат). Эти точки также выступают 3-периодическими. 4 и 5 – повторяющиеся. Покидая их, можно быть абсолютно уверенными в том, что когда-нибудь к ним получится вернуться. 4 и 5 также являются 2-периодическими. У цепочки справа есть еще одно ребро. За счет него вся система становится повторяющейся, а также апериодической.
Для повторяющихся состояний, согласно Google, можно определить среднее время повторения. Оно называется ожидаемым временем возвращения при выходе из состояния. Здесь необходимо обратить внимание на то, что при вероятности возвращения равной 1 нет гарантий того, что время возвращения является конечным. Все это позволяет различать положительное и нулевое рекуррентные состояния. Google описывает первое как конечное ожидаемое время возврата, а второе – как бесконечное.
PageRank
PageRank – алгоритм, который до сих пор используется в Google. Он хорошо объясняет принцип работы рассматриваемых цепей.
PageRank пытается решить проблему, которая заключается в следующем: выбор ранжирования страницы заданного множества при помощи связей между ними. Для этого используется следующий алгоритм: случайный Интернет-пользователь находится на одной из страниц в заданный (начальный) момент времени. Далее он начинает случайную навигацию при помощи нажатия для каждой страницы по одной из ссылок, ведущих на другую страницу из рассматриваемого множества. Для данной веб-страницы все разрешенные ссылки имеют равные шансы на то, чтобы быть нажатыми.
Это и есть постановка цепи Маркова согласно Google:
- страницы – это разнообразные состояния;
- вероятности перехода определяются связями от страницы к странице;
- свойства беспамятства подтверждаются пользовательским поведением.
Если предположить, что определенная цепочка выступает в качестве рекуррентной положительной и апериодичной, то, согласно Google, через длительный промежуток времени распределение вероятности «текущей страницы» будет сведено к стационарному распределению. Все это способствует тому, что, независимо от начальной страницы, через длительное время каждая страница имеет вероятность быть текущей (практически фиксированную вероятность), если выбрать случайный шаг по времени.
В основе PageRank, используемой в Google, заложена гипотеза о том, что наиболее вероятные страницы в стационарном распределении должны быть самыми важными. Они посещаются пользователями чаще остальных. Стационарное распределение вероятностей определяет для каждого состояния значение PageRank.
Использование в SEO
Google указывает, что рассматриваемые цепи могут быть использованы в SEO. С их помощью можно провести анализ структуру ссылок и спрогнозировать, на какие порталы будут вести ссылки в дальнейшем.
Google также приводит наглядный пример использования рассматриваемых цепей в SEO:
- Собрать информацию о внутренних ссылках на сайте. Для этого, согласно Google, нужно использовать краулер сканирования.
- Записать URLs всех внутренних ссылок на каждой странице.
- Создать матрицу переходов со ссылочной структурой веб-сервиса. Google подчеркивает, что каждая ее строка – это страница сайта, а столбец – целевая страница, на которую разрешается переход по внутренней ссылке. Значение в каждой матричной ячейке – это количество ссылок, существующих между двумя страницами.
- Проанализировать матрицу переходов. Это необходимо для выявления закономерностей в ссылочной структуре на веб-сервисе.
- Использовать данные, полученные при помощи матрицы ссылок, для формирования рекомендаций по оптимизации внутренней ссылочной структуры страницы. Пример – рекомендовать, чтобы важные страницы сайта включали в свой состав больше внутренних ссылок, указывающих на них. Google подчеркивает, что это помогает повышать их видимость для поисковиков.
- Выполнить рекомендации и отследить полученные результаты. Обычно на это уходит несколько месяцев.
Это – всего лишь один из примеров, в котором использованы цепи Маркова. Другие факторы в SEO для оптимизации веб-сервиса тоже имеют значения.
Теперь понятно, что собой представляют цепи Маркова, а также как их можно использовать. Лучше изучить эту тему помогут дистанционные компьютерные курсы. Они рассчитаны на срок от нескольких месяцев до года. Позволяют освоить любое IT-направление или специализацию. В конце каждого успешно завершенного курса учащемуся выдается электронный сертификат, подтверждающий приобретенные знания и навыки.
Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!
