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

И сегодня мы поговорим о фильтре Калмана , разберемся, что это такое, для чего и как он применяется.

Начнем с небольшого примера. Пусть перед нами стоит задача определять координату летящего самолета. Причем, естественно, координата (обозначим ее ) должна определяться максимально точно.

На самолете мы заранее установили датчик, который и дает нам искомые данные о местоположении, но, как и все в этом мире, наш датчик неидеален. Поэтому вместо значения мы получаем:

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

Задача поставлена, перейдем к ее решению.

Пусть мы знаем управляющее воздействие (), благодаря которому летит самолет (пилот сообщил нам, какие рычаги он дергает 😉). Тогда, зная координату на k-ом шаге, мы можем получить значение на (k+1) шаге:

Казалось бы, вот оно, то что надо! И никакой фильтр Калмана тут не нужен. Но не все так просто.. В реальности мы не можем учесть все внешние факторы, влияющие на полет, поэтому формула принимает следующий вид:

где – ошибка, вызванная внешним воздействием, неидеальностью двигателя итп.

Итак, что же получается? На шаге (k+1) мы имеем, во-первых, неточное показание датчика , а во-вторых, неточно рассчитанное значение , полученное из значения на предыдущем шаге.

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

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

А теперь предположим, что связи с пилотом нет, и мы не знаем управляющее воздействие . Казалось бы, в этом случае фильтр Калмана мы использовать не можем, но это не так 😉 Просто “выкидываем” из формулы то, что мы не знаем, тогда

Получаем максимально упрощенную формулу Калмана, которая тем не менее, несмотря на такие “жесткие” упрощения, прекрасно справляется со своей задачей. Если представить результаты графически, то получится примерно следующее:

Если наш датчик очень точный, то естественно весовой коэффициент K должен быть близок к единице. Если же ситуация обратная, то есть датчик у нас не очень хороший, то K должен быть ближе к нулю.

На этом, пожалуй, все, вот так вот просто мы разобрались с алгоритмом фильтрации Калмана! Надеюсь, что статья оказалась полезной и понятной =)

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

В чем же идея такого замечательного алгоритма? Идея проста: допустим у нас есть какой-то очень слабый алгоритм, скажем, . Если мы сделаем очень много разных моделей с использованием этого слабого алгоритма и усредним результат их предсказаний, то итоговый результат будет существенно лучше. Это, так называемое, обучение ансамбля в действии. Алгоритм Random Forest потому и называется "Случайный Лес", для полученных данных он создает множество деревьев приятия решений и потом усредняет результат их предсказаний. Важным моментом тут является элемент случайности в создании каждого дерева. Ведь понятно, что если мы создадим много одинаковых деревьев, то результат их усреднения будет обладать точностью одного дерева.

Как он работает? Предположим, у нас есть некие данные на входе. Каждая колонка соответствует некоторому параметру, каждая строка соответствует некоторому элементу данных.

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

Thursday, May 10, 2012

Thursday, January 12, 2012

Вот собственно и всё. 17-ти часовой перелет позади, Россия осталась за океаном. А в окно уютной 2-ух спальной квартиры на нас смотрит Сан-Франциско, знаменитая Кремниевая долина, Калифорния, США. Да, это и есть та самая причина, по которой я практически не писал последнее время. Мы переехали.

Всё это началось еще в апреле 2011 года, когда я проходил телефонное интервью в компании Zynga. Тогда это все казалось какой-то игрой не имеющей отношения к реальности и я и представить себе не мог, во что это выльется. В июне 2011 года Zynga приехали в Москву и провели серию собеседований, рассматривалось около 60 кандидатов прошедших телефонное интервью и из них было отобрано около 15 человек (точное число не знаю, кто-то потом передумал, кто-то сразу отказался). Интервью оказалось неожиданно простым. Ни тебе задачек на программирование, ни заковыристых вопросов про форму люков, в основном проверялись способности болтать. А знания, на мой взгляд, оценивались лишь поверхностно.

А дальше началась канитель. Сначала мы ждали результатов, потом офера, потом одобрение LCA, потом одобрения петиции на визу, потом документы из США, потом очередь в посольстве, потом дополнительную проверку, потом визу. Временами мне казалось, что я готов все бросить и забить. Временами я сомневался, а нужна ли нам эта Америка ведь и в России не плохо. Весь процесс занял где-то около полугода, в итоге, в середине декабря мы получили визы и начали готовиться к отъезду.

В понедельник был мой первый рабочий день на новом месте. В офисе созданы все условия для того чтобы не только работать, но и жить. Завтраки, обеды и ужины от собственных поваров, куча разнообразнейшей еды распиханной по всем уголкам, спортзал, массаж и даже парикмахер. Все это совершенно бесплатно для сотрудников. Многие добираются на работу на велосипеде и для хранения транспорта оборудовано несколько комнат. В общем, ничего подобного в России мне встречать не доводилось. Всему, однако, есть своя цена, нас сразу предупредили, что работать придется много. Что такое "много", по их меркам, мне не очень понятно.

Надеюсь, однако, что несмотря на количество работы, в обозримом будущем смогу возобновить ведение блога и, может быть, расскажу что-нибудь о американской жизни и работе программистом в Америке. Поживем - увидим. А пока, поздравляю всех с наступившим новым годом и рождеством и до новых встреч!

Для примера использования, распечатаем дивидендную доходность российских компаний. В качестве базовой цены, берем цену закрытия акции в день закрытия реестра. Почему-то на сайте тройки этой информации нет, а она ведь гораздо интересней чем абсолютные величины дивидендов.
Внимание! Код выполняется довольно долго, т.к. для каждой акции требуется сделать запрос на сервера finam и получить её стоимость.

Result <- NULL for(i in (1:length(divs[,1]))){ d <- divs if (d$Divs>0){ try({ quotes <- getSymbols(d$Symbol, src="Finam", from="2010-01-01", auto.assign=FALSE) if (!is.nan(quotes)){ price <- Cl(quotes) if (length(price)>0){ dd <- d$Divs result <- rbind(result, data.frame(d$Symbol, d$Name, d$RegistryDate, as.numeric(dd)/as.numeric(price), stringsAsFactors=FALSE)) } } }, silent=TRUE) } } colnames(result) <- c("Symbol", "Name", "RegistryDate", "Divs") result

Аналогично можно построить статистику для прошлых лет.

Этот фильтр применяют в разных областях – от радиотехники до экономики. Здесь мы обсудим основную идею, смысл, суть данного фильтра. Излагаться она будет максимально простым языком.
Предположим, что у нас есть необходимость в измерениях некоторых величин некоего объекта. В радиотехнике чаще всего имеют дело с измерениями напряжений на выходе некоего устройства (датчика, антенны и т.д.). В примере с электрокардиографом (см. ) мы имеем дело с измерениями биопотенциалов на теле человека. В экономике, например, измеряемой величиной могут быть курсы валют. Каждыё день курс валют разный, т.е. каждый день “его измерения” дают нам разную величину. А если обобщать, то можно сказать, что большая часть деятельности человека (если не вся) сводится именно к постоянным измерениям-сравнениям тех или иных величин (см. книгу).
Итак, предположим, что мы что-то постоянно измеряем. Так же предположим, что наши измерения всегда идут с некоторой ошибкой – оно и понятно, ведь нет идеальных измерительных приборов, и каждый выдаёт результат с ошибкой. В простейшем случае описанное можно свести к следующему выражению: z=x+y, где x – истинное значение, которое мы хотим измерить и которое измерили бы если бы у нас был идеальный измерительный прибор, y – ошибка измерения, вносимая измерительным прибором, а z – измеренная нами величина. Так вот задача фильтра Калмана состоит в том, чтобы по измеренной нами z всё-таки догадаться (определить), а какое же истинное значение x было, когда мы получали нашу z (в которой "сидит" истинное значение и ошибка измерения). Необходимо отфильтровать (отсеять) из z истинное значение x – убрать из z искажающий шум y. То есть, имея на руках только лишь сумму нам необходимо догадаться о том, какие слагаемые дали эту сумму.
В свете вышеописанного сформулируем теперь всё следующим образом. Пусть есть всего лишь два случайных числа. Нам даётся только их сумма и от нас требуется по этой сумме определить, какими являются слагаемые. Например, нам дали число 12 и говорят: 12 – это сумма чисел x и y, вопрос – чему равны x и y. Чтобы ответить на этот вопрос, составляем уравнение: x+y=12. Мы получили одно уравнение с двумя неизвестными, поэтому, строго говоря, найти два числа которые и дали эту сумму не возможно. Но кое-что об этих числах мы всё-таки можем сказать. Мы можем сказать, что это были либо числа 1 и 11, либо 2 и 10, либо 3 и 9, либо 4 и 8 и т.д., также это либо 13 и -1, либо 14 и -2, либо 15 и -3 и т.д. То есть мы можем по сумме (в нашем примере 12) определить множество возможных вариантов, которые дают в сумме именно 12. Один из этих вариантов – это искомая нами пара, которая на самом деле прямо сейчас и дала 12. Нелишне так же отметить, что все варианты пар чисел дающих в сумме 12 образуют прямую, изображённую на рис.1, которая и задаётся уравнением x+y=12 (y=-x+12).

Рис.1

Таким образом, искомая нами пара лежит где-то на этой прямой. Повторюсь, выбрать из всех этих вариантов ту пару, которая была на самом деле – которая дала число 12, не владея какими-либо дополнительными подсказками, невозможно. Однако, в ситуации, для которой изобретён фильтр Калмана, такие подсказки есть . Там заранее о случайных числах кое-что известно. В частности там известна так называемая гистограмма распределения для каждой пары чисел. Она обычно бывает получена после достаточно длительных наблюдений за выпадениями этих самых случайных чисел. То есть, например, из опыта известно, что в 5% случаев обычно выпадает пара x=1, y=8 (обозначим эту пару так: (1,8)), в 2% случаев пара x=2, y=3 (2,3), в 1% случаев пара (3,1), в 0.024% случаев пара (11,1) и т.д. Повторюсь, эта гистограмма задана для всех пар чисел, в том числе и для тех, что образуют в сумме 12. Таким образом, для каждой пары, что даёт в сумме 12, мы можем сказать, что, например, пара (1, 11) выпадает в 0.8% случаев, пара (2, 10) – в 1% случаев, пара (3, 9) – в 1.5% случаев и т.д. Таким образом, мы можем по гистограмме определить, в скольких процентах случаев сумма слагаемых пары равна 12. Пусть, например, в 30% случаев сумма даёт 12. А в остальных 70% выпадают остальные пары – это (1,8), (2,3), (3,1) и т.д. – те, что в сумме дают числа отличные от 12. Причём пусть, например, пара (7,5) выпадает в 27% случаев в то время, как все остальные пары, что дают в сумме 12, выпадают в 0.024%+0.8%+1%+1.5%+…=3% случаев. Итак, по гистограмме мы выяснили, что числа дающие в сумме 12 выпадают в 30% случаев. При этом мы знаем, что если выпало 12, то чаще всего (в 27% из 30%) причиной этого является пара (7,5). То есть если уже выпало 12, то мы можем сказать, что в 90% (27% из 30% – или, что то же самое 27 раз из каждых 30-ти) причиной выпадения 12 является пара (7,5). Зная, что чаще всего причиной получения суммы равной 12 является пара (7,5) логично предположить, что, скорее всего, она выпала и сейчас. Конечно, всё-таки не факт, что на самом деле сейчас число 12 образовано именно этой парой, однако, в следующие разы, если нам попадётся 12, и мы опять предположим пару (7,5), то где-то в 90% случаев из 100% окажемся правы. А вот если мы будем предполагать пару (2, 10), то окажемся правы лишь в 1% из 30% случаев, что равно 3.33% правильных догадок по сравнению с 90% при предположении пары (7,5). Вот и всё – в этом и состоит смысл алгоритма фильтра Калмана. То есть фильтр Калмана не гарантирует, что не ошибётся в определении слагаемого по сумме, однако он гарантирует, что ошибётся минимальное количество раз (вероятность ошибки будет минимальна), так как использует статистику – гистограмму выпадения пар чисел. Так же необходимо подчеркнуть, что часто в алгоритме фильтрации Калмана используется так называемая плотность распределения вероятности (ПРВ). Однако необходимо понимать, что смысл там тот же, что и у гистограммы. Более того, гистограмма – это функция, построенная на основе ПРВ и являющаяся её приближением (см., например, ).
В принципе мы эту гистограмму можем изобразить в виде функции двух переменных – то есть в виде некоей поверхности над плоскостью xy. Там, где поверхность выше, там выше и вероятность выпадения соответствующей пары. На рис.2 изображена такая поверхность.

рис.2

Как видно над прямой x+y=12 (которая есть варианты пар дающих в сумме 12) расположены точки поверхности на разной высоте и наибольшая высота у варианта с координатами (7,5). И когда нам встречается сумма равная 12, в 90% случаев причиной появления этой суммы является именно пара (7,5). Т.е. именно эта пара, дающая в сумме 12, имеет наибольшую вероятность появления при условии, что сумма равна 12.
Таким образом, здесь описана идея лежащая в основе фильтра Калмана. Именно на ней и построены всевозможные его модификации – одношаговые, многошаговые рекуррентные и т.д. Для более глубокого изучения фильтра Калмана рекомендую книгу: Ван Трис Г. Теория обнаружения, оценок и модуляции.

p.s. Для того, кто интересуется объяснениями понятий математики что называется "на пальцах" можно посоветовать вот эту книгу и в частности главы из её раздела "Математика" (саму книгу или отдельные главы из неё вы можете приобрести ).

В интернете, в том числе и на хабре, можно найти много информации про фильтр Калмана. Но тяжело найти легкоперевариваемый вывод самих формул. Без вывода вся эта наука воспринимается как некое шаманство, формулы выглядят как безликий набор символов, а главное, многие простые утверждения, лежащие на поверхности теории, оказываются за пределами понимания. Целью этой статьи будет рассказать об этом фильтре на как можно более доступном языке.
Фильтр Калмана - это мощнейший инструмент фильтрации данных. Основной его принцип состоит в том, что при фильтрации используется информация о физике самого явления. Скажем, если вы фильтруете данные со спидометра машины, то инерционность машины дает вам право воспринимать слишком быстрые скачки скорости как ошибку измерения. Фильтр Калмана интересен тем, что в каком-то смысле, это самый лучший фильтр. Подробнее обсудим ниже, что конкретно означают слова «самый лучший». В конце статьи я покажу, что во многих случаях формулы можно до такой степени упростить, что от них почти ничего и не останется.

Ликбез

Перед знакомством с фильтром Калмана я предлагаю вспомнить некоторые простые определения и факты из теории вероятности.

Случайная величина

Когда говорят, что дана случайная величина , то имеют ввиду, что эта величина, может принимать случайные значения. Разные значения она принимает с разной вероятностью. Когда вы кидаете, скажем, кость, то выпадет дискретное множество значений: . Когда речь идет, например, о скорости блуждающей частички, то, очевидно, приходится иметь дело с непрерывным множеством значений. «Выпавшие» значения случайной величины мы будем обозначать через , но иногда, будем использовать ту же букву, которой обозначаем случайную величину: .
В случае с непрерывным множеством значений случайную величину характеризует плотность вероятности , которая нам диктует, что вероятность того, что случайная величина «выпадет» в маленькой окрестности точки длиной равна . Как мы видим из картинки, эта вероятность равна площади заштрихованного прямоугольника под графиком:

Довольно часто в жизни случайные величины распределены по Гауссу, когда плотность вероятности равна .

Мы видим, что функция имеет форму колокола с центром в точке и с характерной шириной порядка .
Раз мы заговорили о Гауссовом распределении, то грешно будет не упомянуть, откуда оно возникло. Также как и числа и прочно обосновались в математике и встречаются в самых неожиданных местах, так и распределение Гаусса пустило глубокие корни в теорию вероятности. Одно замечательное утверждение, частично объясняющее Гауссово всеприсутствие, состоит в следующем:
Пусть есть случайная величина имеющая произвольное распределение (на самом деле существуют некие ограничения на эту произвольность, но они совершенно не жесткие). Проведем экспериментов и посчитаем сумму «выпавших» значений случайной величины. Сделаем много таких экспериментов. Понятно, что каждый раз мы будем получать разное значение суммы. Иными словами, эта сумма является сама по себе случайной величиной со своим каким-то определенным законом распределения. Оказывается, что при достаточно больших закон распределения этой суммы стремится к распределению Гаусса (к слову, характерная ширина «колокола» растет как ). Более подробно читаем в википедии: центральная предельная теорема . В жизни очень часто встречаются величины, которые складываются из большого количества одинаково распределенных независимых случайных величин, поэтому и распределены по Гауссу.

Среднее значение

Среднее значение случайной величины - это то, что мы получим в пределе, если проведем очень много экспериментов, и посчитаем среднее арифметическое выпавших значений. Среднее значение обозначают по-разному: математики любят обозначать через (математическое ожидание), а заграничные математики через (expectation). Физики же через или . Мы будем обозначать на заграничный лад: .
Например, для Гауссова распределения , среднее значение равно .

Дисперсия

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

Независимые случайные величины

Случайные величины бывают зависимыми и нет. Представьте, что вы бросаете иголку на плоскость и записываете координаты ее обоих концов. Эти две координаты зависимы, они связаны условием, что расстояние между ними всегда равно длине иголки, хотя и являются случайными величинами.
Случайные величины независимы, если результат выпадения первой из них совершенно не зависит от результата выпадения второй из них. Если случайные величины и независимы, то среднее значение их произведения равно произведению их средних значений:

Доказательство

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

Из этого сразу же следует, что:

Как вы видите, доказательство проведено для случайных величин, которые имеют непрерывный спектр значений и заданы своей плотностью вероятности. В других случаях идея доказательтсва аналогичная.

Фильтр Калмана

Постановка задачи

Обозначим за величину, которую мы будем измерять, а потом фильтровать. Это может быть координата, скорость, ускорение, влажность, степень вони, температура, давление, и т.д.
Начнем с простого примера, который и приведет нас к формулировке общей задачи. Представьте себе, что у нас есть радиоуправляемая машинка, которая может ехать только вперед и назад. Мы, зная вес машины, форму, покрытие дороги и т.д., расcчитали как контролирующий джойстик влияет на скорость движения .

Тогда координата машины будет изменяться по закону:

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

У нас есть установленный на машинке GPS сенсор, который пытается мерить истинную координату машинки, и, конечно же, не может ее померить точно, а мерит с ошибкой , которая является тоже случайной величиной. В итоге с сенсора мы получаем ошибочные данные:

Задача состоит в том, что, зная неверные показания сенсора, найти хорошее приближение для истинной координаты машины .
В формулировке же общей задачи, за координату может отвечать все что угодно (температура, влажность…), а член, отвечающий за контроль системы извне мы обозначим за (в примере c машиной ). Уравнения для координаты и показания сенсора будут выглядеть так:

Давайте подробно обсудим, что нам известно:

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

Алгоритм Калмана

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

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

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

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

Доказательство

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

Распишем последнее выражение:

Доказательство

Из того что все случайные величины, входящие в выражение для , независимы, следует, что все «перекрестные» члены равны нулю:

Мы использовали тот факт, что , тогда формула для дисперсии выглядит намного проще: .

Это выражение принимает минимальное значение, когда(приравниваем производную к нулю):

Здесь мы уже пишем выражение для коэффициента Калмана с индексом шага , тем самым мы подчеркиваем, что он зависит от шага итерации.
Подставляем полученное оптимальное значение в выражение для , которую мы минимизировали. Получаем;

Наша задача решена. Мы получили итерационную формулу, для вычисления коэффициента Калмана.
Давайте сведем, наши полученные знания в одну рамочку:

Пример

Код на матлабе

Clear all; N=100 % number of samples a=0.1 % acceleration sigmaPsi=1 sigmaEta=50; k=1:N x=k x(1)=0 z(1)=x(1)+normrnd(0,sigmaEta); for t=1:(N-1) x(t+1)=x(t)+a*t+normrnd(0,sigmaPsi); z(t+1)=x(t+1)+normrnd(0,sigmaEta); end; %kalman filter xOpt(1)=z(1); eOpt(1)=sigmaEta; for t=1:(N-1) eOpt(t+1)=sqrt((sigmaEta^2)*(eOpt(t)^2+sigmaPsi^2)/(sigmaEta^2+eOpt(t)^2+sigmaPsi^2)) K(t+1)=(eOpt(t+1))^2/sigmaEta^2 xOpt(t+1)=(xOpt(t)+a*t)*(1-K(t+1))+K(t+1)*z(t+1) end; plot(k,xOpt,k,z,k,x)

Анализ

Если проследить, как с шагом итерации изменяется коэффициент Калмана , то можно показать, что он всегда стабилизируется к определенному значению . К примеру, когда среднеквадратичные ошибки сенсора и модели относятся друг к другу как десять к одному, то график коэффициента Калмана в зависимости от шага итерации выглядит так:

В следующем примере мы обсудим как это поможет существенно облегчить нашу жизнь.

Второй пример

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

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

На следующем графике показаны отфильтрованные двумя разными способами данные с вымышленного сенсора. При условии того, что мы ничего не знаем о физике явления. Первый способ - честный, со всеми формулами из теории Калмана. А второй - упрощенный, без формул.

Как мы видим, методы почти ничем не отличаются. Маленькое отличие наблюдается, только вначале, когда коэффициент Калмана еще не стабилизировался.

Обсуждение

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

в среднем меньше всего отличалось бы от реального значения координаты . Мы видим, что отфильтрованное значение есть линейная функция от показания сенсора и предыдущего отфильтрованного значения . А предыдущее отфильтрованное значение является, в свою очередь, линейной функцией от показания сенсора и предпредыдущего отфильтрованного значения . И так далее, пока цепь полностью не развернется. То есть отфильтрованное значение зависит от всех предыдущих показаний сенсора линейно:

Поэтому фильтр Калмана называют линейным фильтром.
Можно доказать, что из всех линейных фильтров Калмановский фильтр самый лучший. Самый лучший в том смысле, что средний квадрат ошибки фильтра минимален.

Многомерный случай

Всю теорию фильтра Калмана можно обобщить на многомерный случай. Формулы там выглядят чуть страшнее, но сама идея их вывода такая же, как и в одномерном случае. В этой прекрасной статье вы можете увидеть их: http://habrahabr.ru/post/140274/ .
А в этом замечательном видео разобран пример, как их использовать.

Фильтр Калмана

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

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

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

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

Введение

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

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

Классический фильтр Калмана является уравнениями для расчета первого и второго момента апостериорной плотности вероятности (в смысле вектора математических ожиданий и матрицы дисперсий, в том числе взаимных) при данных ограничениях. Ввиду того, что для нормальной плотности вероятности математическое ожидание и дисперсионная матрица полностью задают плотность вероятности, можно сказать, что фильтр Калмана рассчитывает апостериорную плотность вероятности вектора состояния на каждый момент времени. А значит полностью описывает вектор состояния как случайную векторную величину.

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

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

• Расширенный фильтр Калмана (EKF, Extended Kalman filter). Сведение нелинейных моделей наблюдений и формирующего процесса с помощью линеаризации посредством разложения в ряд Тейлора .
• Unscented Kalman filter (UKF). Используется в задачах, в которых простая линеаризация приводит к уничтожению полезных связей между компонентами вектора состояния. В этом случае «линеаризация» основана на unscented -преобразовании.
• Ensemble Kalman filter (EnKF). Используется для уменьшения размерности задачи.
• Возможны варианты с нелинейным дополнительным фильтром, позволяющим привести негауссовские наблюдения к нормальным.
• Возможны варианты с «обеляющим» фильтром, позволяющим работать с «цветными» шумами
• и т. д.

Используемая модель динамической системы

Фильтры Калмана базируются на дискретизированных по времени линейных динамических системах . Такие системы моделируются цепями Маркова при помощи линейных операторов и слагаемых с нормальным распределением . Состояние системы описывается вектором конечной размерности - вектором состояния . В каждый такт времени линейный оператор действует на вектор состояния и переводит его в другой вектор состояния (детерминированное изменение состояния), добавляется некоторый вектор нормального шума (случайные факторы) и в общем случае вектор управления, моделирующий воздействие системы управления. Фильтр Калмана можно рассматривать как аналог скрытым моделям Маркова , с тем отличием, что переменные, описывающие состояние системы, являются элементами бесконечного множества действительных чисел (в отличие от конечного множества пространства состояний в скрытых моделях Маркова). Кроме того, скрытые модели Маркова могут использовать произвольные распределения для последующих значений вектора состояния, в отличие от фильтра Калмана, использующего модель нормально распределенного шума. Существует строгая взаимосвязь между уравнениями фильтра Калмана и скрытой модели Маркова. Обзор этих и других моделей дан Roweis и Chahramani (1999) .

При использовании фильтра Калмана для получения оценок вектора состояния процесса по серии зашумленных измерений необходимо представить модель данного процесса в соответствии со структурой фильтра - в виде матричного уравнения определенного типа. Для каждого такта k работы фильтра необходимо в соответствии с приведенным ниже описанием определить матрицы: эволюции процесса F k ; матрицу наблюдений H k ; ковариационную матрицу процесса Q k ; ковариационную матрицу шума измерений R k ; при наличии управляющих воздействий - матрицу их коэффициентов B k .

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

Модель системы/процесса подразумевает, что истинное состояние в момент k получается из истинного состояния в момент k −1 в соответствии с уравнением:

,

• F k - матрица эволюции процесса/системы, которая воздействует на вектор x k −1 (вектор состояния в момент k −1 );
• B k - матрица управления, которая прикладывается к вектору управляющих воздействий u k ;
• w k - нормальный случайный процесс с нулевым математическим ожиданием и ковариационной матрицей Q k , который описывает случайный характер эволюции системы/процесса:

В момент k производится наблюдение (измерение) z k истинного вектора состояния x k , которые связаны между собой уравнением:

где H k - матрица измерений, связывающая истинный вектор состояния и вектор произведенных измерений, v k - белый гауссовский шум измерений с нулевым математическим ожиданием и ковариационной матрицей R k :

Начальное состояние и векторы случайных процессов на каждом такте {x 0 , w 1 , …, w k , v 1 , …, v k } считаются независимыми .

Многие реальные динамические системы нельзя точно описать данной моделью. На практике неучтённая в модели динамика может серьёзно испортить рабочие характеристики фильтра, особенно при работе с неизвестным стохастическим сигналом на входе. Более того, неучтённая в модели динамика может сделать фильтр неустойчивым . С другой стороны, независимый белый шум в качестве сигнала не будет приводить к расхождению алгоритма. Задача отделения шумов измерений от неучтенной в модели динамики сложна, решается она с помощью теории робастных систем управления .

Фильтр Калмана

Фильтр Калмана является разновидностью рекурсивных фильтров . Для вычисления оценки состояния системы на текущий такт работы ему необходима оценка состояния (в виде оценки состояния системы и оценки погрешности определения этого состояния) на предыдущем такте работы и измерения на текущем такте. Данное свойство отличает его от пакетных фильтров, требующих в текущий такт работы знание истории измерений и/или оценок. Далее под записью будем понимать оценку истинного вектора в момент n с учетом измерений с момента начала работы и по момент m включительно.

Состояние фильтра задается двумя переменными:

Итерации фильтра Калмана делятся на две фазы: экстраполяция и коррекция. Во время экстраполяции фильтр получает предварительную оценку состояния системы (в русскоязычной литературе часто обозначается , где означает «экстраполяция», а k - номер такта, на котором она получена) на текущий шаг по итоговой оценке состояния с предыдущего шага (либо предварительную оценку на следующий такт по итоговой оценке текущего шага, в зависимости от интерпретации). Эту предварительную оценку также называют априорной оценкой состояния, так как для её получения не используются наблюдения соответствующего шага. В фазе коррекции априорная экстраполяция дополняется соответствующими текущими измерениями для коррекции оценки. Скорректированная оценка также называется апостериорной оценкой состояния, либо просто оценкой вектора состояния . Обычно эти две фазы чередуются: экстраполяция производится по результатам коррекции до следующего наблюдения, а коррекция производится совместно с доступными на следующем шаге наблюдениями, и т. д. Однако возможно и другое развитие событий, если по некоторой причине наблюдение оказалось недоступным, то этап коррекции может быть пропущен и выполнена экстраполяция по нескорректированной оценке (априорной экстраполяции). Аналогично, если независимые измерения доступны только в отдельные такты работы, всё равно возможны коррекции (обычно с использованием другой матрицы наблюдений H k ).

Этап экстраполяции

Этап коррекции

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

Выражение для ковариационной матрицы оценки вектора состояния системы справедливо только при использовании приведенного оптимального вектора коэффициентов. В общем случае это выражение имеет более сложный вид.

Инварианты

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

Математические ожидания оценок и экстраполяций вектора состояния системы, матрицы ошибок являются нуль-векторами:

где - математическое ожидание .

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

Пример построения фильтра

Представим себе вагонетку , стоящую на бесконечно длинных рельсах при отсутствии трения . Изначально она покоится в позиции 0, но под действием случайных факторов на неё действует случайное ускорение . Мы измеряем положение вагонетки каждые ∆t секунд, но измерения неточны. Мы хотим получать оценки положения вагонетки и её скорости. Применим к этой задаче фильтр Калмана, определим все необходимые матрицы.

В данной задаче матрицы F , H , R и Q не зависят от времени, опустим их индексы. Кроме того, мы не управляем вагонеткой, поэтому матрица управления B отсутствует.

Координата и скорость вагонетки описывается вектором в линейном пространстве состояний

где - скорость (первая производная координаты по времени).

Будем считать, что между (k −1 )-ым и k -ым тактами вагонетка движется с постоянным ускорением a k , распределенным по нормальному закону с нулевым математическим ожиданием и среднеквадратическим отклонением σ a . В соответствии с механикой Ньютона можно записать

.

Ковариационная матрица случайных воздействий

(σ a - скаляр).

На каждом такте работы производится измерение положения вагонетки. Предположим, что погрешность измерений v k имеет нормальное распределение с нулевым математическим ожиданием и среднеквадратическим отклонением σ z . Тогда

и ковариационная матрица шума наблюдений имеет вид

.

Начальное положение вагонетки известно точно

, .

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

, .

В этом случае на первых тактах работы фильтр будет с бо́льшим весом использовать результаты измерений, чем имеющуюся априорную информацию.

Вывод формул

Ковариационная матрица оценки вектора состояния

По определению ковариационной матрицы P k |k

подставляем выражение для оценки вектора состояния

и расписываем выражение для вектора ошибок

и вектора измерений

выносим вектор погрешности измерений v k

так как вектор погрешности измерений v k не коррелирован с другими аргументами, получаем выражение

в соответствии со свойствами ковариации векторов данное выражение преобразуется к виду

заменяя выражение для ковариационной матрицы экстраполяции вектора состояния на P k |k −1 и определение ковариационной матрицы шумов наблюдений на R k , получаем

Полученное выражение справедливо для произвольной матрицы коэффициентов, но если в качестве неё выступает матрица коэффициентов, оптимальная по Калману, то данное выражение для ковариационной матрицы можно упростить.

Оптимальная матрица коэффициентов усиления

Фильтр Калмана минимизирует сумму квадратов математических ожиданий ошибок оценки вектора состояния.

Вектор ошибки оценки вектора состояния

Стоит задача минимизировать сумму математических ожиданий квадратов компонент данного вектора

,

что эквивалентно минимизации следа ковариационной матрицы оценки вектора состояния P k |k . Подставим в выражение для ковариационной матрицы оценки вектора состояния имеющиеся выражения и дополним до полного квадрата:

Заметим что, последнее слагаемое является ковариационной матрицей некоторой случайной величины, поэтому его след неотрицателен. Минимум следа достигнется при обнулении последнего слагаемого:

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

Ковариационная матрица оценки вектора состояния при использовании оптимальной матрицы коэффициентов

Выражение для ковариационной матрицы оценки вектора состояния P k |k при использовании оптимальной матрицы коэффициентов примет вид:

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