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

Содержание

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

Слайд 1Методы машинного обучения
5. Логические методы классификации


Слайд 2Методы классификации
Метрические методы классификации
Логические методы классификации
Линейные методы: метод стохастического градиента
Линейные методы:

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

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


Слайд 3План лекции

Понятие закономерности
Интерпретируемость
Информативность

Алгоритм ID3
Небрежные решающие деревья – ODT
Бинаризация данных


Понятия закономерности и

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



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

Слайд 4Идея логических методов
Смоделировать человеческую логику принятия решений в ситуациях, когда есть

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

Слайд 5Логическая закономерность (определение и свойства)
предсказательная сила (способность)
p – positive
n – negative
непротиворечивая (чистая)

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

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


Слайд 6Логическая закономерность (требования и задачи)
Отдельная закономерность – это еще не классификатор, это

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

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


Слайд 7Пример реализации свойства интерпретируемости
естественное накладывание пороговых условий для количественных признаков
отнесение к классу

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

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


Слайд 8Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
дано: обучающая выборка

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

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

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


Слайд 9Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
треугольники / четырехугольники


Слайд 10Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
длина выпуклой оболочки

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

Слайд 11Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
идея была в

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

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


Слайд 12Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
больше черных фигур

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

Слайд 13Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
видно, насколько разные

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

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


Слайд 14Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
наличие осевой симметрии

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

Слайд 15Как понимают закономерность люди? Тесты М.М. Бонгарда [Проблема узнавания, 1967]
точка на центральной

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

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


Слайд 16Что нужно делать, чтобы извлекать закономерности из данных?
в учебных задачах признаки

даны

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

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

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

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


Слайд 17В каком виде ищут закономерности? (часто используемые виды)
пороговое условие может быть

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

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

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

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


Слайд 18В каком виде ищут закономерности? (часто используемые виды)
получаем линейную комбинацию признаков

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

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

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

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

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

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

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


Слайд 19Часто используемые критерии информативности
безошибочность
точность
линейная функция стоимости
относительная точность
все предложенные здесь меры не очень

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

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


Слайд 20Нетривиальность проблемы свертки двух критериев (контрпримеры для них)
свои
чужие

Рассматриваем разные пары правил –

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

хор.

плох.

хор.

плох.

хор.

плох.

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

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

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


Слайд 21Часто используемые критерии информативности (обзор)
нет однозначного ответа на то, КАКОЙ критерий лучше

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

Слайд 22Часто используемые критерии информативности (IGain)
частота
частота
энтропия всей выборки
энтропия части выборки
энтропия части выборки
Информационная энтропия – мера неопределенности или

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

Слайд 23Часто используемые критерии информативности (IStat)
Другая идеология того, как получить оценку информативности –

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

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

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

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


Слайд 24Иллюстрация к тому, где находятся закономерности
Статистический критерий: «информативность правил увеличивается по мере

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

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

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

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


Слайд 25Парето-критерий информативности в (p, n)-плоскости
пример того, как можно отбирать законо-мерности
недоми-нируемые – это

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

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

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


Слайд 26Как происходит поиск информативных закономерностей?
алгоритмов множество, здесь представлена общая идея, под которую

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

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

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

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

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


Слайд 27Определение бинарного решающего дерева
предикат
метка класса
у каждого объекта есть только одна возможность дойти

до листа

Слайд 28Пример решающего дерева
дерево может быть несбалансированным


Слайд 29Решающее дерево, покрывающее набор конъюнкций
условие попадание объекта в терминальную вершину (лист) можно

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

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


Слайд 30Жадный алгоритм построения дерева ID3
рекурсивная процедура, берущая на входе часть выборки и

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

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

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

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

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

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


Слайд 31Разновидности многоклассовых критериев ветвления
предикат β тем более информативен, чем больше пар

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

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

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


Слайд 32Обработка пропусков (логические алгоритмы толерантны к пропускам)
дерево обладает тем свойством, что можно

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

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

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

четко: 0 или 1

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


Слайд 33Решающие деревья ID3: достоинства и недостатки
любой признак любого типа можно бинаризовать
иногда листы

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

Слайд 34Иллюстрация того, что жадный ID3 переусложняет структуру дерева
задача исключающего ИЛИ
абсолютно неинформативное

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

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


Слайд 35Редукция дерева («стрижка кустов», pruning: С4.5, CART)
хотим понять, какие вершины оказались лишними

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

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

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

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

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

срезали все

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


Слайд 36Небрежные решающие деревья – ODT (Oblivious Decision Tree)
идея строить деревья быстро
на каждом

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

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


Слайд 37Алгоритм обучения ODT ODT (Oblivious Decision Tree)
при формальной постановке простой задачи

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

Слайд 38Задача бинаризации вещественного признака
не надо ставить пороги между объектами одного и того же

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

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


Слайд 39Способы разбиения области значений признака на зоны
идея того, как еще можно дробить

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

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

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

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

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


Слайд 40Резюме лекции


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика