2010 Лекции МОТП (Ветров) (1185317), страница 4
Текст из файла (страница 4)
статистикиКраткое напоминание основныхвероятностных понятийЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики• X : Ω → R – случайная величина• Вероятность попадания величины в интервал (a, b)равнаP(a ≤ X ≤ b) =Zbp(x)dx,aгде p(x) – плотность распределения X,Z ∞p(x) ≥ 0,p(x)dx = 1−∞• Если поведение случайной величины определяетсянекоторым параметром, возникают условныеплотности p(x|θ). Если рассматривать уcловнуюплотность как функцию от параметраf (θ) = p(x|θ),то принято говорить о т.н.
функции правдоподобияНормальное распределениеНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистикиматематической статистике1(x − µ)2X ∼ N (x|µ, σ 2 ) = √exp −2σ 22πσµ = EX, σ 2 = DX , E(X − EX)22Журавлев,Ветров• Нормальное распределение играет важнейшую роль вp(x|m,s )Лекция 1.Различныезадачимашинногообученияsm3s• Из центральной предельной теоремы следует, чтосумма независимых случайных величин с ограниченнойдисперсией стремится к нормальному распределению• На практике многие случайные величины можносчитать приближенно нормальнымиМногомерное нормальное распределениеЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообучения• Многомерное нормальное распределение имеет видX ∼ N (x|µ, Σ) = √2π1n√1T −1exp − (x − µ) Σ (x − µ) ,2det Σгде µ = EX, Σ = E(X − µ)(X − µ)T — векторматематических ожиданий каждой из n компонент иматрица ковариаций соответственно• Матрица ковариаций показывает, насколько сильносвязаны (коррелируют) компоненты многомерногонормального распределенияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистикиΣij = E(Xi − µi )(Xj − µj ) = Cov(Xi , Xj )• Если мы поделим ковариацию на корень изпроизведений дисперсий, то получим коэффициенткорреляцииCov(Xi , Xj )ρ(Xi , Xj ) , p∈ [−1, 1]DXi DXjОсобенности нормального распределенияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики• Нормальное распределение полностью задаетсяпервыми двумя моментами (мат.
ожидание и матрицаковариаций/дисперсия)• Матрица ковариаций неотрицательно определена,причем на диагоналях стоят дисперсиисоответствующих компонент• Нормальное распределение имеет очень легкие хвосты:большие отклонения от мат. ожидания практическиневозможны. Это обстоятельство нужно учитыватьпри приближении произвольных случайных величиннормальнымиx2x2x2x1(a)x1(b)x1(c)Основная задача мат. статистикиЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики• Распределение случайной величины X известно сточностью до параметра θ• Имеется выборка значений величины X, x = (x1 , .
. . , xn )• Требуется оценить значение θ• Метод максимального правдоподобияθ̂ML = arg max f (θ) = arg max p(x|θ) = arg maxnYi=1p(xi |θ)• Можно показать, что ММП (не путать с одноименнойкафедрой) является асимптотически оптимальным приn→∞• Обычно максимизируют не само правдоподобие, а егологарифм, т.к.
это вычислительно проще(произведение плотностей по всем объектам переходитв сумму логарифмов плотностей)Пример использованияЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики• Пусть имееется выборка из нормальногораспределения N (x|µ, σ 2 ) с неизвестными мат.ожиданием и дисперсией• Выписываем логарифм функции правдоподобияnX(xi − µ)2nL(X|µ, σ) = −− n log σ − log(2π) → max2µ,σ2σ2i=1nX (xi − µ)∂L=−=0∂µσ2µML =1ni=1nXi=1n∂L X (xi − µ)2n=− =03∂σσσi=1nxi1X(xi − µ)2 =ni=12nnXX1 xi − 1=xj nn2σML=i=1j=1ВыводыЛекция 1.РазличныезадачимашинногообученияЖуравлев,ВетровНекоторыезадачимашинногообученияОсновныепроблемымашинногообученияНапоминаниеПолезныесведения излинейнойалгебры итеорииоптимизацииОсновныепонятия мат.статистики• Не все параметры можно настраивать в ходе обучения• Существуют специальные параметры (будем называтьих структурными), которые должны бытьзафиксированы до начала обучения• В последнем примере величина m (количествокомпонент смеси) является структурным параметром• Основной открытой проблемой машинного обученияявляется проблема выбора структурных параметров,позволяющих избегать переобученияОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииОбобщенные линейные моделиЮ.
И. Журавлев1 , Д. П. Ветров11МГУ, ВМиК, каф. ММПКурс «Математические основы теориипрогнозирования»План лекцииОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации1 НапоминаниеФормула БайесаРешение нерешаемых систем уравнений2 Линейная регрессияКлассическая линейная регрессияМетод наименьших квадратовВероятностная постановка задачи3 Применение регрессионных методов для задачи классификациЛогистическая регрессияМетод IRLSПлан лекцииОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации1 НапоминаниеФормула БайесаРешение нерешаемых систем уравнений2 Линейная регрессияКлассическая линейная регрессияМетод наименьших квадратовВероятностная постановка задачи3 Применение регрессионных методов для задачи классификациЛогистическая регрессияМетод IRLSУсловная вероятностьОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации• Пусть X и Y — случайные величины с плотностями p(x)и p(y) соответственно• В общем случае их совместная плотностьp(x, y) 6= p(x)p(y).
Если это равенство выполняется,величины называют независимыми• Условной плотностью называется величинаp(x, y)p(x|y) =p(y)• Смысл: как факт Y = y влияет на распределение X.RRЗаметим, что p(x|y)dx ≡ 1, но p(x|y)dy не обязан равнятьсяединице, т.к. относительно y это не плотность, а функцияправдоподобия• Очевидная система тождествp(x|y)p(y) = p(x, y) = p(y|x)p(x) позволяет легкопереходить от p(x|y) к p(y|x)p(x|y) =p(y|x)p(x)p(y)Правило суммирования вероятностейОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации• Все операции над вероятностями базируются наприменении всего двух правил• Правило суммирования: Пусть A1 , . .
. , Akвзаимоисключающие события, одно из которых всегдапроисходит. ТогдаkXP(Ai ∪ Aj ) = P(Ai ) + P(Aj )P(Ai ) = 1i=1• Очевидное следствие (формула полной вероятности):∀B верноPki=1P(Ai |B) = 1, откудаkXP(B|Ai )P(Ai )i=1P(B)=1P(B) =P(B|Ai )P(Ai )i=1• В интегральной формеZp(b) =kXp(b, a)da =Zp(b|a)p(a)daПравило произведения вероятностейОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации• Правило произведения гласит, что любую совместнуюплотность всегда можно разбить на множителиp(a, b) = p(a|b)p(b)P(A, B) = P(A|B)P(B)• Аналогично для многомерных совместныхраспределенийp(a1 , . .
. , an ) =p(a1 |a2 , . . . , an )p(a2 |a3 , . . . , an ) . . . p(an−1 |an )p(an )• Можно показать (Jaynes, 1995), что правиласуммирования и произведения вероятностей являютсяединственными возможными операциями,позволяющими рассматривать вероятности какпромежуточную ступень между истиной и ложьюАприорные и апостериорные сужденияОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации• Предположим, мы пытаемся изучить некотороеявление• У нас имеются некоторые знания, полученные до (лат.a priori) наблюдений/эксперимента.
Это может бытьопыт прошлых наблюдений, какие-то модельныегипотезы, ожидания• В процессе наблюдений эти знания подвергаютсяпостепенному уточнению. После (лат. a posteriori)наблюдений/эксперимента у нас формируются новыезнания о явлении• Будем считать, что мы пытаемся оценить неизвестноезначение величины θ посредством наблюденийнекоторых ее косвенных характеристик x|θФормула БайесаОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации• Знаменитая формула Байеса (1763 г.) устанавливаетправила, по которым происходит преобразованиезнаний в процессе наблюдений• Обозначим априорные знания о величине θ за p(θ)• В процессе наблюдений мы получаем серию значенийx = (x1 , .
. . , xn ). При разных θ наблюдение выборки xболее или менее вероятно и определяется значениемправдоподобия p(x|θ)• За счет наблюдений наши представления о значении θменяются согласно формуле Байесаp(θ|x) =p(x|θ)p(θ)p(x|θ)p(θ)=Rp(x)p(x|θ)p(θ)dθ• Заметим, что знаменатель не зависит от θ и нуженисключительно для нормировки апостериорнойплотностиПлан лекцииОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации1 НапоминаниеФормула БайесаРешение нерешаемых систем уравнений2 Линейная регрессияКлассическая линейная регрессияМетод наименьших квадратовВероятностная постановка задачи3 Применение регрессионных методов для задачи классификациЛогистическая регрессияМетод IRLSПсевдообращение матрицОбобщенныелинейные моделиВетров• Предположим, нам необходимо решить СЛАУ видаAx = b• Если бы матрица A была квадратной и невырожденнойНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации(число уравнений равно числу неизвестных и всеуравнения линейно независимы), то решениезадавалось бы формулой x = A−1 b• Предположим, что число уравнений больше числанеизвестных, т.е.
матрица A прямоугольная.Домножим обе части уравнения на AT слеваAT Ax = AT b• В левой части теперь квадратная матрица и ее можноперенести в правую часть¡¢−1 Tx = AT AA b¡ T ¢−1 T• Операция A AA называется псевдообращениемматрицы A, а x – псевдорешениемНормальное псевдорешениеОбобщенныелинейные моделиВетровНапоминаниеФормула БайесаРешениенерешаемыхсистемуравненийЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации• Если матрица AT A вырождена, псевдорешенийбесконечно много, причем найти их на компьютеренетривиально• Для решения этой проблемы используетсяридж-регуляризация матрицы AT AAT A + λI,где I – единичная матрица, а λ – коэффициентрегуляризации. Такая матрица невырождена длялюбых λ > 0• Величина¡¢−1 Tx = AT A + λIA bназывается нормальным псевдорешением.