2010 Лекции МОТП (Ветров) (1185317), страница 3
Текст из файла (страница 3)
статистикиНеполнота признакового описанияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучениеНапоминание• Отдельные признаки могут отсутствовать у некоторыхобъектов. Это может быть связано с отсутствиемданных об измерении данного признака для данногообъекта, а может быть связано с принципиальнымотсутствием данного свойства у данного объекта• Такое часто встречается в медицинских и химическихданных• Необходимы специальные процедуры, позволяющиекорректно обрабатывать пропуски в данных• Одним из возможных способов такой обработкиявляется замена пропусков на среднее по выборкезначение данного признака• По возможности, пропуски следует игнорировать иисключать из рассмотрения при анализесоответствующего объектаПротиворечивость данныхЛекция 1.РазличныезадачимашинногообученияЖуравлев,Ветров• Объекты с одним и тем же признаковым описаниеммогут иметь разные исходы (принадлежать к разнымклассам, иметь отличные значения регрессионнойпеременной и т.п.)Некоторыезадачимашинногообучения• Многие методы машинного обучения не могутОсновныепроблемымашинногообучения• Необходимо заранее исключать или корректироватьМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучениеНапоминаниеработать с такими наборами данныхпротиворечащие объекты• Использование вероятностных методов обученияпозволяет корректно обрабатывать противоречивыеданные• При таком подходе предполагается, что исход t длякаждого признакового описания x есть случайнаявеличина, имеющая некоторое условное распределениеp(t|x)Разнородность признаковЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучениеНапоминание• Хотя формально предполагается, что признакиявляются вещественнозначными, они могут бытьдискретными и номинальными• Номинальные признаки отличаются особенностямиметрики между значениями• Стандартная практика состоит в замене номинальныхпризнаков на набор бинарных переменных по числузначений номинального признака• Текстовые признаки, признаки-изображения, даты ипр.
необходимо заменить на соответствующиеноминальные либо числовые значенияПлан лекцииЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучение1 Некоторые задачи машинного обученияЗадачаЗадачаЗадачаЗадачаЗадачаЗадачаклассификациивосстановления регрессиикластеризации (обучения без учителя)идентификациипрогнозированияизвлечения знаний2 Основные проблемы машинного обученияМалый объем обучающей выборкиНекорректность входных данныхПереобучениеНапоминание3 НапоминаниеПолезные сведения из линейной алгебры и теории оптимизОсновные понятия мат. статистикиИдея машинного обученияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучениеНапоминание• Задача машинного обучения заключается ввосстановлении зависимостей по конечным выборкамданных (прецедентов)• Пусть (X, t) = (xi , ti )ni=1 – обучающая выборка, гдеxi ∈ Rd – признаковое описание объекта, а t ∈ T –значение скрытой компоненты (классоваяпринадлежность (не по Марксу!), значение прогноза,номер кластера и т.д.)• При статистическом подходе к решению задачи МОпредполагается, что обучающая выборка являетсявыборкой из некоторой генеральной совокупности сплотностью p(x, t)• Требуется восстановить p(t|x), т.е.
знание о скрытойкомпоненте объекта по измеренным признакамПроблема переобученияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровПрямая минимизация невязки на обучающей выборке ведетк получению решающих правил, способных объяснить всечто угодно и найти закономерности даже там, где их нет.43НекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучение210−1−2−3−3−2−101234532Напоминание10−1−2−3123456Способы оценки и увеличения обобщающейспособностиЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучениеНапоминание• На сегодняшний день единственным универсальнымспособом оценивания обобщающей способностиявляется скользящий контроль• Все попытки предложить что-нибудь отличное отметода проб и ошибок пока не привели кобщепризнанному решению.
Наиболее известны из нихследующие:• Структурная минимизация риска (В. Вапник,А. Червоненкис, 1974)• Минимизация длины описания (Дж. Риссанен, 1978)• Информационные критерии Акаике и Байеса-Шварца(Х. Акаике, 1974, Г. Шварц, 1978)• Максимизация обоснованности (Д. МакКай, 1992)• Последний принцип позволяет надеяться наконструктивное решение задачи выбора моделиПримеры задач выбора моделиЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияМалый объемобучающейвыборкиНекорректностьвходных данныхПереобучениеНапоминание• Определение числа кластеров в данных• Выбор коэффициента регуляризации в задачемашинного обучения• Установка степени полинома при интерполяциисплайнами• Выбор наилучшей базисной функции в обощенныхлинейных моделях• Определение количества ветвей в решающем дереве• и многое другое...План лекцииЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики1 Некоторые задачи машинного обученияЗадачаЗадачаЗадачаЗадачаЗадачаЗадачаклассификациивосстановления регрессиикластеризации (обучения без учителя)идентификациипрогнозированияизвлечения знаний2 Основные проблемы машинного обученияМалый объем обучающей выборкиНекорректность входных данныхПереобучение3 НапоминаниеПолезные сведения из линейной алгебры и теории оптимизОсновные понятия мат.
статистикиМатричная нотацияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики• При работе с многомерными величинами очень удобнаматричная нотация, т.е. представление многихопераций над векторами и числами в виде операцийнад матрицами• Скалярное произведение двух векторов x, y ∈ Rdпринимает видhx, yi =dXxi yi = xT y,i=1т.е. вектора трактуются как частные случаи матриц• Квадратичная формаhAx, yi =d XdXxi aij yj = xT Ayi=1 j=1• Матричная нотация облегчает математическиевыкладки и позволяет реализовать вычисления наЭВМ более эффективноПример использованияЛекция 1.РазличныезадачимашинногообученияЖуравлев,Ветров• Предположим нам надо решить несовместную систему линейныхуравнений Ax ≈ b, A ∈ Rm×n• Для этого будем минимизировать квадрат нормы невязки(система-то нерешаемая) kAx − bk2 → minx• Представляя норму в матричной виде, дифференцируя поНекоторыезадачимашинногообученияОсновныепроблемымашинногообучениявектору и приавнивая производную к нулю получаем известнуюформулу для псевдорешения СЛАУkAx − bk2 = hAx − b, Ax − bi = (Ax − b)T (Ax − b) =(Ax)T Ax − bT Ax − (Ax)T b + bT b =НапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики∂∂xxT AT Ax − 2xT AT b + bT bxT AT Ax − 2xT AT b + bT b = 2AT Ax − 2AT b = 0x = AT A−1AT b• Заметим, что если матрица A квадратная (число уравненийравно числу неизвестных) и невырожденная, то последняяформула переходит в формулу обычного решения СЛАУx = A−1 bЗадача условной оптимизацииЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровПусть f (x) : Rd → R — гладкая функция.
Предположим, чтонам необходимо найти ее экстремум:f (x) → extrxНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистикиДля того, чтобы найти экстремум (решить задачубезусловной оптимизации), достаточно проверить условиестационарности:∇f (x) = 0Предположим, что нам необходимо найти экстремумфункции при ограничениях:f (x) → extrxg(x) = 0Поверхность ограниченияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистикиЗаметим, что ∇g(x) ортогонален поверхности ограниченияg(x) = 0.
Пусть x и x + ε — две близкие точки поверхности.Тогдаg(x + ε) ≃ g(x) + εT ∇g(x)Т.к. g(x + ε) = g(x), то εT ∇g(x) ≃ 0. При стремленииkεk → 0 получаем εT ∇g(x) = 0. Т.к. ε параллеленповерхности g(x) = 0, то ∇g(x) является нормалью к этойповерхности.Функция ЛагранжаЛекция 1.РазличныезадачимашинногообученияНеобходимым условием оптимальности являетсяортогональность ∇f (x) поверхности ограничения, т.е.:∇f + λ∇g = 0Журавлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияЗдесь λ 6= 0 — коэффициент Лагранжа. Он может бытьлюбого знака.Функция ЛагранжаНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистикиL(x, λ) , f (x) + λg(x)Тогда∇x L = 0∂L=0∂λ⇒ условие (1)⇒ g(x) = 0(1)Функция Лагранжа.
Пример.x2Лекция 1.Различныезадачимашинногообучения**(x 1,x 2)Журавлев,Ветровx1g(x1,x2)=0Некоторыезадачимашинногообученияf (x1 , x2 ) = 1 − x21 − x22 → maxx1 ,x2ОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистикиg(x1 , x2 ) = x1 + x2 − 1 = 0Функция Лагранжа:L(x, λ) = 1 − x21 − x22 + λ(x1 + x2 − 1)Условия стационарности:− 2x1 + λ = 0− 2x2 + λ = 0x1 + x2 − 1 = 0Решение:(x∗1 , x∗2 )=( 12 , 12 ),λ = 1.План лекцииЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики1 Некоторые задачи машинного обученияЗадачаЗадачаЗадачаЗадачаЗадачаЗадачаклассификациивосстановления регрессиикластеризации (обучения без учителя)идентификациипрогнозированияизвлечения знаний2 Основные проблемы машинного обученияМалый объем обучающей выборкиНекорректность входных данныхПереобучение3 НапоминаниеПолезные сведения из линейной алгебры и теории оптимизОсновные понятия мат.