Обсуждение:Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)
Материал из MachineLearning.
(20 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
Добрый день! | Добрый день! | ||
- | + | Возник вопрос по поводу [[Структурные_методы_анализа_изображений_и_сигналов_(курс_лекций)_/_Задание_2#.D0.92.D0.B0.D1.80.D0.B8.D0.B0.D0.BD.D1.82_3|задания 3]]. Нашёл следующие непонятные для себя моменты: | |
*«где <tex>c_{0,j},\ldots,c_{M,j}</tex> — коэффициенты авторегрессии, которые зависят от состояния СММ.» Т.е коэффициентов М+1 штука. В то же время в описании функций сказано: «C — коэффициенты авторегрессии, матрица типа double размера K x M;» Не ясно, где ошибка - M или М+1. | *«где <tex>c_{0,j},\ldots,c_{M,j}</tex> — коэффициенты авторегрессии, которые зависят от состояния СММ.» Т.е коэффициентов М+1 штука. В то же время в описании функций сказано: «C — коэффициенты авторегрессии, матрица типа double размера K x M;» Не ясно, где ошибка - M или М+1. | ||
Строка 10: | Строка 10: | ||
''[[Участник:Василий Ломакин|Василий Ломакин]] 20:14, 1 ноября 2009 (MSK)'' | ''[[Участник:Василий Ломакин|Василий Ломакин]] 20:14, 1 ноября 2009 (MSK)'' | ||
- | Василий, здравствуйте. По сути в Вашем вопросе уже содержатся ответы: | + | :Василий, здравствуйте. По сути, в Вашем вопросе уже содержатся ответы: |
- | * Матрица <tex>C\in\mathbb{R}^{K\times M</tex>; | + | :* Матрица <tex>C\in\mathbb{R}^{K\times M</tex>; |
- | * В качестве величины <tex>c_{0,j}</tex> используйте <tex>d</tex>-мерный вектор | + | :* В качестве величины <tex>c_{0,j}</tex> используйте <tex>d</tex>-мерный вектор Mu_j из спецификации СММ; |
- | * Коэффициенты авторегрессии <tex>c_{m,j}</tex> '''считаем общими''' для всех размерностей вектора <tex>x_n</tex>. Таким образом, получаем линейную комбинацию векторов и никаких некорректностей не возникает. | + | :* Коэффициенты авторегрессии <tex>c_{m,j}</tex> '''считаем общими''' для всех размерностей вектора <tex>x_n</tex>. Таким образом, :получаем линейную комбинацию векторов и никаких некорректностей не возникает. |
+ | : | ||
+ | :Желаю Удачи. | ||
+ | : | ||
+ | :--[[Участник:Dmitry Vetrov|Д.П. Ветров]] 16:15, 2 ноября 2009 (MSK) | ||
- | + | ::Я так и подумал (собственно так уже и реализовал), но на всякий случай решил уточнить. Спасибо за интересное задание! | |
- | --[[Участник: | + | :: |
+ | ::[[Участник:Василий Ломакин|Василий Ломакин]] 08:41, 3 ноября 2009 (MSK) | ||
+ | |||
+ | ---- | ||
+ | |||
+ | Здравствуйте! Появился вопрос по поводу 1 варианта 2 задания. | ||
+ | |||
+ | При реализации функции HMM_TEST нужно хранить величину lj (сколько моментов времени мы находимся в данном состоянии) для каждого | ||
+ | t(n,j). Как рассчитывать эту величину, если мы не знаем ни того состояния, в котором находимся в начальный момент времени, ни того состояния, куда переходим? Или нужно делать полный перебор для состояния t(n-1,i) по состояниям t(n,j), то есть из каждого состояния можем попасть в одно из К? | ||
+ | |||
+ | Надеюсь на Ваши разъяснения! | ||
+ | Извините за корявый вопрос, лучше сформулировать не удалось. | ||
+ | |||
+ | [[Участник:Марина|Марина Дударенко]] 14:30, 13 ноября 2009 (MSK) | ||
+ | |||
+ | :Один из возможных способов решения задачи — вводить функцию Беллмана <tex>V_n(j)</tex> как стоимость оптимальной траектории при условии, что в момент времени <tex>n</tex> мы находимся в состоянии <tex>j</tex>, причем в следующий момент времени произойдет переход в другое состояние. Пусть <tex>a</tex> и <tex>b</tex> — соответственно минимально и максимально допустимая длина одного сегмента. Тогда функция Беллмана <tex>V_n(j)</tex> вычисляется как максимум по моментам времени <tex>k = n-b,\dots,n-a</tex> ситуаций, что в момент времени <tex>k</tex> был переход в состояние <tex>j</tex> и затем в этом состоянии мы находились <tex>n-k</tex> отсчетов. Таким образом, в отличие от классического алгоритма Витерби здесь пересчет идет по моментам смены состояния сигнала. Сложность алгоритма соответственно возрастает в <tex>b-a</tex> раз. | ||
+ | :[[Участник:Kropotov|Д.А. Кропотов]] 20:53, 13 ноября 2009 (MSK) | ||
+ | |||
+ | ::Спасибо большое за разъяснение! | ||
+ | ::[[Участник:Марина|Марина Дударенко]] 20:27, 15 ноября 2009 (MSK) Дударенко Марина | ||
+ | |||
+ | ---- | ||
+ | |||
+ | Здравствуйте! Не могли бы вы проверить, правильно ли я вывел формулы для M-шага EM-алгоритма в случае авторегрессионной скрытой марковской модели: | ||
+ | |||
+ | <tex>\textstyle\mu_{j^*} = \frac{\sum_{i=1}^N \gamma(t_{ij^*})\(x_i - \sum_{m=1}^Mc_{mj^*}x_{i-m}\)}{\sum_{i=1}^N \gamma(t_{ij^*})}</tex>; | ||
+ | |||
+ | <tex>\textstyle\Sigma = \frac | ||
+ | {\sum_{j=1}^K \sum_{i=1}^N \gamma(t_{ij})\(x_i - \sum_{m=1}^Mc_{mj}x_{i-m}\)^T\(x_i - \sum_{m=1}^Mc_{mj}x_{i-m}\)} | ||
+ | {\sum_{i=1}^N \gamma(t_{ij^*})}</tex>; | ||
+ | |||
+ | <tex>\textstyle c_{m^*j^*} = \frac | ||
+ | {\sum_{i=1}^N \gamma(t_{ij}) x_{i-m^*}^T \left(x_i - \mu_{j^*} - \sum_{m\not=m^*}\left(c_{mj^*}x_{i-m}\right) \right)} | ||
+ | {\sum_{i=1}^N \gamma(t_{ij^*}) x_{i-m^*}^T x_{i-m^*} }</tex>; | ||
+ | |||
+ | [[Участник:Василий Ломакин|Василий Ломакин]] 10:43, 23 ноября 2009 (MSK) | ||
+ | |||
+ | :*Формула для <tex>\mu_j</tex> правильная. | ||
+ | :*Формула для <tex>\Sigma</tex> не совсем правильная. Во-первых, в знаменателе должна стоять еще и сумма по всем <tex>j</tex>. Что такое у вас <tex>j^*</tex> в формуле для <tex>\Sigma</tex> — не совсем понятно. Во-вторых, в числителе должен быть вектор <tex>\mu_j</tex> в мат.ожидании, т.е. компоненты вида <tex>x_i-\mu_j-\sum_{m=1}^Mc_{mj}x_{i-m}</tex>. В-третьих, обычно в векторной нотации вектор — это вектор-столбец, т.е. для получения матрицы должно быть выражение вида <tex>vv^T</tex>. Если у вас под вектором понимается вектор-строка, то формула правильная, если нет, то транспонирование должно быть в другом месте. | ||
+ | :*Формула для <tex>c_{mj}</tex> абсолютно неправильная. Помимо прочего она должна зависеть от матрицы <tex>\Sigma</tex> и не зависеть от остальных компонент <tex>c_{mj}</tex>. Попробуйте еще подумать над формулой для <tex>c_j</tex>. Советую выводить эту формулу сразу для вектора <tex>c_j</tex>, а не для отдельных его компонент. Если не будет получаться, то тогда, что делать, подскажу правильный вариант. | ||
+ | : Крайний срок сдачи второго задания с уменьшением оценки за позднюю сдачу - ближайшее воскресенье, 29 ноября. После этого срока задание принято не будет (соответственно не будет допуска к экзамену). — [[Участник:Kropotov|Д.А. Кропотов]] 19:39, 23 ноября 2009 (MSK) | ||
+ | |||
+ | ::Да, прошу прощения, при наборе формулы для ковариационной матрицы я напутал, все ваши замечания правильные. | ||
+ | ::Насчёт <tex>c_j</tex> - попробую последовать вашему совету. Эта идея приходила мне в голову, но меня остановило то, что мы не изучали дифференцирование по вектору (по <tex>c_j</tex>). | ||
+ | ::Насчёт сдачи задания - я ведь его уже сдал, вы его не получили или пока не проверяли? В readme я указал, что выведенные мной формулы работают только для случая <tex>M</tex> = 1. В общем я разберусь в вопросе и новую версию программы досдам, надо же всё-таки работу до конца довести. Если что-то не получится, подойду к вам в четверг. [[Участник:Василий Ломакин|Василий Ломакин]] 21:47, 23 ноября 2009 (MSK) | ||
+ | :::#Ваше задание не было получено. Из 517 группы задание получено только от Одиноковой Евгении. В системе проверки задания в таблице есть строчка от еще одного представителя 517 группы, но самого архива с работой нет. Возможно, вы что-то не так сделали на этапе загрузки задания на сервер. Попробуйте загрузить свой архив еще раз. | ||
+ | :::#Что касается дифференцирования по вектору, то вам понадобятся только два следующих свойства: <tex>\frac{d}{d\vec{x}}\vec{x}^T\vec{b}=\vec{b}</tex> и <tex>\frac{d}{d\vec{x}}\vec{x}^TA\vec{x}=2A\vec{x}</tex>. Оба этих свойства легко проверяются путем покоординатного дифференцирования. | ||
+ | :::— [[Участник:Kropotov|Д.А. Кропотов]] 22:23, 23 ноября 2009 (MSK) | ||
+ | ::::# Очень странно, только что зашёл на сайт и скачал оттуда своё собственное задание. Что я делаю не так? Всё равно загрузить повторно? | ||
+ | ::::# Да, спасибо, вывести уже получилось, сейчас проверяю как оно работает... | ||
+ | ::::И ещё вопрос - а почему заведомо не работала формула, описанная выше? Я принципиально ошибся при дифференцировании или по какой-то причине всё равно не получится рассчитать <tex>c_{mj}</tex> покоординатно? [[Участник:Василий Ломакин|Василий Ломакин]] 23:36, 23 ноября 2009 (MSK) | ||
+ | :::::Я попробую выяснить у администратора ресурса, с чем могут быть связаны проблемы при загрузке задания. Может быть в системе после того, как задание загружено, нужно нажать на какую-нибудь кнопку «отправить задание на проверку»? | ||
+ | :::::Ваша формула для <tex>c_{mj}</tex> переходит в правильную при <tex>M=1</tex>. Что касается возможности покоординатного вычисления, то при выводе соответствующих формул в какой-то момент должна возникнуть система линейных уравнений. Если СЛАУ записана в векторной форме <tex>A\vec{x}=\vec{b}</tex>, то очень просто записать ответ в явном виде <tex>\vec{x}=A^{-1}\vec{b}</tex>. Кроме того, в том случае, если матрица <tex>A</tex> вдруг окажется вырожденной или плохо обусловленной, то сразу понятно, что делать — находить нормальное псевдорешение по формуле <tex>\vec{x}=(A^TA+\lambda I)^{-1}A^T\vec{b}</tex> для некоторого небольшого <tex>\lambda</tex>. В принципе можно выписать явную формулу и для отдельной компоненты <tex>x_i</tex> по правилу Крамера, но в таком виде формула получится громоздкой и долго вычисляемой на компьютере. | ||
+ | :::::[[Участник:Kropotov|Д.А. Кропотов]] 01:42, 24 ноября 2009 (MSK) | ||
+ | ::::::Только что загрузил задание. Нашёл в интерфейсе кнопку "Подтвердить задание", нажал её, может быть это поможет. Хотя помню, что при загрузке задания по удалению шума её не нажимал. Чтобы всё было честно добавил в архив и старый вариант, отправленный неделю назад. Новый отличается модификацией обучения <tex>c</tex> в EM-алгоритме и несколько более читабельным кодом. Алгоритм Витерби и генерация выборки такие же. Судите сами заслуживает ли это штрафа и в каком объёме :) Спасибо! [[Участник:Василий Ломакин|Василий Ломакин]] 14:27, 24 ноября 2009 (MSK) | ||
+ | |||
+ | ::::::И ещё вопрос вдогонку - а где лучше почитать про дифференцирование по вектору, по матрице и т.п.? | ||
+ | :::::::Да, теперь задание получено. | ||
+ | :::::::Про дифференцирование по векторам и матрицам вкратце написано в приложении C книги Bishop C.M. Pattern Recognition and Machine Learning, Springer, 2006. Кроме того, многие модели в этой книги выводятся с использованием матричной нотации. | ||
+ | :::::::[[Участник:Kropotov|Д.А. Кропотов]] 22:00, 24 ноября 2009 (MSK) |
Текущая версия
Добрый день! Возник вопрос по поводу задания 3. Нашёл следующие непонятные для себя моменты:
- «где — коэффициенты авторегрессии, которые зависят от состояния СММ.» Т.е коэффициентов М+1 штука. В то же время в описании функций сказано: «C — коэффициенты авторегрессии, матрица типа double размера K x M;» Не ясно, где ошибка - M или М+1.
- , где - число, - вектор, получается сложение вектора с числом. Хотя если смотреть с точки зрения матлаба, вопрос отпадает :)
- В описании функций указано «Mu — константы в центрах гауссиан для каждого состояния, матрица типа double размера K x d, в которой в каждой строке стоит вектор для соответствующего состояния; ». Но по формуле Mu на каждом шаге генерится только с помощью авторегрессии. Для чего тогда передавать этот параметр?
Василий Ломакин 20:14, 1 ноября 2009 (MSK)
- Василий, здравствуйте. По сути, в Вашем вопросе уже содержатся ответы:
- Матрица ;
- В качестве величины используйте -мерный вектор Mu_j из спецификации СММ;
- Коэффициенты авторегрессии считаем общими для всех размерностей вектора . Таким образом, :получаем линейную комбинацию векторов и никаких некорректностей не возникает.
- Желаю Удачи.
- --Д.П. Ветров 16:15, 2 ноября 2009 (MSK)
- Я так и подумал (собственно так уже и реализовал), но на всякий случай решил уточнить. Спасибо за интересное задание!
- Василий Ломакин 08:41, 3 ноября 2009 (MSK)
Здравствуйте! Появился вопрос по поводу 1 варианта 2 задания.
При реализации функции HMM_TEST нужно хранить величину lj (сколько моментов времени мы находимся в данном состоянии) для каждого t(n,j). Как рассчитывать эту величину, если мы не знаем ни того состояния, в котором находимся в начальный момент времени, ни того состояния, куда переходим? Или нужно делать полный перебор для состояния t(n-1,i) по состояниям t(n,j), то есть из каждого состояния можем попасть в одно из К?
Надеюсь на Ваши разъяснения! Извините за корявый вопрос, лучше сформулировать не удалось.
Марина Дударенко 14:30, 13 ноября 2009 (MSK)
- Один из возможных способов решения задачи — вводить функцию Беллмана как стоимость оптимальной траектории при условии, что в момент времени мы находимся в состоянии , причем в следующий момент времени произойдет переход в другое состояние. Пусть и — соответственно минимально и максимально допустимая длина одного сегмента. Тогда функция Беллмана вычисляется как максимум по моментам времени ситуаций, что в момент времени был переход в состояние и затем в этом состоянии мы находились отсчетов. Таким образом, в отличие от классического алгоритма Витерби здесь пересчет идет по моментам смены состояния сигнала. Сложность алгоритма соответственно возрастает в раз.
- Д.А. Кропотов 20:53, 13 ноября 2009 (MSK)
- Спасибо большое за разъяснение!
- Марина Дударенко 20:27, 15 ноября 2009 (MSK) Дударенко Марина
Здравствуйте! Не могли бы вы проверить, правильно ли я вывел формулы для M-шага EM-алгоритма в случае авторегрессионной скрытой марковской модели:
;
;
;
Василий Ломакин 10:43, 23 ноября 2009 (MSK)
- Формула для правильная.
- Формула для не совсем правильная. Во-первых, в знаменателе должна стоять еще и сумма по всем . Что такое у вас в формуле для — не совсем понятно. Во-вторых, в числителе должен быть вектор в мат.ожидании, т.е. компоненты вида . В-третьих, обычно в векторной нотации вектор — это вектор-столбец, т.е. для получения матрицы должно быть выражение вида . Если у вас под вектором понимается вектор-строка, то формула правильная, если нет, то транспонирование должно быть в другом месте.
- Формула для абсолютно неправильная. Помимо прочего она должна зависеть от матрицы и не зависеть от остальных компонент . Попробуйте еще подумать над формулой для . Советую выводить эту формулу сразу для вектора , а не для отдельных его компонент. Если не будет получаться, то тогда, что делать, подскажу правильный вариант.
- Крайний срок сдачи второго задания с уменьшением оценки за позднюю сдачу - ближайшее воскресенье, 29 ноября. После этого срока задание принято не будет (соответственно не будет допуска к экзамену). — Д.А. Кропотов 19:39, 23 ноября 2009 (MSK)
- Да, прошу прощения, при наборе формулы для ковариационной матрицы я напутал, все ваши замечания правильные.
- Насчёт - попробую последовать вашему совету. Эта идея приходила мне в голову, но меня остановило то, что мы не изучали дифференцирование по вектору (по ).
- Насчёт сдачи задания - я ведь его уже сдал, вы его не получили или пока не проверяли? В readme я указал, что выведенные мной формулы работают только для случая = 1. В общем я разберусь в вопросе и новую версию программы досдам, надо же всё-таки работу до конца довести. Если что-то не получится, подойду к вам в четверг. Василий Ломакин 21:47, 23 ноября 2009 (MSK)
- Ваше задание не было получено. Из 517 группы задание получено только от Одиноковой Евгении. В системе проверки задания в таблице есть строчка от еще одного представителя 517 группы, но самого архива с работой нет. Возможно, вы что-то не так сделали на этапе загрузки задания на сервер. Попробуйте загрузить свой архив еще раз.
- Что касается дифференцирования по вектору, то вам понадобятся только два следующих свойства: и . Оба этих свойства легко проверяются путем покоординатного дифференцирования.
- — Д.А. Кропотов 22:23, 23 ноября 2009 (MSK)
- Очень странно, только что зашёл на сайт и скачал оттуда своё собственное задание. Что я делаю не так? Всё равно загрузить повторно?
- Да, спасибо, вывести уже получилось, сейчас проверяю как оно работает...
- И ещё вопрос - а почему заведомо не работала формула, описанная выше? Я принципиально ошибся при дифференцировании или по какой-то причине всё равно не получится рассчитать покоординатно? Василий Ломакин 23:36, 23 ноября 2009 (MSK)
- Я попробую выяснить у администратора ресурса, с чем могут быть связаны проблемы при загрузке задания. Может быть в системе после того, как задание загружено, нужно нажать на какую-нибудь кнопку «отправить задание на проверку»?
- Ваша формула для переходит в правильную при . Что касается возможности покоординатного вычисления, то при выводе соответствующих формул в какой-то момент должна возникнуть система линейных уравнений. Если СЛАУ записана в векторной форме , то очень просто записать ответ в явном виде . Кроме того, в том случае, если матрица вдруг окажется вырожденной или плохо обусловленной, то сразу понятно, что делать — находить нормальное псевдорешение по формуле для некоторого небольшого . В принципе можно выписать явную формулу и для отдельной компоненты по правилу Крамера, но в таком виде формула получится громоздкой и долго вычисляемой на компьютере.
- Д.А. Кропотов 01:42, 24 ноября 2009 (MSK)
- Только что загрузил задание. Нашёл в интерфейсе кнопку "Подтвердить задание", нажал её, может быть это поможет. Хотя помню, что при загрузке задания по удалению шума её не нажимал. Чтобы всё было честно добавил в архив и старый вариант, отправленный неделю назад. Новый отличается модификацией обучения в EM-алгоритме и несколько более читабельным кодом. Алгоритм Витерби и генерация выборки такие же. Судите сами заслуживает ли это штрафа и в каком объёме :) Спасибо! Василий Ломакин 14:27, 24 ноября 2009 (MSK)
- И ещё вопрос вдогонку - а где лучше почитать про дифференцирование по вектору, по матрице и т.п.?
- Да, теперь задание получено.
- Про дифференцирование по векторам и матрицам вкратце написано в приложении C книги Bishop C.M. Pattern Recognition and Machine Learning, Springer, 2006. Кроме того, многие модели в этой книги выводятся с использованием матричной нотации.
- Д.А. Кропотов 22:00, 24 ноября 2009 (MSK)
- И ещё вопрос вдогонку - а где лучше почитать про дифференцирование по вектору, по матрице и т.п.?