?

Log in

No account? Create an account

Pattern recognition - Не кинокритик. Не палеонтолог.

фев. 11, 2010

04:57 pm - Pattern recognition

Previous Entry Поделиться Next Entry

Смотрим.
На входе двумерная визуальная информация. Это исходные зашумленные данные (фото, например, или кадр с камеры, или сканированный лист). Дано пространство моделей (априорно заданных возможных расшифровок), каждая из которых описывается малым объемом данных. Например, "заглавная буква А, сдвинутая на (-2, 2) и повернутая на 8 градусов по часовой стрелке". Или, для другой задачи, "двухполосное асфальтовое шоссе, поворот влево через 200 метров, закатное солнце под углом 30 градусов к горизонту, светит прямо в объектив". Каждую ситуацию умеем "рендерить", после чего проверять, насколько хорошо "рендер" совпадает с исходным изображением. Дальше, пользуясь моделью зашумленного канала, выясняем, что же на самом деле у нас на входе.
Если решать задачу распознавания в такой постановке, получается очень много, просто чудовищно много вычислений, даже в самых простых случаях (одна буква, маленькое разрешение). Поэтому все(?) делают наоборот: вычисляют какие-то агрегированные фичи исходного изображения (особые точки, контуры всякие) и строят модель по этим фичам. Рендера никакого нет.

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

Кто что скажет?
Если такое уже есть в сколько-нибудь промышленном качестве, кто покажет пальцем?

Tags: ,

Comments:

[User Picture]
From:freedom_of_sea
Date:Февраль 11, 2010 01:59 pm

это труднее чем

(Link)
а вы можете из компилятора автоматически построить формальное описание языка?
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 02:00 pm

Re: это труднее чем

(Link)
Нет.
Но это другой метауровень.
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 02:02 pm

Re: это труднее чем

(Link)
в смысле, взаимоотношения "компилятор" vs "грамматика" - не аналогия для "входа" vs "модели", а аналогия для "получение модели по входу вторым способом" vs "первым способом"
(Ответить) (Parent) (Thread)
[User Picture]
From:freedom_of_sea
Date:Февраль 11, 2010 02:45 pm

да

(Link)
"карта - не территория"
(Ответить) (Parent) (Thread)
[User Picture]
From:lyuden
Date:Февраль 11, 2010 02:47 pm
(Link)

http://web.media.mit.edu/~minsky/eb5.html

Марвин Мински рассказывает про то как они делали Builder.

По моему что-то похожее.

Либо я не понял, идеи. :)

(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 03:50 pm
(Link)
Спасибо, прочитаю
(Ответить) (Parent) (Thread)
From:(Anonymous)
Date:Февраль 11, 2010 05:13 pm
(Link)
Дабы сэкономить вам время я имел в виду параграф $5-7 Imagination и схему показывающую, что при анализе картинки машина использует информацию, о том что это могло бы быть.

Это часть книги Emotional Machine. Она мягко говоря "философская", но вроде ссылки на оригинальные работы там есть. Сам я их впрочем не читал.


"We concluded that this was because the information in our system flowed only in the input-to-output direction — so if any level made a mistake, there was no further chance to correct it."
(Ответить) (Parent) (Thread)
[User Picture]
From:begemotv2718
Date:Февраль 11, 2010 03:09 pm

Сильно пахнет нефтью

(Link)
Как то сильно ассоциируется с преобразованием Хафа (Hough transform).
Кажется и алгоритмы для него есть не столь плохие. Но это то вы, чай, и без меня знаете.
(Ответить) (Thread)
[User Picture]
From:bmalex
Date:Февраль 11, 2010 03:31 pm
(Link)
понятно, что второй подход не эквивалентный первому, т.е. преобразование должно быть приблизительным. А генеративный подход (1-ый который) в моделях, что просто решаются (например, распознавание нотного текста), намного более эффективный, чем использование фич. Потому мне кажеться, что такое преобразование возможно только на очень узком множестве моделей.

(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 03:46 pm
(Link)
Генеративный подход все равно ведь предполагает какое-то сокращение пространства перебора. Не в чистом виде же его применяют?
А на подход с фичами (как его правильно называть, кстати?) можно посмотреть как на утрированное сокращение пространства перебора, до единственного элемента. Ясно, что в промежутке возможен весь спектр.

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

В идеале я вижу систему такой: задача ставится заданием пространства моделей и процедуры "рендера" отдельных моделей. "Младшие программисты" генерируют black boxes, каждый из которых описывает процесс вычисления отдельной фичи. Вычисленная фича - это ограничения, накладываемые на пространство перебора. "Черные ящики" независимы. Система в процессе обучения или даже online комбинирует эти черные ящики наилучшим образом, используя стандартные техники из machine learning - это тупая, вполне "компьютерная" работа.
(Ответить) (Parent) (Thread)
[User Picture]
From:bmalex
Date:Февраль 11, 2010 04:25 pm
(Link)
Да, не перебором всех возможностей, но и сокращением перебора тоже сложно назвать. (например, решение квадратного уравнения по формуле - это тоже сокращение перебора? или использование фич?). Подход на основе фич, мне кажется, можно называть "на основе признаков"))

В AdaBoost используется похожий подход:
- предъявляются много reference изображений (примеры)
- предъявляются много мусора (контрпримеры)
- запускается обучение/построение каскада классификаторов.
- алгоритм обучения выбирает и настраивает параметры множества классификаторов (фич-детекторов) которое ~наилучшим~ образом позволяют распознавать исходные примеры. Но множество классификаторов, хоть и очень большое, но заранее параметрически задано.
- с пом-ю каскада можно распознавать изображения))

Для некоторых целей AdaBoos очень хорошо работает, но для многих - не работает((





(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 06:26 pm
(Link)
Про AdaBoost знаю, но там все-таки более классическая задача решается, классификатор с фиксированным небольшим множеством возможных ответов (например, 2 :)

А где не работает, кстати, расскажите? На саму задачу классификации плохо отображается, или несмещенные антипримеры сложно найти, или просто классифицирует плохо?
(Ответить) (Parent) (Thread)
[User Picture]
From:bmalex
Date:Февраль 11, 2010 09:58 pm
(Link)
Всё верно, но и на большее число ответов можно обобщить)) Честно говоря, я к AdaBoost скептически отношусь, и мне кажется, что надо перечислять то, где он вообще работает. Не работает, потому что классификаторы в нем достаточно просты и часто плохо описывают предметную задачу. А хорошо работает AdaBoost для face-detection, хотя многие пытались использовать его, где попало, но ничего не вышло (более детально рассказать у меня не получится - тут уже проще самому найти информацию).

Честно говоря, хотя этой обласит CS уже больше 50-ти лет, но поле тут не паханое, что очень грустно.
(Ответить) (Parent) (Thread)
[User Picture]
From:brainslugs.blogspot.com
Date:Февраль 11, 2010 03:45 pm
(Link)
Подход с рендером кстати вполне себе используется в распознавании позы или 3D модели человека по фото/видео. Ну, то есть не знаю насколько "используется", но часто встречается в работах на ету тему.

Там есть "словарь" пререндереных поз и тупо подбирается наиболее похожая на фото. Или несколько наиболее похожих, и между ними интерполируем.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 03:49 pm
(Link)
да, это я и сам делал :)
http://sim0nsays.livejournal.com/28898.html?thread=1008610#t1008610
(Ответить) (Parent) (Thread)
[User Picture]
From:ko444evnik
Date:Февраль 11, 2010 04:04 pm

химически чистый случай:

(Link)
http://belnetmon.livejournal.com/989870.html
(Ответить) (Thread)
[User Picture]
From:vanxant
Date:Февраль 11, 2010 06:04 pm
(Link)
Поэтому все(?) делают наоборот
Ну в-общем, не все.
Есть, кхм, область, где делают как раз впрямую. Рендерят в специально загрубленном качестве все модели со всех ракурсов, используют некоторые трюки, чтобы радикально уменьшить количество данных, потом строят дерево и по нему ищут. Каждый слой дерева - это уменьшенный в 4/8/16 раз нижележащий слой. При распознавании ищут по этому дереву. Если в момент распознавания есть некие гипотезы о том, что вероятно должно найтись, то поиск по такому дереву выполняется буквально за единицы вычислений решающей функции.
В целом, по сути, используется обычное предварительное вычисление данных. Скорость за счет памяти. Если удается решить вопрос с памятью под эталоны, то даже не на самом мощном железе возможно реал-тайм распознавание.
Понятно, что "универсальный распознаватель всего и вся" на этом подходе не сделаешь, но для многих практических задач это давно реализовано без всяких обратных схем.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 06:16 pm
(Link)
> Есть, кхм, область, где делают как раз впрямую
А где, если не секрет?
(Ответить) (Parent) (Thread)
[User Picture]
From:_foreseer
Date:Февраль 11, 2010 06:33 pm
(Link)
думаю наведение бомб на танки или типа того
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Февраль 11, 2010 06:38 pm
(Link)
Ну так бы и говорили прямо, что футбол роботов.
А то "область", "область".
(Ответить) (Parent) (Thread)
[User Picture]
From:bekabaka
Date:Март 9, 2010 07:19 pm
(Link)
По-моему это просто ассоциативная память, нэ?
(Ответить) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:Февраль 11, 2010 08:07 pm
(Link)
А ты же видел этот TED-talk где чувак показывает новое поколение нейронных сетей -- типа генеративное, где есть слой генераторов, умеющих создавать какие-то выходные образы (куски изображений цифр), и слой или два активаторов, сопоставляющих целевые значения (сами цифры) активированным генераторам (в обе стороны). Ну и всё это совместно обучается. Кажется так, если я правильно помню. Там самое замечательно было -- можно было посмотреть "мысли" девайса, когда ему говорят "представь цифру два".
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Февраль 12, 2010 09:53 am
(Link)
Так, я с нового года встал на путь исправления, и если я чего-то стыдного не знаю, то я в этом немедленно признаюсь. Так лучше и полезнее, чем делать вид, что всё ок.

Я ВООБЩЕ НЕ ЗНАЮ ЧТО ТАКОЕ TED-talk :)
Сейчас пойду самообразуюсь.
(Ответить) (Parent) (Thread)
[User Picture]
From:faceted_jacinth
Date:Февраль 12, 2010 11:02 am
(Link)
Стоп, я всё перепутал. То есть не стоп, TED прикольный в любом случае, но эта штука оказывается была в гугле: http://www.youtube.com/watch?v=AyzOUbkUf3M -- эффективно обучающаяся Boltzmann machine.

Причём у меня сейчас возникло подозрение, что я её у тебя и увидел в общем-то =)
(Ответить) (Parent) (Thread)
[User Picture]
From:plakhov
Date:Февраль 12, 2010 11:09 am
(Link)
А, я понял теперь, о чем ты. Увидел ты у _foreseer'а, видимо. Я от него об этом впервые услышал. Ну или в его комментарии здесь, не помню уже.
(Ответить) (Parent) (Thread)