Category: наука

Category was added automatically. Read all entries about "наука".

medved

StatMod и ML

Рассмотрим, чем полезен StatMod в плане инженерии ML и почему "преподаваемый" ML тут проигрывает. Под "преподаваемым" ML я имею в виду подход, который воспроизводится обычно на курсах, статьях и проч. Ибо, вообще говоря, тут не может быть принципиальной разницы между ML и (Mathematical) Statistics. Т.е. всякий метод из матстатистики можно привнести в ML.

Я вообще не хочу рассматривать различие между статистикой и МЛ, гораздо существеннее разница между probabilistic и nonprobablistic моделированием. Для простоты будем считать, что ML всегда работает с моделями данных (возможно неявно) - как впрочем и статистика. Но эти модели могут быть вероятностные, а могут быть и невероятностные. И вместо StatMod в заголовке точнее будет написать ProbMod.

Collapse )
medved

Инженерность в ML

Последнее время занимаюсь некоторой деятельностью, которую я условно называю "инженерия МЛ". Ибо на практике (при решении "промышленных" задач), инженерности очень не хватает. И вообще, я обнаружил, что эта тема ниочень развита в литературе.
Под инженерностью/инженерией я понимаю некую методику решения практических задач (пусть и ограниченного круга), некий подход к конструированию таких решений. Если рассмотреть с точки зрения науки, то фундаментальные ученые занимаются общими вопросами, которые на первый взгляд вообще не имеют никакого отношения к жизни простых людей. Прикладные ученые берут эти отвлеченные вопросы и конкретизируют до такой степени, что становится понятно, как это можно применить к решению всеразличных проблем, возникающих "на практике". Ну а инженеры уже берут это знание и решают эти самые проблемы, при этом им еще надобно учитывать ограничения по ресурсам.

И вот эта вот инженерия МЛ, на мой взгляд, тема весьма слабо развитая, на данный момент.
Что нисколько ни удивительно, просто еще прикладные исследования токо-токо дозрели (до массового внедрения).

Collapse )
medved

Цикл Бойда и Decision theory: встраиваем ИИ в традиционные ИТ

Как мы видели, ИИ на данном этапе не меняет принципально информационные процессы. Это нервная система человека и животных основана на иных принципах, нежели электронно-вычислительные машины. Искусственную элементную базу, основанную на принципах есестественных вычслителей еще только осваивают, она еще не получила широкого распространения, в то время как видеокарточка может выдавать производительность в десяток триллионов операций в секунду, и стоить в районе тысячи долларов.

Да и гибридный подход, совмещение традиционных электронно-вычислительных компонент с компонентами, основанными на принципах фунеционирования живых "вычислителей", имеет свои преимущества. Иными словами, актуальна и еще значительное время будет актуальна задача совмещения традиционного алгоритмического ИТ с распознаванием образов, машинным обучением.

[Собственно, технически, никакой принципиальной проблемы тут нет.]
Модель, которую выучил компьютер - это просто функция, софтверная компонента. Так что чисто технически она также реализована на той же элементной базе, и реализована в виде алгоритма. Просто немного другая интерпретация результата. Ведь распознавания образов операция нечеткая, а для традиционной алгоритмики ближе строгая формальная логика (но, повторюсь, теор вер и прочая нечеткая логика там вполне себе активно используется).

Рассмотрим пример. Допустим, мы реализуем систему контроля доступа с помощью ИИ и у нас есть распознавалка образов (лиц, отпечатков пальцев, прочей биометрии). И она выдает ответ в виде вероятности, что предъявленный стимул соответствует тому или иному классу или объекту (например, классу тех лиц, кому разрешен доступ, либо конкретному человеку). Если вероятность близка к 1 или 0, то все ясно. А что делать если эта вероятность к примеру 0.5? Понятно, что ответ зависит от конкретного применения системы ИИ, например, в случае контроля доступа лучше подстраховаться, и установить порог срабатывания сильно выше 0.5, ближе к 1.

Систематически эти вопросы изучаются в такой области знания как Теория принятия решений. Многие наверняка сталкивались с ошибками первого и второго рода - это все оттуда (естественно, теория принятия решений используется и в статистике, и в машинном обучении, и в экономике и проч).

Отмечу, что теория принятия решений актуально не только задач классификации, т.е. когда нам нужен выбор из конечного набора альтернатив. Ели ответ непрерывный, то и там есть место теории принятия решений. Например, современная финансовая теория основана (может быть основана) на так называемом стохастических дисконт-факторах, которые по сути и есть применение этой самой теории принятия решений. Если опустить заумные слова, то речь идет о том, что к примеру доход и убыток равной величины, воспринимаются людьми по разному - эффект от убытка 100 у.е. будет зачастую выше, нежели от прибыли в 100 у.е. Как пример крайней степени, можно привести банкротство - если компания в текущий период не может расчитаться по своим обязательствам, то она часто банкротится, несмотря на то, что в следующий период у нее может быть значительная прибыль, которая с лихвой компенсирует убытки. Однако, всегда есть та или иная степень неопределенности относительного будущего.
Таким образом, проблема финансирования "кассового разрыва" - одна из важнейших как в бизнесе, так и в экономике и финансах.
В теории это выражается в том, что в случае прибыли и в случае убытков используют разные ставки дисконтирования. Поскольку, будущее неорпеделено, то и ставка дисконтирования получается стохастической, вероятностной.

Думаю, что из двух рассмотренных примеров, видно, что на концептуальном уровне, встраивание системы распознавания образов (как продукта машинного обучения) в практическую систему, может быть весьма нетривиальной задачей. Хотя технически, это просто функция, которой подают что-то на вход и получают что-то на выходе - т.е. обычная (под)программа, софтверный компонент. Впречем, теория принятия решений - тема хорошо разработанная, так что просто нужно подробно и детально покумекать на тему, как встраивать системы распознавания образов в объемлющую ИТ-систему. Ведь риски от замены естественного интеллекта искусственным могут быть весьма велики.

Отмечу, что есть такая интересная схема как Цикл Бойда. Цикл состоит из четырех элементов: Наблюдение (Observe), Ориентация (Orient), Решение (Decide) и Действие (Act), и этот цикл хорошо ложится на рассмотренные выше концепции.
Т.е. мы сперва собираем данные - Observe. Затем распознаем в них те или иные закономерности (образы) - Orient. Используя теория приянятия решений, вырабатываем решений на основе вероятностей, выдаваемых моделью ИИ - Decide. Ну и, наконец, реализуем решение - Act.
Конечно же, ИИ и МЛ может применяться и в процессе реализации решений - например, для управление роботом может использоваться нейросеть или еще какая-то модель МЛ. Так и в процессе сбора данных может использоваться те или иные алгоритмы МЛ или computer vision. Ну и т.д. Концепция Бойда подразумевает иерархическую декомпозицию, т.е. могут быть и под-циклы и над-циклы Бойда. Поэтому, Циклы Бойда - весьма интересная методология, для целей реализации систем МЛ и ИИ на на практике.
medved

Экзистенциальная философия лёрнинга

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

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

Первый момент - лёринг часто сводят к задаче оптимизации. Свести к оптимизационной задаче - это вообще мега-мощный прием современной науки и инженерии (наверное, для него можно сделать отдельный раздел ТРИЗ). Вопрос - можем ли мы вообще оставаться в фреймворке лёрнинга (экзистенциальный вопрос) или рано или поздно придется выйти из него?

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

Третий момент - какие проблемы в контексте лёрнинга возникают при использовании оптимизации? Вообще, конечно, оптимизация используется разными способами. Например, мы минимизируем эмпирический риск. Но, на самом деле, мы хотим минимизировать ожидаемый риск, просто мы его не можем посчитать (аз исключением каких-нить синтетических случаев).
Т.е. у нас тут тоже есть (не)явная подмена оптимизируемой проблемы. Есессно, оптимизация в прямолинейном виде легко приводит к оверфиттингу.
Вывод - проблемы с оптимизацией еще не отвергают гипотезу, что лёрнинг есть разновидность оптимизации. Просто может нужна более хитрая оптимизация (на уровне выбора модели, к примеру).

Четвертый момент - допустим есть байесовский лёрнинг. Нe и мы хотим использовать posterior mean в качестве прогноза. По идее, тут никакой оптимизации нет - мы и модель даже не выбираем, а интегрируем по всему возможному пространству моделей. Но мы ведь знаем, что mean соответствует квадратичной функции ошибки. Т.е. неявную оптимизационную задачу все равно нетрудно сконструировать (и возможно ее будет проще решать нежели Монте-Карло для решения задачи интеграции).

Пятый момент - допустим, у нас квадратичная функция ошибки. Т.е. мы хотим минимизировать отклонение прогнозов в среднеквадратичном смысле. Ну или не обязательно в среднеквадратичном. Главное, что мы, на самом деле, хотим чтобы наша выученная фунеция проходила как можно ближе к тренировочным примерам. Но, поскольку мы понимаем, что примеры могут быть с шумом, то не хотим чтобы она проходила точно через тренировочные примеры.
На самом деле, может даже более естественно (в случае регрессии), ставить задачу лёрнинга как решение системы стохастических уравнений. Ну т.е. для каждого примера, у нас есть одно уравнение, что прогноз по модели должен быть примерно (с ошибкой) равен учебному результату. Ну а среднеквадратичная (или любая другая) метрика лишь способ измерить насколько ошибка велика.

Итого, у меня прослеживается следующая эволюция представлений о той форме, в которой существует лёрнинг:
1 лёрнинг есть разновидность оптимизации
2 в связи с очевидными проблемами оптимизации, нужно заключить что лёрнинг есть отдельная форма, которая использует оптимизацию как инструмент. Более того, например, экономику можно рассматривать тоже не как оптимизацию (максимальное удовлетворение потребностей при ограниченых ресурсах), а в лёрнинговой парадигме - адаптация к оружающей среде, ну типа учимся удовлетворять потребности с помощью ограниченных ресурсов (используя инструментарий оптимизации там где получится.
3 лёрнинг как решение системы стохастических уравнений - мы знаем что хотим получить, но примерно, с некоторой ошибкой
medved

Зачем нужно вероятностное моделирование (и вероятностное программирование, в частности)?

Одна из проблем в преподавании статистики и теор вера, заключается в том, что нифига не понятно зачем оно все это надо, а точнее, непонятно как это применить.
По крайней мере, я не встречал материалов, раскрывающих эту тему. Хотя отдельные моменты кое-где, бывало, что и раскрываются.
А ведь если понятна идеология, зачем и как это делать, то и изучаемый материал (весьма сложный и запутанный для большинства) становится инструментом, а не просто какими-то абстрактными рассуждениями.
Вобщем, в конечном итоге, приходится придумывать идеологию и методологию самому, хотя опираясь на кучу научных и проч работ и статей, конечно же.

Первый момент, который хотелось бы пояснить - это то, что случайная величина есть абстрактный объект, который в природе не встречается :). Но мы используем его для моделирования реальности и для рассуждения об этих моделях. Ну и этот объект, очевидно, абстрагирует неопределенность. А неопределенность в реальности имеется :).
Рассмотрим пример. Допустим мы измеряем какое-то изделие. Каждый раз, когда мы измеряем изделие, мы получим немного отличающийся результат. Т.е. тут есть ошибки измерений - факторы, которые мы не контролируем, или о которых у нас нет инфы. Вообще, факторов, которые привносят ошибку, ну или неопределенность, может быть несколько: разные измерительные инструменты, разные измеряющие (применяющие процедуры), влияние факторов на размер изделия (температура, к примеру), ошибки связанные с прибором (погрешности измерения).
Тут у нас явно или неявно, присутствует вероятностная/стохастическая модель. Т.е. есть некая величина - размер изделия, которую мы не наблюдаем непосредственно (скрытая, латентная переменная). А наблюдать мы можем результаты измерений. При этом у нас есть модель, что каждый результат измерения равен этой скрытой переменной плюс шум.
Плюс у нас есть еще всякие допущения относительно шума, а также процедуры измерения. Ибо если у нас этих допущений нет, то и решение неопределено - для любого "размера" можно подобрать соответствующие значения шумов, которые "объясняют" результаты измерения.
Collapse )
medved

Вероятности в программерской концепции теор вера

У идеальных генераторов случайных чисел, выдаваемые значения не зависят друг от друга, но у разных генераторов могут варьироваться относительные частоты, с которыми выдается то или иное значение.
Рассмотрим, таким образом, "частотное" понимание вероятности.
Допустим для начала, что генератор выдает конечное кол-во разных значений. Тогда, если мы дернем генератор N раз, мы можем подсчитать, сколько раз было выдано то или иное значение.
Ну и мы можем нормализовать эти значения, поделив на общее кол-во чисел (== N), и получив частоты, с которыми нам встретились те или иные значения.
Ну и если мы устремим N к бесконечности, то эти нормализованные значения устремятся к вероятностям, которые и определяют свойства генератора, как случайной величины.
Понятно, что в любом конечном наборе сгенерированных значений, частоты будут отличаться от специфицированных вероятностей, но будут вертеться вокруг них.
Т.е. генератор случайных чисел, который выдает конечный набор значений, определяется набором вероятностей (эти значения получить). При этом вероятности неотрицательные и в сумме дают единицу.

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

Если же множество значений непрерывно, тогда говорят о функции плотности вероятности. Для простоты, рассмотрим дискретизированную версию. Т.е. разобьем множество значений на интервалы.
Ну и получим производную случайную величину, которая уже будет дискретна. Вероятность случайного числа попасть в тот или иной диапазон, будет определяться площадью графика плотности вероятности, на данном диапазоне. Т.е. интегралу от плотности вероятности на данном диапазоне.
Ну и сие будет верно для всеразличных разбиений на интервалы.
Вобщем, для непрерывной величины, мы не можем говорить о вероятности отдельного значения, но можем говорить о вероятность попасть в тот или иной интервал.
Таким образом, генератор специфицируется функцией плотности вероятности, которая неотрицательна, и интеграл от которой по всему диапазону значений равен 1.

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

Программирование, теор вер и машин лёрнинг

Программерский взгляд на теор вер особенно актуален в контексте машинного обучения. Раньше (очень давно), искусственный интеллект избегал вероятностных трактовок - исследователи вроде как просто боялись сией сложной темы. Однако, сейчас машинное обучение тесно завязано на вероятностную трактовку. Т.е. для полноценного освоения машинного обучения знать основы теор вера и статистики необходимо. Но и программирование в какой-то степени знать тоже надо.
Ну и для программеров, можно снизить порог входа в область, если описать маппинг на привычные программерам концепции.

Я для себя уже примерно сформировал подобный маппинг. Основной концепцией в теорвере является случайная величина. Для программерской трактовки, я сделаю упор на другое понятие - на генераторы (случайных чисел). Генератор - это такая функция, которая выдает значение, если его попросить (т.е. вызвать функцию). При этом каждый раз могут возвращаться разные значения. Ну и если эти значения выдаются каждый раз случайно, независимо от предыдущих действий, то у нас будет генератор случайных чисел.
Такой генератор случайных чисел и есть основа программерской концепции теор вера (моей программерской концепции, если точнее). Т.е. это такой класс функций. При этом у генератора может быть спецификация, которая определяет его свойства. Вот эта спецификация и есть случайная величина - т.е. в обычном теорвере ей способствует понятие случайной величины.
Т.е. у всех генераторов случайных чисел - и у их спецификаций - есть общее свойство: выдаваемые ими значения не зависят от предыдущих действий, т.е. случайны, не подчиняются никакому закону.
Но в рамках этого общего требования, относительные частоты выдаваемых значений, также как и их типы, могут различаться. Ну и случайная величина и уточняет эти аспекты.

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

Ну и эти концепции можно использовать для моделирования реальности. Т.е. мы из строительных блоков - генераторов, строим модели - того как образуются какие-то данные, числа и проч. А на основе спецификаций этих генераторов, мы можем рассуждать о свойствах подобных моделей. Ну и если мы возьмем программную реализацию генератора случайных чисел, то мы можем устроить и числовую симуляцию модели.

Т.е. у нас тут три уровня. Есть генераторы случайных чисел, из которых мы строим модели - уровень моделирования. В данном случае, это абстрактные математические объекты. Есть программные реализации генераторов - их можно использовать для симуляции. И есть еще один уровень спецификации, на котором мы рассуждаем о свойствах полученных конструкций - т.е. как раз уровень теорвера (и статистики), тут нам нужны спецификации генераторов.

Рассмотрим примеры. Допустим мы бросаем игральную кость. Игральная кость у нас выступает как генератор случайных чисел. Ну и допустим мы специфицируем, что это правильная игральная кость, т.е. она выдает числа от 1 до 6 с равной вероятностью (и каждый раз значение независимо от предыдущих действий).
Т.е. мы игральную кость моделируем генератором случайных чисел. Ну и на основании специфицированных свойств, мы можем делать какие-то рассуждения, например, какой значение в среднем мы будем получать, если подбрасывать кость бесконечно много раз. Или какую сумму значений мы будем получать в среднем, если подбросим кость N раз, ну и т.д.
Замечу, что реальная игральная кость может заметно отличаться от идеального генератора, например, последовательные значения могут зависеть друг от друга. В данном случае, мы это явление не сможем смоделировать простым генератором случайных чисел, ибо он подразумевает, что выдаваемые значения никак друг от друга не зависят. Для моделирования этого надо использовать более сложную конструкцию - случайный процесс.

Другой пример. Допустим мы измеряем что-нить, ну и каждый раз получаем немного разные значению - в силу тех или иных ошибок, т.е. факторов, которые мы не контролируем. Мы можем моделировать результаты измерений случайными числами - опять-таки, если считаем, что последовательные измерения друг на друга не влияют.
Ну и у этих измерений будут какие-то закономерности, т.е. небольшие отклонения будут встречаться чаще, а большие - реже. Мы их можем моделировать разными распределениями случайных величин. Например, отклонения в плюс могут иметь такую же вероятность как и отклонения в минус, но может быть и по другому.
Тут мы также можем ставить задачи о рассуждении о свойствах модели - как оценить "истинный размер" по серии измерений, и какова точность этой оценки.
"Истинным размером" тут будет параметр генератора случайных чисел, который порождает результаты измерений. Ну и нам он типа заранее не известен, и мы хотим его оценить по результатам замеров.
medved

Ядреное дерево

Еще одно лирическое отступление, связанное и с IRLS и с Woodbury matrix identity.
Вообще, на мой взгляд, без хорошего знания базовой линейной алгебры в машин лёрнинге делать особо нечего, а вышеупомянутая identity дает возможность потренироваться в операциях с матрицами. Надо сказать, сия identity лежит в основе многих практических методов лёрнинга.
Я ранее писал что с ее помощью можно сократить вычисления в случае метода Ньютона ну или к примеру в случае логистической регрессии, когда кол-во фич сильно больше кол-ва тренировочных примеров.
Вообще, подобные случаи возникают нередко, ну и вобщем-то kernel методы и Gaussian Process Regression есть примеры применения этой самой identity, а точнее обычно это носит название Kernel trick (ailev как-то услышал Kernel 3 вместо Kernel trick, а я почему-то подумал, что он услышал Kernel Tree :), вобщем такой двойная ошибочка, которая и легла в основу названия поста - дерево получается и правда ядреным :)).

Кроме того, отмечу что в предыдущем посте я забил на случай когда у нас есть слагаемое, которое нормализует плотность вероятности (логарифм partition функции). Сейчас можно рассмотреть и этот случай тоже.
Collapse )
medved

Лирическое отступление - линейные модели и IRLS

Немного лирического отступления от туториала по секонд-ордер методам, который несколько неожиданно для меня разветвляется :).
Оказывается такой забавный алгоритм как Iteratively Reweighted Least Squares (IRLS) имеет отношение к методу Ньютона.

Допустим у нас есть линейная модель - под линейной моделью я понимаю ситуацию, когда у нас для предсказания используется линейная функция от входа. Точнее, в виде f(x'*p) - где x - вход, а p - параметры, ну а f(.) - какая-то функция. Вообще говоря, вместо x можно тоже использовать какую-нить функцию - ну т.е. выполнить преобразование или расширение фич. Т.е. линейная модель это достаточно сложная хрень а вовсе не хухры-мухры. Но для простоты будем считать, что мы уже выполнили преобразование/экспансию фич.

Линейные модели - точнее обычно говорят о Generalized linear model - возникают когда у нас вероятностное распределение ошибок модели принадлежит exponential family. Очевидно, в случае экспоненты хорошо работает Maximum Likelyhood - ну т.е. мы логарифмируем произведение вероятностей, и получаем сумму логарифмов, ну а если плотность вероятности описывается через экспоненту от чего-нить, то у нас все несколько упрощается.

Допустим у нас log-likelyhood имеет вид sum f(X*p). Вообще говоря, там еще может прибавляться некий член, который нормализует функцию плотности вероятности, чтобы она давала 1 при интеграции/суммировании, точнее логарифм оного, ежели он зависит от парамеров p. Плюс, если мы делаем регуляризацию/MAP, то соответственно тоже вылезает какой-то член, зависящий от параметров p. Но пока проигнорируем это.

Допустим мы минимизируем эту сумму (варьируя параметр p понятное дело) методом Ньютона. Т.е. у нас есть ключевой Ньютоновский шаг H*d = -g где H - Гессиан, d - дельта изменения параметров, ну и g - градиент. В нашем случае, g = X'*f'(X*p), а H = X'*diag(f''(X*p))*X при этом заметим, что у нас возникает частный случай Weighted Least Squares, где весами являются вектор вторых производных, параметрами - дельта (изначальных) параметров, ну а целевой функцией -f'(X*p)/f''(X*p) - тут происходит поэлементное деление соответствующих векторов.
Т.е. min ||y-X*d||W где W=diag(f''), а y = -f'/f''. Ну и формула для решения будет соответственно inv(X'*W*X)*X'*W*y т.е. как раз и решение для Ньютоновского шага, что неудивительно ибо в методе Ньютона мы и апроксимируем функцию параболой.
Конечно надо чтобы вторые производные не обращались в ноль, но тут поможет регуляризация. Если у нас используется L2 регуляризация то мы без проблем получаем Tikhonov Regularization.
Т.е. в случае GLM метод Ньютона сводится к серии взвешенных линейных регрессий, где веса пересчитываются на каждом шаге.
Хотя по сцыле в википедии используется несколько иная трактовка IRLS, но не суть важно, просто другой вариант IRLS, но идея схожая (наверное, один из другого как-то получается). В данном случае, очевидно, тоже итеративно перевзвешиваются наименьшие квадраты :).
medved

Туториал по секонд-ордер методам - метод Ньютона

Рассмотрим Ньютон метод поподробнее. Хотя он не катит для нейросеток, в силу того, что последние очевидно невыпуклые, да и метод Ньютона будет вычислительно нереальным для типичных размеров нейросеток. Зато эти методы пригодятся при работе с апроксимациями Гессиана.
Итак, в методе Ньютона ключевым является вычисление вектора, вдоль которого мы движемся, вместо оригинального градиента, и который считается решением уравнения Hx = -g.
В некоторых случаях можно сильно ускорить затраты на решение этого уравнения, использую знания о структуре матрицы. Кроме того, уравнение можно решать приближенно.
Решить уравнение проще, если Гессиан моэно как-то декомпозировать. Один из вариантов, если Гессиан можно представить в виде суммы low-rank матрицы и легко инвертируемой матрицы.
Другой вариант - Гессиан можно декомпозировать на произведение легко инвертируемых матриц (sparse, diagonal, block-diagonal, ортогональной etc).
Сумма low-rank и диагональной матрицы возникает не так уж и редко.
Воззьмем к примеру Logistic Regression с L2 регуляризацией, в случае когда у нас не очень много тренировочных примеров, но очень много фич. Регуляризация тут критична.
В этой ситуации можно снизить стоимость инвертирования Гессиана с N^3 до M^3, где N и M - кол-во параметров и тренировочных примеров, соответственно.
Ну и если кол-во параметров сильно больше кол-во примеров, то нам это интересно. Отмечу, что потенциально этот трик можно попробовать применить в случае мини-батчей, ибо кол-во примеров у нас небольшое - конечно, надо будет решить некоторое кол-во проблем :).
Collapse )