МО(АР)

Машинное обучение занимается поиском скрытых закономерностей в данных.
Данные это набор объектов. Каждый объект характеризуется набором переменных (вектором). Переменные — наблюдаемые и скрытые (Х и Т).
Наблюдаемые легко посчитать (фактически, измерить)
Скрытые — вычисление связано с затратами ресурса
Обучающая выборка — известна и наблюдаемая компонента, и скрытая
Между наблюдаемыми переменными и скрытыми далеко не всегда есть связь.

Решение задачи МО — нахождение способа параметризации зависимости между скрытыми и наблюдаемыми переменными с точностью до W (фактически, зная W можем определить скрытые переменные по наблюдаемым)

Эффект переобучения — алгоритм запомнил обучающую выборку и на обучающей выборке все ок, но на произвольном объекте прогноз неадекватен.

Пример: анкета на кредит
Наблюдаемые — результаты анкеты
Скрытые — дать\ не дать кредит
Обучающая выборка — клиентская база

Метод опорных векторов — ?

BigData analysic
Объем данных, доступных для анализа, растет быстрее, чем скорость их обработки -> старые математические методы не применимы -> необходимы новые математические методы:
1) байесовский подход к машинному обучению
2) обучение по неполностью размеченным данным (или вообще неразмеченным)
3) глубинное обучение
4) стохастическая оптимизация
5) тензиорное разложение

По тензорному обучению нет учебников вообще пока

Особеннность байесовского подхода — интерпретация случайности: случайность — мера незнания. Все величины детерминированы, просто мы не знаем как они себя ведут.
Пример: подбрасывание монетки: с одной стороны этот процесс случайный, с другой — подчиняется законам механики, ничего случайного в нем нет, он полностью детерминирован и при наличии н.у. мы можем предсказать что произойдет
Тогда, если вдуматься — все детерминировано, мы просто не знаем входные данные. Тогда различие между случайной-не случайной величиной пропадает, будем использовать все свойства что тех, что других.
Кодировать будем в терминах вероятностных распределений.
Тогда используем теорему байеса: апостериорное распределение с точностью до нормировочной константы равно произведению функции правдоподобия на априорное распределение на данную случайную величину.
А теперь проще: есть задача оценки параметра тетта по косвенным проявлениям в виде величин(ы) Х. Тогда взаимосвязь между Х и тетта это вероятность P(X|тетта) — т.е. Х пронаблюдали при заданном тетта, это и есть функция правдоподобия — априорное распределение, позволяющее закодировать априорное ожидание относительно параметров тетта. В МО это часто используется.
Смысл распределения — как изменились ожидания относительно тетта с учетом того, что мы пронаблюдали набор косвенных проявлений.
Свойство подхода: если есть вероятностная модель, которая задает совместное распределение на все переменные, то всегда можно, зная это распределение, построить любое условное распределение.
Т.е. если есть совместное распределение на три группы переменных p(U, O, L), где U — неизвестные переменные, которые нужно спрогнозировать, O — переменные, которые мы знаем (наблюдаемые), L — не знаем, и пофиг
Любое условие можно выразить через совместное распределение как частное интегралов. Сложность — взятие интегралов.

Процесс обучения по байевской модели:
— задаем совместное распределение на группы переменных X, T, W
— этап обучения: дана обучающая выборка и скрытые компоненты, по ним строим апостериорное распределение на параметр W
— если поступает новый набор объектов, о которых известен только набор Х, то ищем условное распределение по всевозможным наборам, кратно W, полученным на этапе обучения
p(W) — дополнительный критерий, используемый для исключения эффекта переобучения

Преимущества байесовского подхода:
— апостериорное распределение можно использовать для новой модели если появятся новые данные
апостерионое распределение == априорное при поступлении новой информации
Фактически, происходит последовательная правка результата с учетом апостериорных распределений
— байесовский подход можно использовать для построения графа-моделей
Считалось, что есть есть выборка из н объектов, то скрытые компоненты разных объектов зависят только от наблюдаемых компонентов этих объектов (и то далеко не полностью и не всегда), а между собой и не взаимодействуют.
Теперь это уже не факт. Пусть А нравится научная фантастика, а Б друг А, тогда чему равна вероятность того, что Б нравится научная фантастика? А если таких друзей 20 человек? По крайней мере, она явно выше.

Обучение по неполным данным
Известны и наблюдаемые, и скрытые переменные.
Пусть скрытые неизвестны, но известно подмножество возможных значений скрытых переменных.
Т.е. если раньше мы строили какую-то более-менее подходящую функцию и ее использовали для генерации новых пар (x, y), то теперь мы пытаемся построить алгоритм прогнозирования переменных Т притом, что мы их в обучающей выборке даже не видим, а видим какие-то их подмножества.
Легко построить большие выборки для Х.
А вот построить Т довольно сложно и дорого.
А вот подмножество Т построить просто.

Обучение по полностью размеченным данным:
ЕМ-алгоритм — сводит задачу к задаче ЕМ
Два шага — Е-шаг: по неполной разметке восстановить полную
М-шаг: берем матожидание и пытаемся оптимизировать по W
Итерационно повторяем

SVM — метод опорных векторов
Пусть есть скоринговая фнкция, зависящая от Т, Х, W и прогнозирование осуществляется: поступает Х, знаем W после обучения, max(T) — результат
Через формулу получаем W — задача квадратичного программирования
W минимизируется и получает ограничения: W должно быть таким, чтобы выход скоринговой функции на правильном ответе обуч.выборки был выше, чем выход на других объектах.
Если данные неполные, то берем Т максимальное и требуем, чтобы максимум был больше, чем максимум на всевозможных Т

Глубинное обучение: нейронные сети оказались крайне эффективны, в частности, сверточные сети используются для анализа изображений
Предобучение — сначала определяется зона, где мера градиентного спуска сойдется к локальному экстремуму. Поэтому сначала находят уданое начальное приближение и в нее скатываемся градиентом.
Реализация — 10 млн нейронов может быть запущено для бытовом пк

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

Тензорные разложения. Как можно хранить и выполнять базовые операции для тензоров (многомерных массивов)
Можно ли придумать формат для хранения тензоров, чтобы он влезал в память и чтобы можно было сложить тензоры через методы линейной алгебры не выводя тензор из формата тензора.
ТТ-формат (tensor train) дает такую возможность
Для произовольной позиции может посчитать элемент
Каждый элемент это произведение G-ядер
Пусть есть 1024 элемента. Тогда это преобразуем в 10-мерный тензор по два элемента.
В ТТ предствлении можно хранить нейросети и выборки

В основе МО лежит байесовский вывод.
===
Суть вывода:
Пусть есть две вазы печенья, причем, в первой соотношение простого к шоколадному == 30:10,
во второй — 20:20. Берем наугад, знаем, что на выходе имеем простое.
Пусть Н1 — выбор 1 вазы, а Н2 — второй. Пока вазы идентичны, т.е. р(Н1) = р(Н2) = 0.5
Е — наблюдение. Наблюдаем только Н1: р(Е/Н1) = 30/40 = 0.75; только Н2: р(Е/Н2) = 20/40 = 0.5.
Тогда по формуле Байеса:
р(Н1/Е) = р(Е/Н1)р(Н1)/(р(Е/Н1)р(Н1)+р(Е/Н2)р(Н2)) = 0.75*0.5/(0.75*0.5 + 0.5*0.5) = 0.6
До того, как мы наблюдали результат, вероятность была 0.5, но теперь вероятность р(Н1/Е) = 0.6
===
Вероятностные программы имеют две особенности:
1) возможность выбирать значения случайно из вероятностных разпределений;
2) возможность определять значения переменных посредством наблюдения.
Вторая особенность крайне сложна и поднимает огромное количество семантических вопросов.

Программа {x := 0} [1/2] {x := 1}; observe x = 1
кладет 0 в х с вероятностью 1/2
кладет 1 в х с вероятностью 1/2
observe запрещает все запуски, нарушающие это условие и предотвращает возможность его нарушения
Единственный возможный результат запуска — 1. В это же время условие
{x := 0 observe x = 1} [1/2] {x := 1 observe x = 1}
намного сложнее, так как весь левый бранч недостижим

=======================================================================================
Левая лекция чувака из яндекса
ВП рассуждает о моделях в реальном мире.
Свойства объектов + Свойства среды == Процесс. На выходе — какие-то данные.
Строим модель объектов, находим только важные свойства, некритичные отбрасываем совсем.
Процесс составляем так, чтобы он был похож на тот, что и в реальности, но может быть представлен куда
проще и тривиальнее. Однако эта модель не может быть использована ирл. Поэтому добавляется шум, чтобы
позволить модели стать более реальной. Т.е.
Свойства объектов + Свойства среды == Процесс + Шум
И вот тут врывается теорема Байеса.
Проблемы вероятностного моделирования:
модель разработать довольно легко (в конкретной предметной области, особенно если она новая), вполть
до часов
юзаем модель байеса на переменные, интересующие в наблюдениях, иногда это невозможно вычислительно,
поэтому имеет смысл использовать приближенные выводы (EP, VMP, MCMC). Эти методы сложны и по
реализации, и по пониманию.
НО ЕСТЬ ХОРОШИЙ ШАНС ПРИДУМАТЬ МОДЕЛЬ, КОТОРАЯ БУДЕТ ЭФФЕКТИВНО ИСПОЛЬЗОВАТЬ МОДЕЛЬ БАЙЕСА БЕЗ
УПОРОТЫХ ПРИБЛИЖЕНИЙ
Все стремятся к простым моделям, ибо реально тяжело.
Идея вероятностного программирования сводится к тому, чтобы указывать просто выходы и интересующие
модели. Движок вероятностного вывода делает все сам.
Формальные языки: ЯП, лол. Идея ВП — описание модели с помощью программы, т.е. подача на вход
свойства интересующих объектов, а потом генерирует случайные данные + добавляет немного шума.
===
Примитивный пример:
2 монетки, орел-решка, проверям упали ли они одинаково.
// model
bool coin1Heads = Bernoilli.Sample(0.5);
bool coin2Heads = Bernoilli.Sample(0.5);
// Bernoilli.Sample(0.5) — ГПСЧ ренерит тру с вероятностью 0.5 (аналогично фолс, внезапно)
bool bothheads = coin1Heads && coin2Heads;
// query
observe bothHeads == false; увидели, что обе монетки не выпали
infer coin1Heads; какая вероятность того, что монетка выпала орлом?
очевидно, что раз всего вариантов 4: оо ор ро рр, но не оо (ибо bothheads == false), то 1/3
===
Этот пример запускаем бесконечное количество раз (лол)
infer задает вопросы
observe смотрит равно ли текущее значение переменной тому, чему должно быть и если не равно,
то всем операторам infer говорит выкинуть сохраненное значение (чтобы они не включили это в
распределение)
=====
Пример:
Линейная регрессия
Есть некоторое значение, считаем, что она примерно линейна. Всё. ТАДА ТАДА ТАМ
Есть точки, каждая обладает вектором признаков, мы считаем скалярное произведение с вектором
весов + шум.

float[,] x = GetFeatuers(); // массив признаков, двухмерный, по 1 измерению — объекты, по 2 —
признаки. Массив всегда наблюдаем.
float [] w = new float[x.GetLength(1)]; — заявили
for (int m = 0; m < w.Length; ++m)
w[m] = Gaussian.FromMeanAndVariance(0, 1); // нормальное распределение с матожид = 0 и дис = 1
// фактически — сделали априорное распределение
float[] y = new float [x.GetLength(0)];
for (int n = 0; n < y.Length; ++n)
{
y[n] = Gaussian.FromMeanAndVariance(0, 0.1); // наварили шума
for (int m = 0; m < w.Length; ++m)
y[n] += w[m] * x[n, m]; // к шуму докинули скалярное произведение вектора признаков
соответствующего объекта с вектором весов
}
observe y == GetOutcomes();
infer w; // спрашиваем какое апостер. распределение при известном y
=====
Выходные значения сильно зависят от движка. Если MCMC, то распределение вышло бы в виде набора
sampleов из апостериорного распределения.
Модель True Skill: если есть игра двух игроков, в которой исход с обязательным победителем, то для
составления уровня мастерства используется сие.
Игровые модели хороши для определения релевантности.
Пусть игрок — число. Число — показатель мастерства. Значение растет пропорционально скиллу.
Как определить кто выиграл, кто проиграл.
Берем мастерство а + шум, берем мастерство б + шум.
Шум дает возможность прогноза на все возможные исходы, а не только строго транзитивные.
double[] skills = new double[PlayerCount];
// навыки каждого игрока
int[] gamePlayer1 = new int[GameCount];
//кто играл первым игроком
int[] gamePlayer2 = new int[GameCount];
//кто играл вторым игроком
bool[] player1Wins = bool[GameCount];
// 1 если выиграл 1

//априорное распределение
for (int p = 0; p < PlayerCount; ++p)
{
skills[p] = Gaussian.FromMeanAndVariance(0, 1);
}
// априорно у всех все одинаково, ибо у нормального распределения довольно легкие хвосты

for (int g = 0; g < GameCount; ++g)
{
int p1 = gamePlayer1[g];
int p2 = gamePlayer2[g];
// берем 2 игроков
double advantage = skills[p1] — skills[p2];
// считаем преимущество первым над вторым
double noisyAdvantage = advantage + Gaussian.FromMeanAndVariance(0, 0.1);
// зашумляем, чтобы так, кто сильнее, все равно мог проиграть
player1Wins[g] = noisyAdvantage > 0;
// условие победы
}

//вероятностная модель задана
Всё, получена апостериорная модель
True Skill through time -> навыкам игроков каждый год дали возможность для изменения
натравили шум с бОльшей дисперсией

Модель DARE
Есть набор ответов на тесты. Ответов нет. Надо найти.
Фактически — задача краудсерчинга.
Решения — Whitehill, BCC, DARE
Студент == абилка == число
Вопрос == сложность + сложность (чем выше, тем сильнее нужен навык студента; exp: вопрос
херово сформулирован)

for (int s = 0; s < StudentCount; ++s)
{
ability[s] = Gaussian.FromMeanAndVariance(0, 1);
}
// способности примерно равны, а отклонения маловероятны
for (int q = 0; q < QuestionCount; ++q)
{
difficulty[q] = Gaussian.FromMeanAndVariance(0, 0.1);
discrimination[q] = Gamma.FromMeanAndVariance(0, 0.01); // распределение на положительной полуоси
// аналогично параметры вопроса
trueAnswer[q] = Discrete.Uniform(AnswerCount);
// истинные ответы не знаем, поэтому кидаем кубик
}

for (int s = 0; s < StudentCount; ++s)
{
for (int q = 0; q < QuestionCount; ++q)
{
double advantage = ability[s] — difficulty[q];
// считаем преимущество студента над вопросом
double noisyAdvantage = Gaussian.FromMeanAndPrecision(advantage, discrimination[q]);
// зашумляем. чем больше различающая способность вопроса, тем меньше зашумим преимущество
// Важно, еще раз: функция генерит из распределения с матожид и точностью (точность = 1/дисперсия)
studentAnswers[s][q] = noisyAdvantage > 0 ? trueAnswer[q] : Discrete.Uniform(AnswerCount);
// если зашумленное больше нуля и он знает и отвечает правильно, иначе он прибегает к случайному
// гаданию и все равно отвечает как-то
}
}

Тезисы DARE:
1) Если много одинаковых ответов, значит вопрос легких и ответ правильный
2) Если студент много раз правильно ответил и это совпадает с выборкой и остальные ответы его будут
тоже правильные
3) Если на вопрос и плохие, и хорошие студенты одинаково ответили, то, значит, у вопроса
высокая дискриминация

========================================================

Модель МО: входные данные из троек (i, a, r(i, a)): i — пользователь, a — продукт, r(i, a) — рейтинг, который i поставил a. Можно свести к матрице.
Две проблемы:
1) Матрица рейтингов очень разреженная: рейтингов меньше, чем пользователей * продукты, поэтому все полости нужно предсказывать
2) Проблема холодного старта: что делать, когда ничего нет? рекомендовать популярное? не оценил. и сколько нужно рекомендовать, чтобы оценка была квалифицированной?

Для решения этих проблем ищем либо похожих покупателей, либо похожие продукты (user-based filtering // item-based filtering соответственно):
Определяем что такое «похожий»:
1) User-based :: Все, что у нас есть — матрица предпочтений. Оставим только известные значения, тогда задача сводится к задаче сравнения двух векторов вещественных чисел. Классическое решение — определение коэффициента Корреляции (критерий Пирсона) как сумма произведений разностей выставленного рейтинга и среднего рейтинга пользователя, деленная на произведение сумму корней из квадратов разности выставленного рейтинга и среднего рейтинга.
2) Item-based :: ищется взвешенное среднее уже оцененных продуктов: к средней оценке по всем параметрам прибавляется частное суммы произведения разности выставленной оценки и среднего, деленное на сумму корреляций пирсона, взятых по модулю.
ИРЛ не получится суммировать такие килограммотонны данных, поэтому формулу округляют до k соседей, максимально схожих и уже оценивших.
Как искать соседей? Для небольших размерностей используются k-d деревья, а для больших — локально-чувствительное хэширование (locally sensitive hashing)

Поскольку матрица сильно разряжена — необходимо это учесть : сингулярное разложение матрицы (SVD): R = UDV^T
Вкратце суть: если есть матрица больших размеров (матрица R размером NxM), но малого ранга (например, разреженная, лол), то ее можно разобрать в произведение матрицы N x f x M, сократив число параметров с NM до (N+M)f
Но основной смысл в том, что SVD дает оптимальное приближение, причем такое, что если в матрице оставить только диагональные элементы (и даже не все, а f штук), то: X = UDV^T = U[диаг.матрица до k]V^T ~ U[диаг.матрица до f]V^T
В матрице D элементы упорядочены по размеру, поэтому обнуление последних элементов тождественно обнулению наименьших.
Чем лучше подобрано f, тем меньше вес конечный
Т.е. каждый пользователь представляется в виде вектора из f факторов ui, а каждый продукт — вектором из f факторов vi, а для предсказания рейтинга берем скалярное произведение.
Рейтинг одного продукта: пользователь бака и всем говорит — вы неудачники, вам 1, либо, наоборот, няша и всем ставит 5. Это надо учесть. С другой стороны — пользователь может выбирать только то, что нужно именно ему, а остальное не оценивает вообще. Поэтому вводят базовые предиакторы (baseline predictors — bia), собирающиеся из базовых предикторов отдельных пользователей bi, базовых предикторов отдельных продуктов ba и среднего рейтинга по базе. Т.е. bia = m + ba +bi
Затем добавляются факторы: с учетом поправки на предикторы можно надеяться получить разумные факторы: ria = bia + vaTui, где va — вектор факторов, представляющих продукт а и ui — вектор факторов, представляющих пользователя i. (T это скалярное произведение)
Считать предикторы как разность от среднего нельзя, ибо они зависят друг от друга и оптимизировать их надо только вместе.
Тогда задача сводится к определению такого разумного фактора ria, что: ria = bia + vaTui. А какие разумны? У которых ошибка минимальна. А как найти ошибку? В общем виде — через сумму квадратов отклонений. А минимизировать функцию можно градиентным спуском по полученной функции ошибки L.

Оверфиттинг и регуляризация:
R Project — хорош для МО
http://habrahabr.ru/company/surfingbird/blog/143455/
Повторить эксперимент

К теме по аналихзу рисков:
страхование киберрисков(в рассеюшке есть два калеки, само по себе очень ново)

Реклама
МО(АР)

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s