25 марта 2014

Machine learning в простом проекте

Блог компании Блог компании PreplyПрограммирование
Я CTO проекта Preply и хочу рассказать немного о том, о чем мечтает каждый программист, а именно о сложных и интересных задачах в простых проектах.

Если быть точнее, то о том, как можно добавить немного науки к бизнесу и получить в результате немного пользы. Этой статьей я постараюсь описать один из контекстов использования Machine Learning в реальном проекте.

Проблема


Мы платформа репетиторов Preply и нас все хотят обмануть.

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

Репетиторы и студенты почему-то пытаются обойти оплату уроков через сайт. Для этого они используют внутреннюю систему сообщений, которая предназначена для уточнения деталей о предстоящих занятиях и доступна после отправки заявки репетитору. Вот несколько примеров обмена контактами:

Мой скайп vasiliy.p, тел +789123456. Значит на 19:00 1 апреля!

Добрый вечер! Вы могли бы написать свой номер или позвонить на мой +78-975-12-34

Не хочу платить до урока, меня зовут Василий Пупкин – найдите меня вконтакте


Опытный программист сразу скажет: «В чем проблема написать регулярные выражения под возможные варианты обмена сообщений?». Проблемы нет, но это решение имеет ряд недостатков:

  1. Сложно предусмотреть все варианты некорректных (то есть тех какие содержат контакты) сообщений. Например, в первой версии продукта был набор регулярных выражений под номер телефона, но он срабатывал и блокировал сообщения вида:
    пятница — с 13 00-15 00-15 30… сколько будет стоит групповое занятие?

    В более сложном случае использовалось регулярное выражение для эл. почты, которое предназначалось для блокировки сообщений типа:
    vasya (собака) pupkin (точка) ru

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

    Cо словом «скайп» еще сложнее: очень тяжело отличить сообщения, содержащие попытки обмена скайпом:
    please add me in Skype — vasya82pupkin

    от уточняющих сообщений:
    do you want to have skype or local lessons?

  2. Нет контроля над порогом доверия. То есть сообщение либо блокируется, либо нет. Для того, чтобы изменить логику, нужно лезть в код. В реальной жизни намного проще допускать ошибки второго типа (пропуск сообщения), чем ошибки первого типа (ложная тревога), так как при ложной тревоге пользователь напишет в поддержку, менеджер поддержки потратит время на то, чтобы извиниться за неправильную блокировку и разблокировать сообщения, не говоря уже об испорченном опыте использования сервиса. С другой стороны пользователи, которые обмениваются контактами, редко становятся нашими клиентами, поэтому проще допускать ошибки второго типа, так как на них мы и так не заработаем (да, это бизнес).


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

Решение


Я решил попробовать 3 метода машинного обучения для правильной классификации корректных/некорректных сообщений, которые мне запомнились из курса Coursera Machine Learning by Andrew Ng.

Первая проблема заключается в подготовке базы для обучения. У нас было более 50 000 сообщений, предварительно классифицированных старой системой. Я взял только 5000 из них и потратил около 2-3 часов на то, чтобы исправить неверную классификацию в тех сообщениях, где прежняя система допускала ошибки. В теории чем больше база, тем лучше, но в реальном мире довольно сложно вручную подготовить большую выборку (проще говоря, лень).

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

Было:
Я хотел бы начать занятия с февраля месяца, это возможно? Точное время тоже смогу сказать в январе, но это точно будет не раньше 18:00

Стало:
время не занятия с февраля возможно? в Точное бы январе, тоже раньше 18:00 Я точно это но сказать смогу будет хотел начать месяца, это

Было:
Буду рада быть полезной, мой тел. (012)345-678 Звоните, будем договариваться, спасибо

Стало:
тел. быть рада Буду полезной, мой Звоните, будем договариваться, спасибо (012)345-678

В результате получился csv файл с ~5000 строчками, где некорректные сообщения отмечены нулем, а корректные единицей. После этого на основе работы с данными мы определили набор характеристик сообщения, которые «на глаз» имеют влияние на классификацию.

  • подозрение на телефон;
  • подозрение на эл. почту;
  • подозрение на скайп контакты;
  • подозрение на url;
  • подозрение на соц. сети;
  • корректные слова, которые идут с цифрами (время, валюта);
  • длина сообщения;
  • подозрительные слова: найдите, добавьте, мой;
  • … и так далее.


После определения характеристик под каждую из них я писал несколько регулярных выражений, например:

import re
SEPARATOR = "|"
reg_arr = [ re.compile(u'фейсбук|facebook|linkedin|vkontakt|вконтакт',re.IGNORECASE | re.UNICODE),
			re.compile(u'соц.{1,10}сет', re.UNICODE)]
			re.compile(u'скайп[^у]|skype', re.IGNORECASE | re.UNICODE),
			re.compile(u'скайпу', re.IGNORECASE | re.UNICODE),
			re.compile(u'[йцукенгшщздлорпавифячсмітьбю].*\s[a-zZ-Z]', re.IGNORECASE | re.UNICODE),
			re.compile('\d{3}[-\.\s]??\d{3}[-\.\s]??\d{4}|\(\d{3}\)\s*\d{3}[-\.\s]??\d{4}|\d{3}[-\.\s]??\d{4}'),
...
			re.compile('http|www|\.com', re.IGNORECASE),
			re.compile(u'мой|my', re.IGNORECASE | re.UNICODE),
			re.compile(u'найдите|find', re.IGNORECASE | re.UNICODE),
			re.compile(u'добавь|add', re.IGNORECASE | re.UNICODE),
...
			re.compile('\w+@\w+', re.IGNORECASE),
			re.compile('.{0,50}', re.IGNORECASE),
			re.compile('.{50,200}', re.IGNORECASE),
....
		]	
			
def feature_vector(text):
	return map(lambda x: 1 if x.search(text) else 0, reg_arr)

fi=open('db_machine.csv', 'r')
fo=open('db_machine_result.csv', 'w')

for line in fi:	
	[text, result] = line.split(SEPARATOR)
	output = feature_vector(text).append(result)
	fo.write(",".join(map(lambda x: str(x), output )) + "\n")	
	
fo.close()
fi.close()


Соответственно после обработки всех сообщений по всем характеристикам (у нас сейчас их около ста) мы записываем вектор характеристик и результат классификации в файл.

После подготовки данных необходимо разбить выборку на три части: для обучения (train set), для подбора параметров (cross-validation set) и проверки (test set). Следуя совету из курса, размеры выборок обучения, подбора параметров, теста соотносятся в пропорции 60/20/20:

import random
with open('db_machine_result.csv','r') as source:
	data = [ (random.random(), line) for line in source ]
data.sort()

n = len(data)
with open('db_machine_result_train.csv','w') as target:
	for _, line in data[:int(n*0.60)]:
		target.write( line )
with open('db_machine_result_cross.csv','w') as target:
	for _, line in data[int(n*0.60):int(n*0.80)]:
		target.write( line )		
with open('db_machine_result_test.csv','w') as target:
	for _, line in data[int(n*0.80):]:
		target.write( line )


Затем, руководствуясь принципом не изобретать велосипед и максимально быстро получить результат, мы использовали скрипты из курса Machine Learning Coursera и просто прогнали наши выборки по алгоритмам логистической регресии, SVM и нейронных сетей. Скрипты просто взяты из курса, например SVM выглядит так:

clear ; close all; clc

data_train = load('db_machine_result_train.csv'); 
X = data_train(:, 1:end-1); y = data_train(:,end);

data_val = load('db_machine_result_cross.csv'); 
Xval = data_val(:, 1:end-1); yval = data_val(:,end);

data_test = load('db_machine_result_test.csv'); 
Xtest = data_test(:, 1:end-1); ytest = data_test(:,end);

[C, sigma] = dataset3Params(X, y, Xval, yval); % подбор параметров на cross-validation set

fprintf('C: %f\n', C);
fprintf('sigma``: %f\n', sigma);

model= svmTrain(X, y, C, @(x1, x2) gaussianKernel(x1, x2, sigma));

p = svmPredict(model, X);
fprintf('Training Accuracy: %f\n', mean(double(p == y)) * 100);

p = svmPredict(model, Xtest);
fprintf('Test Accuracy: %f\n', mean(double(p == ytest)) * 100);

fprintf('Program paused. Press enter to continue.\n');
pause;


Посмотреть на то, как реализованы функции svmTrain/svmPredict можна на сайте курса или, например, здесь.

Все алгоритмы на выборке cross-validation перебирали внутренние параметры (λ — для регуляризации, σ, C — для гауссовской функции, size — для размера скрытого слоя нейронной сети). Представим финальные результаты точности для некоторых из них ниже:

Нейронные сети Логистическая регресия SVM
size=30, λ=1 size=30, λ=0.01 size=30, λ=0.001 λ=0 λ=0.01 λ=1 Linear (λ 0.001, σ=0.001) Gaussian (λ 0.1, σ=0.1) Gaussian (λ 0.001, σ=0.001)
96.41% 97.88% 98.16% 97.51% 97.88% 98.16% 96.48% 97.14% 98.89%


Здесь нужно уточнить, что в процесе подготовки системы результат был намного хуже (96.6% для SVM, например), и очень ощутимые улучшения дала отладка. Мы запустили логистическую регресию, как самую простую и быструю на реальных данных всей выборки, и пересмотрели результат классификации. С удивлением обнаружили, что система оказалась умнее меня, так как в 30% случаев была ошибка в классификации сообщений человеком (как я писал, я просмотрел ~5000 сообщений и, как оказалось, допустил где-то 30-40 ошибок классификации), а система классифицировала все правильно. В процесе отладки мы исправляли ошибки в базе и соответственно точность метода росла. Более того, мы расширяли вектор характиристик, если видели что какой-то интересный паттерн не обрабатывается системой.

Выбрали использовать метод SVM, характеристики на общей выборке были следующие:

Сообщение
Факт
Корректное
Некорректное
Прогноз
Корректное
4998 36
Некорректное
11 390


Поскольку система имеет свойство того, что классы «перекошены» (skewed classes), то для сравнения алгоритма приведу также параметры:

Precision Recall Accuracy
99.28% 99.78% 99.13%


В итоге мы решили использовать SVM с ядром гауссовской функции для фильтрации сообщений на сайте. Он сложнее, чем логистическая регрессия, но дает существенно лучший результат, хотя и работает медленнее.
Полностью путь обработки сообщения выглядит следующим образом:
  • Пользователь отправляет сообщение на сайте, Backbone JS создает модель на машине клиента и POST запросом отправляет ее API сервера;
  • API сервера, написанное на Django TastyPie, использует Django форму валидации модели;
  • первый валидатор подтягивает с базы профиль пользователя и проверяет не отмечен ли пользователь как нарушитель (не нужно проверять дальше, 403 ответ) или он уже делал платежи через сайт (не нужно проверять дальше, сразу 201 ответ);
  • валидатор svmPredict возвращает результат проверки текста сообщения. Если пользователь нарушил правила, в его профиль ставится соответствующий флаг, иначе все хорошо и пользователь получает 201 ответ от API и сообщение пишется в базу;
  • если сообщение содержало контакты или пользователь был нарушителем, клиенту возвращается 403 ответ, при получении которого Backbone рендерит сообщение пользователю, что он нарушает правила. Пользователь в базе отмечается как нарушитель;

Пока работает хорошо и мы этому рады.

Выводы


Понять, почему Machine Leaning работает лучше, чем старая система очень просто — он выявляет те связи между характеристиками, которые были скрыты в экспертном наблюдении. Например, у нас было регулярное выражение и несколько if-условий на событие: если есть кириллица и латиница в тексте, несколько цифр и сообщение короткое, то это, скорее всего, обмен контактами. Теперь мы просто считаем отдельные события, а система сама понимает, какая между ними связь и строит правила вместо нас.

Сейчас мы действительно используем SVM в продакшене для классификации сообщений ввиду хороших показателей точности. Используем в очень простой способ — мы взяли набор весов оптимальной модели и используем портированную на Python функцию svmPredict, упомянутую выше, для классификации. В идеальном мире нужно было бы сделать систему обратной связи с учителем, чтобы администратор указывал на ошибки классификации, а система корректировала веса и улучшалась. Но наш проект живет в реальном мире, где время=деньги и мы пока наслаждаемся тем, что количество обращений в поддержку по поводу неправильной блокировки упало в 2 раза. Также интересная мысль балансировать порог доверия и соответственно ошибки первого и второго типа, но пока нас все устраивает. Измерять количество ошибок типа «пропуск сообщения» довольно сложно. Уточню только, что конверсия заявок в платежи после внедрения системы не упала. Иными словами, даже если пропусков стало больше, на бизнес это не влияет. Но на глаз пропусков тоже стало меньше. Так что это очень хороший результат за одни выходные.

Если тема интересна вам, то я готов написать о collaborative filtering подходе для рекомендаций репетитора, который мы делаем. Если нужен код, также обращайтесь, — там ничего секретного нет, а в статье больше хотелось описать pipeline.

P.S.: Мы растем и в перспективе ищем в наш киевский офис 2 умных и ответственных программистов: стажера и более опытного для закрытия задач, на которые не хватает моих двух рук. Наш стек Python/Django и JS/Backbone. Много интересных задач и лучших практик. Пишите dmytro@preply.com
Теги:machine learningстартапstatisticssvmneural networkslogistic regression
Хабы: Блог компании Блог компании Preply Программирование
+43
37,9k 208
Комментарии 43
Лучшие публикации за сутки