'

Matrixnet

Понравилась презентация – покажи это...





Слайд 0

Москва, 27.02.2010 Конспиролог Андрей Гулин Matrixnet


Слайд 1

Линейная регрессия Дано: K N-мерных самплов {xi} для каждого известно значение функции {fi} Найти: вектор a, такой что aTxi= fi Решение: a=(XTX)-1XTf


Слайд 2

Регуляризация Когда данных мало простое решение не работает Нужна какая-то дополнительная информация, например, мы можем сказать, что мы хотим “маленький” или “простой” вектор a Меры простоты: L0 = feature selection L1 = lasso L2 = ridge = по Тихонову [a=(XTX+?I)-1XTf]


Слайд 3

L1 регуляризация Итеративный алгоритм L1 регуляризации У нас есть текущий “остаток” ri, который в начале равен fi На каждой итерации мы Выбираем самый похожий на ri фактор и считаем с каким множителем ? нам нужно его брать Добавляем ?? к коэффициенту при этом факторе (? < 1) Считаем новый остаток ri http://www-stat.stanford.edu/~tibs/lasso.html


Слайд 4

Нелинейные модели Если бы у нас были пропорциональные релевантности независимые факторы, нам бы хватило линейной регрессии Это не так и нам понадобятся нелинейные модели Полиномиальные “Нейронные сети” Decision Trees …


Слайд 5

Decision Tree


Слайд 6

Boosting Построение strong learner как комбинации “weak learners” Связь с L1 регуляризацией weak learner = единственный фактор с коэффициентом strong learner = линейная регрессия c L1 регуляризацией Для более сложного weak learner boosting дает сложно формализуемую sort of L1 регуляризацию


Слайд 7

Bagging На каждой итерации будем брать не все самплы, а их случайное подмножество Магическим образом более устойчиво Defeats boosting impossibility argument (http://velblod.videolectures.net/2008/pascal2/icml08_helsinki/long_rcn/icml08_long_rcn_01.ppt)


Слайд 8

Limit on decision tree leafs Дисперсия ошибки значения в листе пропорциональна 1/N, где N – количество самплов в листе Введем ограничение – в кошерном дереве должно быть не меньше 10 самплов обучающей выборки на лист Наш лимит ограничивает ошибку аппроксимации “выравнивая” ее по выборке


Слайд 9

TreeNet TreeNet товарища Friedman-a это Boosted Decision Tree с Bagging и ограничением на минимальное количество самплов в листе http://www.salford-systems.com/doc/GreedyFuncApproxSS.pdf http://www.salford-systems.com/doc/StochasticBoostingSS.pdf


Слайд 10

MatrixNet http://seodemotivators.ru/


Слайд 11

MatrixNet MatrixNet отличается в 3-х моментах Использование Oblivious Trees Регуляризация значений в листах вместо ограничения на количество самплов в листе Зависимость сложности модели от итерации (начинаем с простых моделей, заканчиваем сложными)


Слайд 12

Oblivious Trees


Слайд 13

Регуляризация в листьях Вместо ограничения на количество самплов в листьях будем “регуляризовать” значение в листе Например, если домножить значение в листе на sqrt(N/(N+100)), где N – число самплов в листе, то результаты улучшатся. Оптимальный способ регуляризации, видимо, зависит от выборки


Слайд 14

Другие целевые функции А что, если вместо квадратичной ошибки мы хотим оптимизировать что-нибудь другое? Например, для задач классификации больше подходит средний log(p), где p – вероятность, назначенная моделью правильному ответу Получаем обычную задачу максимизации функции, которую можно решать Градиентным спуском = gradient boosting = greedy function approximation Методом Ньютона = logit boost для классификации


Слайд 15

Gradient boosting На каждом шаге boosting-a вместо невязки ri мы аппроксимируем производную целевой функции в текущей точке Размер шага зависит от величины производной, т.е. от гладкости функции Вместо шага по производной в текущей точке мы можем посчитать куда приведет нас производная и шагать в направлении финальной точки траектории


Слайд 16

Ranking А что же делать, если мы хотим научиться ранжировать? Целевая функция для ranking (NDCG/pFound/whatever) задана на порядках и разрывна (описание pFound http://romip.ru/romip2009/15_yandex.pdf) Нужна какая-то непрерывная замена. Замены делятся на классы Pointwise (rmse, классификация, …) Pairwise (RankNet, …) Listwise (SoftRank, …)


Слайд 17

Luce-Plackett model Luce-Plackett model позволяет нам назначить вероятности всем перестановкам, если у нас есть веса документов {wi} Вероятность перестановки вычисляется рекурсивно. Вероятность поставить документ k на первое место равна wk / (w1 + w2 + … + wn), далее аналогично считаем вероятность выбрать второй документ из оставшихся и т.д. Произведение этих вероятностей равно вероятности перестановки.


Слайд 18

Expected pFound Для каждой перестановки мы можем посчитать ее pFound(perm). Также мы знаем вероятность этой перестановки PLP(perm) Просуммировав pFound(perm) * PLP(perm) по всем перестановкам получим expected pFound Expected pFound непрерывен и мы можем максимизировать его с помощью gradient boosting Вместо pFound мы можем подставить любую нужную нам меру


Слайд 19

Вопросы?


×

HTML:





Ссылка: