GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (7)След. > >>   Поиск:  
 Автор Тема: Похожесть двух множеств. Решения.
Kek
Сообщений: 1133
Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 2:26
Изменено: 07 мар 14 2:30
Сформулирую вопрос, который возник у меня в рамках темы Sound-Agent. Вопрос весьма практический и можно сказать узкий. Но это как посмотреть… Речь идет в абстрактном смысле о сравнении двух множеств. Чтобы было меньше абстракции поясню. На рисунке две реализации огибающей слова «молоко».

Т.е. априори мы знаем, что два этих множества обозначают один объект. Смотря на них глазами без всяких умствований, тоже можно сказать, что они похожи. До сих пор я применял корреляционную обработку для анализа похожести. Но тут есть один минус. Множества должны быть одной длинны. Если их тупо пропустить через обработку, обрезав лишнее у более длинного множества, то результат будет таков: коэффициент корреляции = 0.33
Это не отражает нашу субъективную оценку и априорное знание.
Что можно сделать? А это конформные отображения. Математики очень любят пугать малышей этой теорией. Но на самом деле эта задача для программиста выглядит так:
Каждую точку из одной реализации можно мысленно переместить на место в другой. Перемещение может быть произведено по четырем направлениям: вверх, вниз, вперед и назад. И еще можно точку удалить или добавить. Всего шесть действий над точкой, чтобы одно множество превратить в другое. Каждое действие имеет свой вес. Например перемещение вверх на четыре позиции, или на одну. Понятно, что на одну весит меньше. И т.д.
В результате всех действий над точками получается количество действий и общий вес. Минимальность этих двух цифр говорит о большей похожести двух множеств.
Вопрос заключается в том, может кто-то это применяет вовсю? Если нет, то мне кажется это хороший метод и его надо реализовать.
[Ответ][Цитата]
Vpolevoj
Сообщений: 1408
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 3:04
Изменено: 07 мар 14 3:06
Цитата:
Автор: Kek
Речь идет о сравнении двух множеств.

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

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

Из приведенных тобой картинок видно (что называется, невооруженным взглядом), что обе огибающие, если и не равны между собой, то очень похожи (мы в таких случаях говорим, что они ПОДОБНЫ). И сравнительные методы должны были бы это нам показать. Но проблема с их сравнением заключается в том, что множества их описывающие НЕ РАВНЫ. А по идее, должны бы быть равны (просто потому, что так нам было бы проще и удобнее их сравнивать). Но как это можно сделать?

Вот ты привел один способ - обрезать одно из множеств по краю. И он, что совершенно очевидно, не годится, так как первоначально явно одинаковые множества безвозвратно делает явно неодинаковыми.

Но если ли какие-нибудь еще способы приведения двух множеств к одинаковому состоянию, но которые бы не уничтожали их подобие?

Я думаю, что такие способы есть.

Например, сам собой напрашивается метод МАСШТАБИРОВАНИЯ одной из кривой. Вот если бы я имел дело только с графической компонентой (только с линиями графиков), то я бы взял одну из сравниваемых тобой линий и растянул/сжал бы её до размеров другой линии, так, чтобы их длины стали бы одинаковыми. И, глядя на твой рисунок, видно, что они после такой процедуры практически совпали бы.

Но как это можно сделать не графически, а с массивом чисел?

Теоретически можно довольно легко привести одно множество к другому по количеству элементов их составляющих путем РАВНОМЕРНОГО УДАЛЕНИЯ ЛИШНИХ элементов из большего множества. (Представь это действие мысленно: что будет происходить с более длинным графиком на твоём рисунке, если равномерно по всей длине удалить из него часть "лишних" точек?)

А когда два множества уравнены, то процесс сравнения их между собой становится очевидным. И для этого можно применить любой доступный тебе метод.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 3:32
>Vpolevoj
Понимашь. В той области, в которой мне это интересно может возникнуть ситуация, когда одна реализация нелинейно сжата, относительно другой. Например. На картинке вобще-то два горба. Один расщиплен на два пика. Может оказаться так, что расстояния между пиками разные и изменяя линейно масштаб мы не придем к идентичности. Но при этом все эти реализации априори одно и тоже по звучанию.
Есть еще метод под название расстояние Хемминга. Но оно тоже применяется к множествам с одинаковой мощностью, т.е. с одинаковым числом элементов.
Поэтому то, что я предлагаю может решить проблему инвариантности и в звуке и в изображении.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 4:00
Изменено: 07 мар 14 4:01
[Ответ][Цитата]
rrr3
Сообщений: 11857
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 4:02
Изменено: 07 мар 14 4:06
Такое ощущение, что по прежнему идет поиск относительно универсального алгоритма....
При достаточно сложных задачах распознавания универсальность в таком ключе, что описан в ищется как в этой, так и в той ветке - тупиковый вариант. Мозг создает (истин не глаголю) множество алгоритмов приводящих к одному и тому же результату, например, "присвоению" достаточно разнообразным входным совокупностям входных сигналов - присвоения результирующего "значения", как "молоко".
Иными словами универсальность может быть достигнута на ином уровне, на уровне системы способной автоматически создавать эти множества алгоритмов "присвоения" (обучаться, так сказать, в соответствующих обучающих условиях внешней среды), в частности комбинацией более мелких "микроалгоритмов", как это описано в Солянке.
Другого более универсального варианта, вероятно нет.
Или же остается создавать такие системы "присвоения" вручную, или же заужать задачи соответственно зауженности универсальности придуманных вариантов решений.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 4:22
Цитата:
Автор: rrr3

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

А откуда беруться мелкие "микроалгоритмы"? Неужто из наноалгоритмов?
[Ответ][Цитата]
rrr3
Сообщений: 11857
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 4:32
Изменено: 07 мар 14 4:34
Цитата:
Автор: Kek
А откуда беруться мелкие "микроалгоритмы"? Неужто из наноалгоритмов?


Из Вашей головы. Конкретное их изначальное значение (присвоение конкретному/ным выходу/дам конкретный/ые "сигнал/ы" на в ответ на конкртный/ые сигнал/ы на входах) не имеет значение имеет значение их разнообразие и прочее по тексту, где... - говорил не раз.
Так же как не имеет значение изначальное расположение отдельной песчинки при заполнении бутылки шампанского...
(Я ответил серьезно, хотя Вы просто пошутили).
[Ответ][Цитата]
covax
Сообщений: 1609
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 4:34
Цитата:
Автор: Kek
Речь идет в абстрактном смысле о сравнении двух множеств. Чтобы было меньше абстракции поясню. На рисунке две реализации огибающей слова «молоко».


Вопрос в том, должны ли быть равны эти множества? Возможно за этой разницей скрывается звучание еще нескольких слов например "рококо","салака" а вы сейчас пытаетесь "натянуть" образ звучания одного слова на образ другого. Вы то знаете, что это одно слово, а компьютер нет! Да и я вижу, что это два разных слова.
Если не видна разница или она не очевидна - дифференцируйте глубже. Кстати, непонятно почему у вас по одной огибающей, а не по тысяче (хотя бы) на каждое слово?
Какой природы огибающая у вас?
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 4:54
Цитата:
Автор: rrr3
(Я ответил серьезно, хотя Вы просто пошутили).

Я не шутил. Поиск минимально достаточного и необходимого количествоа алгоритмов - вот задача, которую я пытаюсь понять на конкретном потоке. Что-то надо написать ручками. И это что-то конечное число. Во всем остальном вы правы. Из этих микроалгоритмов вырастают сложные действия.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 5:04
Цитата:
Автор: covax
Вопрос в том, должны ли быть равны эти множества?

Вы забегаете вперед. Вообщем-то правильно ставите вопросы. Я говорю без касательства остальных вещей таких как обучение и т.д. Здесь надо сконцентрироваться на узкой проблеме. И она звучит так как я озвучил. Реализация способа сравнения двух множеств различной мощности - это универсальная задача распознавания вообще. Как дальше эта задача встраивается в контекст - это более высокого порядка штука и мне не хотелось бы сейчас об этом говорить. Скажу только, что эталоны слов или фонем для сравнения могут формироваться двумя способами. 1 - четкое обучение. 2 - на основе кластеризации потока, выделения из него часто повторяющихся участков. Без сравнения все равно никуда. Вот и чешу репу.
[Ответ][Цитата]
гость
78.25.120.*
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 5:20
можно подумать в духе 'эластичных преобразований'. Если длина образцов ненормализована, но тем не менее есть эталон, то сначала нужно выделить
самые характерные точки (напр. максимумы или 'околомаксимумные' окрестности)
и совместить их, укладывая (подтягивая) промежуточные точки с соответсвующими
местными деформациями (концы не обязательно искуственно выравнивать), посчитывая
т.ск. энергию деформации (растяжения-сжатия). Эсперимент покажет, может ли подобная
процедура дать хорошую меру сходства.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 5:22
Цитата:
Автор: covax
Возможно за этой разницей скрывается звучание еще нескольких слов например "рококо","салака" а вы сейчас пытаетесь "натянуть" образ звучания одного слова на образ другого.

Вот это поясню. Представим есть некий метод сравнения. И есть эталонное обучение. По нему эталон "молоко" и "рококо" совпадают. Совпадают так же еще сотня слов. Зато слово "алюмосиликаты" точно не входит в список похожих. Конечно же только анализом огибающей дело не заканчивается. Просто этот метод быстрый и лежит в начале пирамиды методов.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 5:24
Изменено: 07 мар 14 5:29
Цитата:
Автор: гость 78.25.120

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

Вы попали в точку. Я именно так и делаю сейчас. Выделяю пики и сравниваю их характеристики.
P.S. Просто подумал, что есть универсальный мат метод. Но к сожалению его нет. Самый близкий - это Расстояние Левенштейна, который надо модифицировать
[Ответ][Цитата]
гость
78.25.120.*
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 5:24
Если А сходна с эталоном, и B cходна с эталоном, то между собою они могут быть
уже заметно несходными.
[Ответ][Цитата]
Kek
Сообщений: 1133
На: Похожесть двух множеств. Решения.
Добавлено: 07 мар 14 5:26
Изменено: 07 мар 14 5:27
Цитата:
Автор: гость 78.25.120
Если А сходна с эталоном, и B cходна с эталоном, то между собою они могут быть
уже заметно несходными.

Ошибки можно избежать если выстроить серию методов, которые "ортогональны". Например в низу - анализ огибающей, далее анализ спектров и т.д. Совокупность методов даст адекват.
[Ответ][Цитата]
 Стр.1 (7): [1]  2  3  4  5  ...  7След. > >>