Презентация на тему Линейные методы классификации (метод стохастического градиента)

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

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

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

методы обучения

а остальные – выкинуть
аналогия легче рассуждений
Гy(u) показывает, насколько важен

объект обучающей выборки, насколько u близок к классу y

на объекте произошла ошибка

смотрим, насколько оценка правильного класса превышает оценку за другие классы; если M>>0, xi является эталоном

отступ – суть отдаленность от другого класса

такие картинки – показывают, сколько каких объектов находится в

выборке

пограничные объекты особенно важны когда граница изогнута

признаков (будут рассмотрены далее), а не ∧, но здесь

складываются «км с кг»

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

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

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

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

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

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

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

f возвратила на объекте xi :
значение > 0, то относим xi в класс +1,
значение < 0, то относим xi в класс –1,
значение = 0, то… относим xi, например, в класс +1

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

если y и f одного знака, то ошибки нет, и чем больше абсолютное значение величины Mi(w), тем надёжнее классификация; если y и f разных знаков, то ошибка, и если большое абсолютное значение Mi(w), то это однозначно выброс

от поверхности

ошибок на обучающей выборке (эмпирический риск)
преимущества функции потерь L(M): 1.

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

огрубление характеристики – ошибка или не ошибка – теряется информация о надёжности i-ого объекта

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

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

замена пороговой функции потерь на непрерывную

методы решения с помощью градиента задач, сводящихся к нахождению

экстремумов функции

современный принцип: можно как угодно менять функции потерь и получать тот или иной по качеству метод, потому что решение сильно зависит от L(M) – зависит от того, как мы штрафуем за ошибки

градиент показывает направление самого быстрого возрастания функции

функцию
будем считать, что объекты заданы векторами из Rn, т.е. имеется

n числовых признаков f1…fn и мы составляем их линейную комбинацию с весами w

технический прием для сокращения записи

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

x и w теперь находятся в пространстве Rn+1

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

обрабатывает и передает информацию посредством электрических и химических сигналов.
Аксон – обычно длинный отросток нейрона, приспособленный для проведения возбуждения и информации от тела нейрона или от нейрона к исполнительному органу.
Дендриты – как правило, короткие и сильно разветвлённые отростки нейрона, служащие главным местом образования влияющих на нейрон возбуждающих и тормозных синапсов (разные нейроны имеют различное соотношение длины аксона и дендритов), и которые передают возбуждение к телу нейрона.
Нейрон может иметь несколько дендритов и обычно только один аксон. Один нейрон может иметь связи со многими (до 20 тысяч) другими нейронами.

между двумя нейронами или между нейроном и получающей сигнал

эффекторной клеткой. Служит для передачи нервного импульса между двумя клетками, причём в ходе синаптической передачи амплитуда и частота сигнала могут регулироваться.

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

между двумя нейронами или между нейроном и получающей сигнал

эффекторной клеткой. Служит для передачи нервного импульса между двумя клетками, причём в ходе синаптической передачи амплитуда и частота сигнала могут регулироваться.

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

между двумя нейронами или между нейроном и получающей сигнал

эффекторной клеткой. Служит для передачи нервного импульса между двумя клетками, причём в ходе синаптической передачи амплитуда и частота сигнала могут регулироваться.

т.е. аналогия с линейным классификатором полная: величина заряда, который приходит в клетку через синапсы – это признаки f, синоптические связи – это веса w,
а коэффициент w0 – это тот порог, который необходим для того, чтобы началась генерация импульса

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

+1
в 1940-1950 годы проводилось большое число нейрофизиологических экспериментов в

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

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

эти механизмы были открыты сначала в нейрофизиологии, а потом математики усмотрели в них градиентную оптимизацию некоторого функционала качества

это клетка или что-то ещё – не важно
задан некий

функционал потерь, который нужно минимизировать

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

каждый следующий шаг – идти в направлении антиградиента

градиент показывает направление самого быстрого возрастания функции

вектор w должен сместиться на величину η (эта)

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

очень много (выборка избыточна), то формула говорит о том,

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

преимущество метода на больших данных: можно обучиться, не просмотрев все данные

выход: идти не по всей обучающей выборке, а по подвыборке; а если обобщить это, то можно:
1. брать только один случайный объект – одно слагаемое этой суммы (см. формулу) и на его основании подправить вектор весов w;
2. брать другой случайный объект и на его основании подправить вектор весов w и т.д.
ЗМ. вектор весов будет метаться, но «в правильном направлении»

закон больших чисел говорит о том, что суммы можно приближенно вычислять так: взять около 30 случайных слагаемых и мы значительно приблизимся к сумме

на тему эвристик
или «градиентный шаг»
текущая оценка нужна для учёта

средних потерь классификатора на выборке

не всегда

пропустили выбранный объект через классификатор

6: примеряем формулу для выбранного объекта

λ можно назначить 1/k, где k – это количество усредняемых потерь εi

7: способ грубо оценить Q, не пересчи-тывая его на всей выборке

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

избежать «паралича нейронной сети»

повлияют на модификацию вектора w, а близкие – наоборот
это объекты

из окрестности разделяющей гиперплоскости

отступ – это расстояние до гипер-плоскости

ЗМ. нарисовать рисунок подхода к увеличению скорости сходимости

темп обучения?
если устремить к 0, но не слишком быстро и

не слишком медленно

подбирать шаг в конкретной задаче – это искусство

задача одномерной оптимизации

чтобы разделяющая поверхность прошла как можно дальше от объектов
приходит

с опытом

линейная комбинация других признаков (доход, доход жены, доход семьи)
n >

l

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

малые изменения x (при таких w) или изменение обучающей выборки могут приводить к радикальному изменению решения

классификатор в виде конструкции как на прошлой лекции
скалярное произведение

вектора признакового описания объекта x и вектора весов w

вектор w – это направляющий вектор разделяющей гиперплоскости, а w0 – это скаляр, сдвиг гиперплоскости

используем аппроксимацию пороговой функции потерь