Лекция 4 (2012 Лекции МОТП (Сенько))
Описание файла
Файл "Лекция 4" внутри архива находится в папке "2012 Лекции МОТП (Сенько)". PDF-файл из архива "2012 Лекции МОТП (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
МАТЕМАТИЧЕСКИЕ ОСНОВЫТЕОРИИ ПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 4Байесовское обучениеРанеебылопоказано,чтомаксимальнуюраспознавания обеспечивает байесовскоеточностьрешающееправило, относящее распознаваемый объект, описываемыйвектором x переменных (признаков) X1,, X n к классу K,*для которого условная вероятность P( K* | x) максимальна.Байесовские методы обучения основаны на аппроксимацииусловных вероятностей классов в точках признаковогопространства с использованием формулы Байеса.Байесовское обучениеРассмотрим задачу распознавания классовK1,, KLФормула Байеса позволяет рассчитать условные вероятности классов вточке признакового пространства:P ( K i | x) f i ( x) P ( K i )L f ( x) P ( K )j 1i, где fi (x) - плотностьiраспределения вероятности для класса K ;iP( Ki ) - вероятность классаK i безотносительно к признаковымописаниям (априорная вероятность).Байесовское обучениеПри этом в качестве оценок априорных вероятностейP( K1 ),, P( K L ) могут быть взяты доли объектов соответствующихклассов в обучающей выборке.Плотности вероятностей f1 (x),, f L (x) восстанавливаются исходяиз предположения об их принадлежности фиксированному типураспределения.Чаще всего используется многомерное нормальное распределения.Байесовское обучениеПлотность данного распределения в общем видепредставляется выражениемf ( x) 1t,1exp[(xμ)(xμ)]2(2 )n / 2 | |1/ 21где μ - математическое ожидание вектора признаков x ;Σ - матрица ковариаций признаков X1,| Σ | - детерминант матрицы Σ ., Xn ;Байесовское обучениеДля построения распознающего алгоритма достаточнооценить вектора математических ожиданий μ1,матрицы ковариаций Σ1,, ΣLдля классов,μL иK1,, KLсоответственно.Оценка μ i вычисляется как среднее значение векторовпризнаков по объектам обучающей выборки из классаμˆ i m1i x j, где mi - число объектов классаs S Kjtiв обучающей выборке.Ki :KiБайесовское обучениеЭлемент матрицы ковариаций для классаK i вычисляется поформуле kki m1is j St Ki( x jk ki )( x jk ki ), k , k {1,, n}, гдеiμk-аякомпонентавектора.
Матрицу ковариации,iсостоящую из элементов kk обозначим ˆikiОчевидно, что согласно формуле Байеса максимум P( Ki | x)достигается для тех же самых классов для которых максимальнопроизведение fi (x)P( Ki ) .Байесовское обучениеОчевидно, что для байесовской классификации можетиспользоваться также натуральный логарифм ln[ fi (x)P( Ki )]который согласно вышеизложенному может быть оценёнˆ xt ) w xt g,0 , гдевыражением gi (x) 12 (xΣiiiˆ 1wi μˆ i Σiˆ 1μˆ t ) 1 ln(| Σˆ |) ln( ) n ln(2 )gi0 12 (μˆ i Σiiii22- независящее от x слагаемое; i - доля объектов класса K i в обучающей выборке.Байесовское обучениеТаким образом объект с признаковым описанием x будетотнесён построенной выше аппроксимациейбайесовского классификатора к классу, для которогооценка gi (x)является максимальной.
Следуетотметить, что построенный классификатор в общемслучае является квадратичным по признакам. Однакоклассификатор превращается в линейный, если оценкиковариационных матриц разных классов оказываютсяравными.Линейный дискриминант ФишераРассмотрим вариант метода Линейный дискриминантФишера (ЛДФ) для распознавания двух классов K1 и K 2 .В основе метода лежит поиск в многомерном признаковомпространстве такого направления w , чтобы средниезначения проекции на него объектов обучающейвыборки из классов K1 и K 2 максимальноразличались.
Проекцией произвольного вектора x на(wxt )направление w является отношение.|w|Линейный дискриминант ФишераВ качестве меры различий проекций классов на wиспользуется функционал•ˆ (w ) Xˆ (w ) |[Xw1w2, где(w ) dˆ1 (w) dˆ2 (w)ˆ (w ) 1Xmi• wis j St Ki(wxtj )| w | - среднее значение проекциивекторов, описывающих объекты из классаKi , i {1,2}Линейный дискриминант Фишера•dˆi (w ) 1mis j St Ki[(wxtj )|w| Xˆ wi ]2- выборочнаядисперсия проекций векторов, описывающих объекты изкласса.Смысл функционала (w) ясен из его структуры.
Он являетсяпо сути квадратом отличия между средними значениямипроекций классов на направление w , нормированным насумму внутриклассовых выборочных дисперсий.Линейный дискриминант ФишераМожно показать, что (w) достигает максимума1wt ˆ 12(μˆ 1t μˆ t2 ) , где ˆ ˆ ˆ . Таким образом оценка1212направления, оптимального для распознавания K1 и1ˆ t ˆ 12(μˆ 1t μˆ t2 ) ( μˆ i m1iможет быть записана в виде wK2s j St Kix j)Распознавание нового объекта s* по признаковому описанию(wx*t )x* производится по величине проекции (x* ) с|w|помощью простого порогового правилаПри (x* ) b объект s* относится к классу K1 и s* относится кклассу K 2 в противном случае.Линейный дискриминант ФишераГраничный параметр b подбирается по обучающейвыборке таким образом, чтобы проекции объектовразных классов на оптимальное направление wоказались бы максимально разделёнными.
Простой, ноэффективной, стратегией является выбор в качествепорогового параметра b средней проекции объектовобучаю щей выборки на w .Линейный дискриминант ФишераМетод ЛДФ легко обобщается на случай с несколькимиклассами.При этом исходная задача распознавания классов K1 ,сводится к последовательности задач с двумя классамии K 2 :K1 K1 , класс K2 \ K1Зад. 1. Класс………………………………………………………………………………K2 \ K LЗад. L. Класс K1 K L, класс, KLK1Для каждой из L задач ищется оптимальное направлениеи пороговое правило.Линейный дискриминант ФишераВ результате получается набор из L направлений,.w Lw1,При распознавании нового объекта s* по признаковомуописанию x* вычисляются проекции на w , , w1L(w1x*t )(w L x*t ) 1 (x* ) , , L (x* ) | w1 || wL |Распознаваемый объект относится к тому классу,соответствующему максимальной величине проекции.Распознавание может производится также по величинам[ 1 (x* ) b1 ],,[ L (x* ) bL ]Логистическая регрессияЦелью логистической регрессии является аппроксимацияплотности условных вероятностей классов в точкахпризнакового пространства.
При этом аппроксимацияпроизводится с использованием логистической функции.ez1g ( z) z ze 1 e 1Рис. 1Логистическая регрессияВ методе логистическая регрессия связь условной вероятностикласса K с прогностическими признаками осуществляютсячерез переменную z , которая задаётсяzкак линейнаякомбинация признаков:z 0 1 X1 n X nТаким образом условная вероятность K в точке векторногопространства x* ( x*1,P( K | x) , x*n ) задаётся в виде1e 0 1x*1 1x* n1e0 1x*1 e 1x* n0 1 x*1 1 x* n1(1)Логистическая регрессияОценки регрессионных параметров0 , 1, , n могутбыть вычислены по обучающей выборке с помощьюразличных вариантов метода максимальногоправдоподобия.
Предположим, что объекты обучающейвыборки сосредоточены в точках признаковогопространства {x1,, xr } . При этом распределениеобъектов обучающей выборка по точкам задаётся спомощью набора пар {(m1, k1 ), ,(mr , kr )} , где mi -общее число объектов в точке xi , ki - число объектовкласса K в точке xiЛогистическая регрессияВероятность данной конфигурации подчиняется распределениюБернулли.
Введём обозначение p(x) P( K | x) . Функцияправдоподобия может быть записана в видеrkikimi kiC[p(x)][1p(x)]L(β, x) mii 1p ( x) e 0 1x*1 Принимая во внимание что 1 p(x)1 p ( x) 11 e 0 1x*1 1x* n 1x* nЛогистическая регрессия• ПолучаемrL(β, x) C ei 1kiniki ( 0 1x*1 1x* n )r1(1 e0 1x*1 rln L(β, x) ln(C ) ki ( 0 1 x*1 kinii 1ri 1 mi ln{1/[1 e( 0 1x*1 i 1 1x* n )mi) 1x* n 1 x*n ) ]}Метод k-ближайших соседей• Простым, но достаточно эффективным подходом к решениюзадач распознавания является метод k-ближайших соседей.Оценка условных вероятностей P( Ki | x)ведётся поближайшей окрестности Vk точки x , содержащей kпризнаковых описаний объектов обучающей выборки. Вkiкачестве оценки P( Ki | x) выступает отношение, где ki kчисло признаковых описаний объектов обучающей выборкииз K i внутри Vk .Метод k-ближайших соседейОкрестность Vk задаётся с помощью функции расстояния (x, x) заданной на декартовом произведении X X ,где X - область допустимых значений признаковыхописаний.
В качестве функции расстояния может бытьиспользована стандартная эвклидова метрикаe (x, x) ni 11n( xi xi) 2Метод k-ближайших соседейДля задач с бинарными признаками в качестве функциирасстояния может быть использована метрика Хэмминга,равная числу совпадающих позиций в двух сравниваемыхпризнаковых описаниях.Окрестность Vk ищется путём поиска в обучающей выборкеk векторных описаний, ближайших в смысле выбраннойфункции расстояний, к описанию x* распознаваемогообъекта s* .Метод k-ближайших соседейЕдинственным параметром, который может быть использовандля настройки (обучения) алгоритмов в методеk–ближайших соседей является собственно само числоближайших соседей.Для оптимизации параметра k обычно используется метод,основанный на скользящем контроле.
Оценка точностираспознавания производится по обучающей выборке приразличных k и выбирается значение данного параметра, прикотором полученная точность максимальна.Распознавание при заданной точностираспознавания некоторых классов• Байесовский классификатор обеспечивает максимальнуюобщуюточностьконкретныхраспознавания.практическихОднакоприпотери,связанныезадачрешенииснеправильной классификацией объектов, принадлежащих кодномуизклассов,значительнопревышаютпотери,связанные с неправильной классификацией объектов другихклассов.