Марковские цепи

Три года я проработал в Сербии iOS-евангелистом - было два профильный проекта и один Machine Learning-овый.

Если вам стало интересно - добро пожаловать в мир HMM.

Постановка задачи

Австрийский банк. У него много клиентов, у клиентов открыт счет в этом банке. В течении года клиент тратит средства со своего счета. Ходит в магазины, гасит коммунальные платежи и пр. Каждое списание денег со счета назовем транзакцией. Дана последовательность транзакций за определенное время (скажем год). Надо обучить машину, чтобы она начала проверять новые транзакции как достоверные или подозрительные. И выдавала предупреждение в последнем случае. Для решения задачи надо использовать Hidden Markov Model.

Введение в HMM

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

Представим эту последовательность из 365 символов в виде массива. h означает здоров, l - болен.

days{365} = {hhhhhhhhhhllllllllllhhhhhhhhhhhhhhhhhhhhhhhh...hhhhh}

Вопрос - Какова вероятность, что я сегодня болен?

$\frac{10}{365}$ = 3 процента

Если вам понятен ответ, то читайте дальше, через 15 минут вы станете экспертом по HMM. Если нет - ставьте плюс и идите ужинать.

Изменим вопрос - Какова вероятность, что я завтра буду больным?

Вы резонно уточните: -А сегодня я болен или здоров?

Если болен (смотрите на последовательность - таких больных дней всего 10), то с вероятностью $\frac{9}{10}$ = 90 процентов завтра я продолжу болеть и с вероятностью 10 процентов стану здоров.

А если я сегодня здоров? - то с вероятностью

$\frac{1}{355}$ = 0.3 процента я завтра заболею и с вероятностью 99.7% буду здоров.

Если вы сегодня больны, то с вероятностью 10% завтра вы будете здоровы и 90% продолжите болеть.

Получили 4 числа, которые красиво вписываются в матрицу 2 на 2 - вуаля! эта матрица и есть Марковский слой. Уберем проценты, оставим чистые вероятности в диапазоне от 0 до 1, как того требует наука.

	здоров	болен
здоров	0.997	0.003
болен	0.10	0.90

Еще раз взглянем на матрицу и прочитаем слева направо, что если ты сегодня здоров, завтра с вероятностью 0.997 ты останешься здоров, а с вероятностью 0.003 заболеешь и так далее.

Формализуем транзакции

Чем отличается последовательность транзакций от череды болен/здоров? Ничем.

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

27.10.2020 00:00 GAZPROMNEFT AZS 219    2507,43 118 753,95 28.10.2020 / 298380 Автомобиль 26.10.2020 14:45 SPAR 77                319,73 121 261,38 27.10.2020 / 220146 Супермаркеты 26.10.2020 14:38 ATM 60006475           4800,00 121 581,11 26.10.2020 / 213074 Выдача наличных 25.10.2020 17:52 EUROSPAR 18            970,02 126 381,11 26.10.2020 / 259110 Супермаркеты 25.10.2020 00:00 Tinkoff Card2Card      20000,00 127 351,13 26.10.2020 / 253237 Перевод с карты 22.10.2020 14:22 SBOL перевод 4276      7000,00 147 351,13 22.10.2020 / 276951 Перевод с карты 22.10.2020 12:18 STOLOVAYA              185,00 154 351,13 23.10.2020 / 279502 Рестораны и кафе 21.10.2020 16:46 MEGAFON R9290499831    500,00 154 536,13 21.10.2020 / 224592 Комунальные платежи, связь, интернет. 21.10.2020 14:17 SPAR 77                987,03 155 036,13 22.10.2020 / 219015 Супермаркеты 21.10.2020 13:42 PYATEROCHKA 646        289,93 156 023,16 22.10.2020 / 294539 Супермаркеты 21.10.2020 00:00 MEBEL                  75,00 156 313,09 22.10.2020 / 279935 Прочие расходы 19.10.2020 14:54 SPAR 77                552,92 132 044,80 20.10.2020 / 208987 Супермаркеты 19.10.2020 00:00 MOBILE FEE             60,00 132 597,72 20.10.2020 / - Прочие операции 16.10.2020 14:19 SPAR 77                579,39 132 657,72 17.10.2020 / 229627 Супермаркеты 12.10.2020 13:33 STOLOVAYA              185,00 133 237,11 13.10.2020 / 261374 Рестораны и кафе 12.10.2020 00:00 OOO MASTERHOST         1000,00 133 422,11 13.10.2020 / 268065 Прочие расходы 11.10.2020 12:09 SPAR 77                782,87 134 422,11 12.10.2020 / 275816 Супермаркеты 10.10.2020 14:52 SBOL перевод           400,00 135 204,98 10.10.2020 / 276925 Перевод с карты 09.10.2020 13:29 SBOL перевод 5484*     1000,00 135 604,98 09.10.2020 / 229184 Перевод с карты 09.10.2020 11:55 MAGNIT MK KRYUCHYA     274,00 136 604,98 10.10.2020 / 209914 Супермаркеты

Напишем на питоне скрипт, который вытащит последовательность моих транзакций в рублях и нарисует график

def readtrans():    with open ("assets/trans.txt", "r") as file:        grades = file.read()    pattern = '(\d{2,5}),\d\d'    result = re.findall(pattern, grades)    r = list(map(int, result[0::2]))    return rdata = readtrans()t = list(range(len(data)))df = pd.DataFrame({'number':t, 'amount':data})ax1 = df.plot.bar(x='number', y='amount', rot=0, width=1.5)

Упростим картину - дешевые транзакции (менее 10$) обозначим буквой l, дорогие свыше 100$ буквой h, остальные - буквой m.

Наша последовательность стала выглядеть подозрительно знакомо

print(observations[:20])trans[] = ['m', 'm', 'm', 'l', 'm', 'm', 'h', 'm', 'l', 'l', 'm', 'l', 'l', 'l', 'l', 'l', 'l', 'm', 'l', 'l']

Теперь напишем Марковский слой для транзакций. Это будет матрица 3 на 3, поскольку у нас 3 возможных типа транзакций = {l,m,h}

[[0.5 0.3 0.2] [0.6 0.3 0.1] [0.7 0.3 0.0]]

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

Эта матрица, этот явный Марковский слой характеризует каждого клиента банка. То есть легко пересчитать данную матрицу при поступлении нового платежа и по какой-то метрике сравнить с канонической. Если отклонение большое - транзакция подозрительна.

-Так просто?! - воскликнет читатель. Да, но за построение такой простой модели банк много денег не заплатит. Надо ввести еще один Марковский слой (невидимый), и алгоритм сразу станет красивее, сложнее и наукоёмчее. И потянет на кандидатскую диссертацию.

Скрытый Марковский слой

Посмотри, читатель, на подробную расшифровку моих платежей. Многие действия повторяются - походы в столовую, пятёрочка, спар, Газпромнефть, мобильный платеж...

То есть существует набор периодических однотипных событий, число которых мы не знаем и Марковский слой для которых невозможно построить. Как построишь, если ничего не знаешь конкретно?! Вот именно. Но мы знаем, что эти события происходят и их примерно 4-6 штук. Поход в магазин. Столовая. Еще что-то. И так далее. И что мы точно знаем, что после похода в столовую мы никогда не опустошаем свой кошелек на сумму более 300 рублей.

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

[[a1 a2 a3 a4 a5] [b1 b2 b3 b4 b5] [c1 c2 c3 c4 c5] [x1 x2 x3 x4 x5] [y1 y2 y3 y4 y5]]

Именно 20, а не 25 (отвечать будет Ягуар). Это точно такой же Марковский слой, что мы строили раньше, но основанный на 5 событиях.

И чтобы связать два слоя (видимый с платежами и невидимый с событиями) мы заведем матрицу перехода размера 5 на 3.

В чем смысл матрицы перехода? В том, что после невидимого события a (поход в столовую)

у нас произойдет с разной степенью вероятности либо l-платеж, либо m-платеж, либо h-платеж. Скорее всего после похода в столовую эта строка будет такая

[0.96 0.04 0.0]

Что означает невозможность потратить более 100 долларов в нашей технопарковской столовой. Даже с приглашенной девушкой.

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

И мы можем найти эти 20+10 неизвестных величин, потому что у нас есть история платежей!

Это прекрасно и это называется обучить систему!

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

Обучение

В питоне есть библиотека hmm, в которой существует метод обучения - ему надо подать ваши три матрицы, и серию последовательностей из транзакций. Алгоритм такой, что вы разбиваете историю ваших транзакций порциями штук по 15-20 и скармливаете ее, пока система не обучится.

Процесс сходимости хорошо виден на графике.

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

Питон против Сишарпа

Работодатель обязал меня использовать библиотек Accord и язык C#

using Accord.MachineLearning;using Accord.Statistics.Models.Markov;using Accord.Statistics.Models.Markov.Learning;using Accord.Statistics.Models.Markov.Topology;using Comtrade.FMS.Common;

Согласно контракту я не могу разглашать код, поэтому написал аналог на Питоне (я не знаю оба языка) и частично смог повторить результат. Но по скорости обучения Питон сильно проигрывает Си-шарпу. Правда, я run-ил программу на разного класса компьютерах)) В Словении это был сервер работодателя. Питон для Хабра пыхтел на 2010 года макбуке.

Приведу одну строку кода, в которой зашифрован метод обучения.

var teacher = new BaumWelchLearning(hmm)

Детали метода Баум-Уэлша вы поймете, прочитав соответствующую литературу и настроив свои мозги на стат. процессы.

Успехов и хорошей карьеры в банковских IT структурах!