Ml 13

33 %
67 %
Information about Ml 13

Published on February 25, 2014

Author: compscicenter

Source: slideshare.net

Instance based learning И. Куралёнок, Н. Поваров Яндекс СПб, 2013 И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 1 из 26

Содержание 1 2 Принцип локальности k-ближайших соседей kNN Методы прототипирования 3 4 5 Лирическое отступление: проклятье размерности Адаптивные соседи Поиск k-ближайших соседей kd-tree Locality-Sensitive Hashing И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 2 из 26

Принцип локальности(совсем не физика) Близкие точки похожи! что значит близки? lq, косинусная мера, Mahalanobis distance, KL-divergence, более хитрые преобразования, Metric Learning etc. что значит похожи? близкие значения целевой функции, возможности простой аппроксимации, схожее распределение, etc. что значит точки? точки из learn, центройды классов, прочие прототипные точки. И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 3 из 26

Алгоритм k-NN 1 2 3 Вычислим значения факторов из интересующей нас точки. Найдём k ближайших соседей по выбранной мере из learn’а. Аггрегируем значения искомой характеристики для найденных точек (попробуем провести отдельный семинар). И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 4 из 26

Параметры k-NN Сколько точек выбрать? ничего лучше подбора по validate или crossfold validation не придумали Как искать соседей? см. вторую часть Способ агрегации. голосовалка, усреднение, моделирование распределения Далее речь пойдет про мульти-классификацию на K классов. И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 5 из 26

Сколько точек выбрать I И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 6 из 26

Сколько точек выбрать II И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 7 из 26

Свойства k-NN Очень часто работает! Простота реализации и наглядность. Ничего не требует на стадии обучения. Известная оценка сверху эффективности при отсутствии bias’а в learn’е. BE = 1 − p(x|k ∗ ) E = K p(x|k)(1 − p(x|k)) i=1 BE ≤ E ≤ 2BE Часто требователен на фазе решения (!) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 8 из 26

Основные способы прототипирования Может много точек и не надо? Будет быстрее работать, глаже границы. Как выбрать прототипные точки: выбрать рандомно; покластеризовать каждый класс(например k-means’ами) и назначить центроиды прототипами; выбрать как-нибудь точки и подвигать их подальше от границ классов. И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 9 из 26

Learning Vector Quantization 1 2 построить вашим любимым методом прототипные точки; до сходимости уменьшая (learning rate): 1 2 Случайно, равномерно выберем точку x из learn’а с возвращением Найдём ближайший прототип прототип нужного класса: подвинем его ближе mjt+1 = mjt + (x − mjt ) "чужой"прототип: подвинем его подальше mjt+1 = mjt − (x − mjt ) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 10 из 26

Проклятье размерности Что происходит с расстояниями когда размерность увеличивается? Проведем простой опыт: будем равномерно выбирать точки из кубика [0, 1]n ⊂ R. Оказывается, что при увеличении n: Точки все ближе “жмутся” к краю Углы между точками выравниваются Окрестности все чаще упираются в границы Для того, чтобы пространство было плотным надо слишком много точек ⇒ Большая размерность — зло для kNN и не только для него! И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 11 из 26

Discriminant Adaptive Nearest-Neighbor (DANN) Идея: а давайте в расстоянии учитывать локальную топологию в искомой точке Выберем много ближайших соседей (например m=50): T = mΣ = m (xi − µ(x))(xi − µ(x))T i=1 = K (xi − µk (x))(xi − µk (x))T k=1 i∈Ik + K (µk (x) − µ(x))(µk (x) − µ(x))T k=1 =W +B Пересчитаем все расстояния для k-NN: D(x, x0 ) = (x − x0 )T D(x − x0 ) 1 1 1 1 D = W − 2 (W − 2 BW − 2 + E )W − 2 Заметим, что ранги матриц, которые мы используем не более m. Получается очень точный, но крайне медленный метод. И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 12 из 26

DANN результат И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 13 из 26

Поиск ближайших соседей Это область на годовой курс, так что за поллекции мы ничего не успеем :). Линейный поиск Разбиение пространства Чувствительное к локальности хеширование (LSH) Кластерный/Пожатый поиск Деревья в пространстве меньшей размерности И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 14 из 26

kd-дерево Идея: разложим множество по поторому будем искать в бинарное дерево с простыми условиями и конкретными точками в узлах. Будем надеяться на правило треугольника (не подходит для cosine(!)) Некоторые свойства: Один из самых простых способов поиска ближайших соседей Работает только в малых размерностях Затратные алгоритмы перестроения (если нужна динамика смотрим R-деревья) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 15 из 26

kd-дерево: построение 1 2 3 По циклу, или рандомно выбираем ось. Ищем точку, разбивающую множество на как можно более равные части. Повторяем 1-2 для каждого из получившихся подмножеств Сложность: O(n log n) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 16 из 26

kd-дерево: построение (в картинках) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 17 из 26

kd-дерево: поиск 1 2 3 Бежим по бинарному дереву поиска Когда добежали, сохраняем листовую точку как x ¯ - текущую лучшую Бежим обратно вверх по дереву: 1 2 если текущая точка лучше то теперь она x ; ¯ сравниваем расстояние от точки-запроса до гиперплоскости текущего уровня пересекает: не повезло, бежим в поддерево не пересекает: повезло, бежим наверх Повторяем 1-3 для каждого из получившихся подмножеств пока делятся Сложность сильно зависит от множества: в лучшем 1 случае O(log n), в худшем O(nN 1− n ) Классический пример проклятия размерности. 4 И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 18 из 26

kd-дерево: поиск (в картинках) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 19 из 26

kd-дерево: свойства 1 2 3 Необходимо правило треугольника Исходит из одинаковости направлений Работает только в малых размерностях. ⇒ точно искать в реальных условиях не получается, будем неточно И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 20 из 26

Немного определений Рандомизированнный R-ближайший сосед если есть R-соседи, то алгоритм должен вернуть каждого из них с вероятностью 1 − δ Р-я c-аппроксимация R-ближайшего соседа ((c, R) − NN) если есть R-сосед, то алгоритм должен вернуть хотя бы одного cR-соседа с вероятностью 1 − δ И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 21 из 26

Locality-Sensitive Hash Functions H = {h|h : Rn → Z+ }, (R, cR, p1 , p2 ) : p − q ≤ R ⇒ pH (h(p) = h(q)) ≥ p1 p − q ≥ R ⇒ pH (h(p) = h(q)) ≤ p2 Понятно, что хотим p1 > p2 И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 22 из 26

LSH алгоритм Построение: 1 2 Выберем L-функций семейства Hk Поделим все данные на кусочки с одинаковыми значениями gi = (hi,1 , ..., hi,k ) Поиск по точке q: 1 Выкинем j ∼ U{1, ..., L} 2 Найдем значение Lj (q) и соответствующий этому значению “кусочек” 3 Линейно поищем в “кусочке” 4 Одно из двух: 1 повторим 1-3 пока не найдется L точек (включая дубли) ближе чем R. 2 переберём все L-функций. И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 23 из 26

Свойства LSH Первая стратегия: с L = 3L, для любой пары ln p1 (R, δ), ∃L = O(N ln p2 ), гарантирующий (c, R) − NN Вторая стратегия: гарантирует рандомизированного R ближайшего соседа при δ = δ(k, L) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 24 из 26

Некоторые известные семейства функций l1 : возьмём w >> R, si ∼ U[0, w ], i = 1, ..., n, hs1 ,...,sn = ( (x1 − s1 ) (xn − sn ) , ..., ) w w ls : возьмём T x+b w >> R, ri ∼ N(0, 1), hw ,r ,b = [ r w ] при δ = δ(k, L) косинусная мера: возьмём ri ∼ N(0, 1), hr = sign(x, r ) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 25 из 26

Что мы сегодня узнали Instance based learning Иногда можно использовать learn в качестве решающей функции Есть проклятье размерности, которое нам мешает Можно учитывать проклятье при построении метода Поиск ближайших соседей Это большая область Если размерность мелкая и есть правило треугольника, то можно искать точно (kd-tree, r-tree) Можно искать неточно, но с гарантиями (LSH) И. Кураленок, Н. Поваров, Яндекс Санкт-Петербург, 2013 Стр. 26 из 26

Add a comment

Related presentations

Related pages

ML 13 - Baulaser & Vermessunggeräte - Rolf Hartmann

Der ML-13 ist ein halbautomatischer Doppelneigungslaser, der abgesehen von Scannen, FB und Drehzahleinstellung dieselben Eigenschaften wie der ML-14i aufweist.
Read more

Nikon ML-L3 Infrarot-Auslöser: Amazon.de: Kamera

Nikon ML-L3 Infrarot-Auslöser: Amazon.de: Kamera. Amazon.de Prime testen Elektronik & Foto Los. Alle Kategorien. DE Hallo! Anmelden Mein ...
Read more

ML-13 Mockrehna Strelln - RWD (Raketen- und ...

Munitionslager - 13 (ML-13), Standort, Struktur ... Hauptaufgaben • Aufbewahrung von Munition aller Kaliber und Verwendungsarten
Read more

essie Nagellack luxedo #48, 13.5 ml: Amazon.de: Beauty

essie Nagellack luxedo #48, 13.5 ml bei Amazon. Große Auswahl an Farblack in Beauty zu günstigen Preisen.
Read more

Passion 100 ml weiss 13 mm RB - flaschenbauer.de

Passion 100 ml weiss 13 mm RB - Kleine Flasche mit großem Herz. Die Motivflasche Passion in Herzform hat 100 ml Volumen und ist mit einer 13 mm ...
Read more

Liter in Milliliter umrechnen - Volumen online konvertieren

Rechnen Sie Volumen-Einheiten um. Umwandeln von Liter in Milliliter, konvertieren Sie l in ml . Einfache Einheitenrechnungen im Bereich Fläche, Volumen ...
Read more

Infrarotfernauslöser ML-L3 Fernsteuerung Konnektivität ...

Infrarotfernauslöser ML-L3 . Lokalen Händler finden; Nikon Store; Dieses Produkt registrieren; Support erhalten; Seite teilen. Lokalen Händler finden ...
Read more

Mercedes-Benz ML 320 CDI Gebrauchtwagen – mobile.de

Sie suchen einen Mercedes-Benz ML 320 CDI in Ihrer Nähe? Finden Sie Mercedes-Benz ML 320 CDI Angebote in allen Preiskategorien bei mobile.de ...
Read more

Mercedes -Benz ML 350 Gebrauchtwagen – mobile.de

Sie suchen einen Mercedes-Benz ML 350 in Ihrer Nähe? Finden Sie Mercedes-Benz ML 350 Angebote in allen Preiskategorien bei mobile.de – Deutschlands ...
Read more

Samsung Deutschland - Smartphone | Haushaltsgeräte | TV

Entdecken Sie die innovative Welt von SAMSUNG! Infomieren Sie sich hier über alle SAMSUNG Produkte & Support und besuchen Sie unseren neuen Online Shop!
Read more