Москва, 27.02.2010 Конспиролог Андрей Гулин Matrixnet. - презентация

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

2 Линейная регрессия Дано: K N-мерных самплов {x i } для каждого известно значение функции {f i } Найти: вектор a, такой что a T x i = f i Решение: a=(X T X) -1 X T f

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

4 L1 регуляризация Итеративный алгоритм L1 регуляризации У нас есть текущий остаток r i, который в начале равен f i На каждой итерации мы Выбираем самый похожий на r i фактор и считаем с каким множителем α нам нужно его брать Добавляем λ α к коэффициенту при этом факторе ( λ < 1) Считаем новый остаток r i

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

6 Decision Tree F1 > 3 F2 > 3 F1 > 6

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

8 Bagging На каждой итерации будем брать не все самплы, а их случайное подмножество Магическим образом более устойчиво Defeats boosting impossibility argument ( _rcn/icml08_long_rcn_01.ppt) _rcn/icml08_long_rcn_01.ppt

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

10 TreeNet TreeNet товарища Friedman-a это Boosted Decision Tree с Bagging и ограничением на минимальное количество самплов в листе

11 MatrixNet

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

13 Oblivious Trees F1 > 3 F2 > 3

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

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

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

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

18 Luce-Plackett model Luce-Plackett model позволяет нам назначить вероятности всем перестановкам, если у нас есть веса документов {w i } Вероятность перестановки вычисляется рекурсивно. Вероятность поставить документ k на первое место равна w k / (w 1 + w 2 + … + w n ), далее аналогично считаем вероятность выбрать второй документ из оставшихся и т.д. Произведение этих вероятностей равно вероятности перестановки.

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

20 Вопросы?