Три года я проработал в Сербии iOS-евангелистом - было два профильный проекта и один Machine Learning-овый.
Если вам стало интересно - добро пожаловать в мир HMM.
Постановка задачи
Австрийский банк. У него много клиентов, у клиентов открыт счет в этом банке. В течении года клиент тратит средства со своего счета. Ходит в магазины, гасит коммунальные платежи и пр. Каждое списание денег со счета назовем транзакцией. Дана последовательность транзакций за определенное время (скажем год). Надо обучить машину, чтобы она начала проверять новые транзакции как достоверные или подозрительные. И выдавала предупреждение в последнем случае. Для решения задачи надо использовать Hidden Markov Model.
Введение в HMM
Я болею коронавирусом каждый год 10 дней подряд. Остальные дни здоров, как бык.
Представим эту последовательность из 365 символов в виде массива. h означает здоров, l - болен.
Если вам понятен ответ, то читайте дальше, через 15 минут вы станете экспертом по HMM. Если нет - ставьте плюс и идите ужинать.
Изменим вопрос - Какова вероятность, что я завтра буду больным?
Вы резонно уточните: -А сегодня я болен или здоров?
Если болен (смотрите на последовательность - таких больных дней всего 10), то с вероятностью = 90 процентов завтра я продолжу болеть и с вероятностью 10 процентов стану здоров.
А если я сегодня здоров? - то с вероятностью
= 0.3 процента я завтра заболею и с вероятностью 99.7% буду здоров.
Если вы сегодня больны, то с вероятностью 10% завтра вы будете здоровы и 90% продолжите болеть.
Получили 4 числа, которые красиво вписываются в матрицу 2 на 2 - вуаля! эта матрица и есть Марковский слой. Уберем проценты, оставим чистые вероятности в диапазоне от 0 до 1, как того требует наука.
здоров
болен
здоров
0.997
0.003
болен
0.10
0.90
Еще раз взглянем на матрицу и прочитаем слева направо, что если ты сегодня здоров, завтра с вероятностью 0.997 ты останешься здоров, а с вероятностью 0.003 заболеешь и так далее.
Формализуем транзакции
Чем отличается последовательность транзакций от череды болен/здоров? Ничем.
Для доказательства этого возьмем список транзакций, который мне предоставил Сбережении по моей просьбе.
Напишем на питоне скрипт, который вытащит последовательность моих транзакций в рублях и нарисует график
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 r
data = 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.
Наша последовательность стала выглядеть подозрительно знакомо
Теперь напишем Марковский слой для транзакций. Это будет матрица 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 неизвестных чисел.
Именно 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 структурах!
= 3 процента
= 90 процентов завтра я продолжу болеть и с вероятностью 10 процентов стану здоров. 
= 0.3 процента я завтра заболею и с вероятностью 99.7% буду здоров.