Методы машинного обучения презентация

метод опорных векторов
Методы восстановления регрессии
Нелинейная и непараметрическая регрессия
Байесовские методы классификации
Поиск ассоциативных правил
Нейронные сети и бустинг
Прогнозирование временных рядов

Видеолекции: http://shad.yandex.ru/lectures
Презентации и текст: http://www.machinelearning.ru/wiki
Машинное обучение (курс лекций, К.В.Воронцов)

информативности



Решающие деревья

неточности, нечеткости, прецеденты и т.п.
Ожидания: правильность и понятность людям (что весьма полезно в определенных предметных областях, таких как медицина, геология, социология, техническая диагностика и т.д.).
Идея получить не только решающее правило, но и понять, разумно ли оно, а также выявить какие логические закономерности оно сформировало на основе имеющихся данных.

закономерность, которую нужно построить для каждого класса

противоречивая закономерность (бесполезна, не несет никакой информации о классах)

«недоклассификатор». Каждый из таких «недоклассификаторов» не может решить задачу, но если набрать их достаточное количество и построить композицию, то она – сможет.
n должно быть как можно меньше, p – как можно больше.
Эти требования могут входить в противоречия, поэтому необходимо найти разумный компромисс.
Решаемые задачи:

Определить, что есть закономерность (на основе статистических критериев).
Какой вид могут иметь правила (чаще это конъюнкции простых условий).
Научиться их строить (это, как правило, переборные алгоритмы).
Понять, как объединять правила в композиции (существует много разных идей – независимо, последовательно и т.д.).

указано с некоторой «уверенностью» (риски отрицательного исхода и дефолта); вероятность уверенности находится из обучающей выборки (доля отрицательных исходов)

такие правила соответствуют способу мышления врача или кредитного аналитика

из 6 объектов одного класса (слева) и 6 объектов другого класса (справа);
задача: установить, какое правило породило эти объекты

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

большой / маленький

фигуры существенно больше, чем ширина /
выпуклая оболочка фигуры имеет одинаковую длину и ширину

том, чтобы научить компьютер «видеть такие закономерности», т.е. не только сканировать рисунок, но и вычислять информативные признаки; при том, что количество информации для их выделения весьма велико, что наглядно демонстрирует этот тест (нужно не только понять, что это спираль и установить, в какую сторону она закручена)

спирали против часовой стрелки / спирали по часовой стрелке

/ больше белых фигур

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

на разных выпуклостях / на одной выпуклости

/ отсутствие осевой симметрии

ветке / точка не на центральной ветке

можно придумать и более хитрые задачи (фотографии мужчин/женщин, марки машин, виды животных и растений, картины в подлиннике и в копии и т.д.)
НУЖНО УМЕТЬ ВЫДЕЛЯТЬ ВАЖНЫЕ ПРИЗНАКИ

даны

пространство поиска зависит от задачи

определяем, что является критерием поиска (свертка двух критериев)

эвристики для сокращения полного перебора, который лучше, но долгий

признак – это тоже функция от объекта, поэтому закономерность может являться признаком

также односторонним

задачи дифференциальной диагностики (должны подтвердиться хотя бы несколько симптомов)

число признаков j должно быть маленьким, чтобы закономерность поняли люди

симптом – это признак, синдром – их совокупность для заболевания

(будут рассмотрены далее), а не ∧, но здесь складываются «км с кг»

снова используется небольшое число признаков j (некое подпространство)

метрика r, аналог того, что было в метрических методах (эталонность сравнения)

способ вычисления оценки

используется прецедентная логика в проверке и интерпретации результата

если вокруг точки x0 описали шар радиусом w0, в котором много объектов одного класса (а других –
мало), то это закономерность

способ вычисления оценки

адекватны, т.к. для них легко найти контрпримеры (см. след. слайд) →

для определения лучшей

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

хор.

плох.

хор.

плох.

хор.

плох.

Фишер энтропия бустинг

берем пары предикатов: чтобы первый был явно хорошей закономерностью, а второй – явно нет, но формула дала бы равную оценку информативности

примеры успешных сверток

и КАК сворачивать два критерия p и n, но есть с десяток разумных способов это сделать

непредсказуемости информации, неопределенность появления какого-либо символа алфавита.
Если есть два взаимоисключающие исхода, которым приписаны вероятности (которые в сумме дают 1), то мы можем связать с этими исходами количество информации, которое они несут. «Чем меньше вероятность исхода, тем больше информации мы получаем, если этот исход реализуется». Энтропия определяется как мат.ожидание количества информации. Первое событие берем с вероятностью q, второе (1-q) и получаем формулу (см. выше).
Вычисляем энтропию, которой обладает обучающая выборка, ДО того, как узнали предикат R, и ПОСЛЕ того. Разность этих энтропий покажет, сколько информации R несет о делении выборки на классы. Разность энтропий называется информационным выигрышем.

это статистические тесты.
Пусть предикат R, покрывающий долю объектов выборки, и класс с, также покрывающий долю объектов, (если трактовать их как вероятностные события) – это независимые события.
Пусть предикат R зафиксирован, а у классов есть вероятность CPN+P вариантов распределиться по выборке, и мы считаем все эти варианты равновероятными. Т.е. это другой способ сказать, что предикат и класс – это независимые случайные величины.
Интуиция говорит, что чтобы R был закономерностью, n/p должно быть много меньше N/P, а статистика выдает точную количественную формулу (см. выше), которая позволяет судить о том, насколько не случайно это событие (соответствующее соотношение n и p).

выделяет предикат R

– log используется для того, чтобы получить величину, которая чем больше, тем лучше

чтобы предикат R был закономерностью, должен быть перекос в сторону p

движения вправо вниз».
На этапе ПОСТРОЕНИЯ правил.

розовая область – это неслучайность (или статистическая закономерность), а красно-зеленая область – это логические закономерности

это пространство, в котором находятся правила; каждая точка пространства соответствует правилу с характеристиками p и n (закономерности находятся в правом нижнем углу)

p-n пространство

те, над которыми нет доминанта

нашли недоминируемые закономерности (лучше них нет), сохранили их, затем удалили их с картинки и «обнажили» второй слой, из которого также выбираются недоминируемые и т.д.; далее из отобранного конструируем классификатор

вид законо-мерностей не важен (∧, шары и т.п.)

подходят следующие частные случаи

общая эвристика, которая может быть реализована по-разному

по любому критерию

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

одно или несколько

до листа

записать как конъюнкцию условий вершин, через которые он прошел (некоторые – с отрицаниями)

дерево покрывает все пространство и развора-чивается в список конъюнкций, поэтому решающие деревья относят к логическим методам

строящая поддерево

когда нечего расщеплять, создается лист

когда есть что расщеплять, строится функционал β (по критерию ветвления I), который пытается разбить объекты так, чтобы какие-то классы желательно целиком ушли в одно из поддеревьев (см. след. слайд)

построен неинформативный предикат (даже когда получена просто малая мощность множества); в этом случае листу приписывается (мажоритарный) класс – которого было больше в выборке U

было несколько классов

в начале передается вся выборка U

объектов, принадлежащих одному классу, пошли в одно поддерево

насколько много информации о разделении выборки на классы несет β; разность энтропии до того, как его узнали, и после дает выигрыш в информации

двойственный критерий предикат β тем более информативен, чем больше пар объектов, принадлежащих разным классам, пошли в разные поддеревья (разделимость ЛУЧШЕ объединения)

не знать значения всех признаков, но тем не менее успешно классифицировать

оценивается вероятность того, что объекты идут по одной или по другой ветке (для всех ветвей)

если для объекта отсутствует признак, объект исключается из оценки информативности

четко: 0 или 1

размыто: вероятность дочерней вершины

построены по малым (статистически ненадежным) подвыборкам

деление, потому что алгоритм не видит возможный следующий шаг

фрагмент шахматной доски

– до которых не дошел ни один объект контрольной выборки

от этой вершины удаляется поддерево и она заменяется на лист

если до этой вершины дошла какая-то часть объектов, считаем число ошибок

срезали правое поддерево

срезали левое поддерево

срезали все

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

уровне используется один признак, для каждого признака устанавливается один порог

композиция таких конструкций используется в Матрикснет Яндекса

возникает довольно непрозрачный алгоритм

класса (это ухудшит информативность)
можно объединять тройки соседних интервалов (крестики, нолики, крестики) до тех пор, пока увеличивается информативность (огрубляем тонкости)

разбиение на информативные зоны

ось значений признака на значения, чтобы сократить перебор (чтобы перебирать не все точки)

если выборка 1000, то бьем по 100

здесь в каждом разбиении может быть разное количество объектов

предыдущий вариант

хорошо работает для больших данных (для выборок избыточной длины)