Инвариантом функции f называется преобразование входа функции, которое не меняет ее выход, или меняет его по известному закону. Например, соотношения f( x ) = f( 100 - x ); g( x, y ) = g( y, x ); h( x, y ) = - h( -y, x ) описывают различные инварианты функций f, g, h.

Андрей Плахов
Вопрос, думаю, лучше сразу формулировать на примерах.

Предположим, часть входов - матрица 64х64, на которую подаются сигналы с камеры. Сможет ли система сформулировать понятие "предмета" как продолжающейся во времени, медленно изменяющейся контрастной части входа? Если не сможет сама, то как человек может ей это "объяснить"? Может ли система сформулировать нечеткое правило "если на входе контур, похожий на №18743, и мы находимся в лесу, то убегать быстрее"? Если да, то как она будет формулировать понятие "похожести" - на многослойных нейросетях? Вход, сдвинутый влево на 1 вход, для нейросети совершенно "непохож" на исходный...

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

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

supremum
"Сможет ли система сформулировать понятие "предмета " как продолжающейся во времени, медленно изменяющейся контрастной части входа? "
ИНС можно заставить распознать токой "предмет " в последовательности кадров изображений. По идее система может построить такую ИНС самостоятельно. Главное, что бы введенное понятие было полезным для системы.

"Если да, то как она будет формулировать понятие "похожести " - на многослойных нейросетях? Вход, сдвинутый влево на 1 вход, для нейросети совершенно "непохож " на исходный... "
Смотря для какой сети. Лично я могу построить сеть выполняющую инвариантное преобразование относительно сдвига не выходя за рамки языка сети. Думаю, что и с другими преобразованиями сеть справится.
Если системе понадобится такие сети, они могут быть построены автоматически.

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

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

Если очень хочется, то наверное можно. Однако цель проекта заключается в создании самостоятельно обучающихся систем.

"Мне кажется, что слово "нечеткий инвариант " - хорошее практическое уточнение слова "понятие ", и что нейронные сети не способны к выделению нечетких инвариантов. "
Что такое нечеткий инвариант? Можно формальное определение? Можно простенький пример такого инварианта?

Андрей Плахов
>я могу построить сеть выполняющую инвариантное преобразование относительно сдвига не выходя за рамки языка сети

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

>Если системе понадобится такие сети, они
>могут быть построены автоматически
Вот это и интересно, как?

supremum
Неинвариантных преобразований относительно чего, какой операции?

">Если системе понадобится такие сети, они
>могут быть построены автоматически
Вот это и интересно, как?"

Путем эволюции структуры(случайный поиск), настройки весов и отбора.

Андрей Плахов
>Неинвариантных преобразований
>относительно чего, какой операции?

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

Иван FXS
А можно - для ежиков - разжевать:
что ВООБЩЕ такое "Х, моделирующий любую кус.-непрерывную функцию, инвариантную относительно сдвигов, причем выход любого Х _заведомо_ инвариантен относительно любого сдвига "?

1. существует ли на свете пример такого Х?
2. что такое "моделирование функции ": вот есть функция
F(x)=2*x+1 - Вы, Андрей, чем можете ее "смоделировать "?
3. приведите - умоляю - хоть один пример "функции, инвариантной относительно сдвигов ", - очень хочется понять, о чем речь!

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

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

Я называю функцию от N^2 аргументов инвариантной отн. сдвигов, если она такая: представим себе ее вход как квадрат NxN. Пусть входы по границе были нулевые, а мы взяли и "сдвинули " этот квадрат в сторону. Получился новый вход. Ф-ия инвариантна, если ее значение от любого такого сдвига не меняется.

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

Иван FXS
О! Я понял!! И - скажу Вам по секрету, что Арифметические Нейронные Сети (которым в слове GARANT "соответсвуют " 4-я и 5-я буквы ;-) ) - в легкую РЕАЛИЗУЮТ все эти три перечисленные Вами функции!

(((Кстати о птичках: функция F(x)=2*x+1 РЕАЛИЗУЕТСЯ АНС (Арифметической Нейронной Сетью), состоящей из двух последовательно соединенных нейронов:
передаточная функция первого - умножение на два,
а передаточная функция второго - прибавление единицы. Не знаю вот только - наступит ли Вам от этого моего сообщения счастье ... ;-) )))

Продолжу, пока никто не мешает ;-)
Андрей, я не понимаю Ваш тезис: "нейронная сеть моделирует функцию"!
По-моему так - она АППРОКСИМИРУЕТ подаваемые ей в при обучении ДИСКРЕТНЫЕ значени-примеры ...
А после окончания обучения - она ПРЕДСТАВЛЯЕТ СОБОЙ конкретную функцию, а вовсе не "моделирует"!

Андрей Плахов
Я действительно применил плохой термин. Сеть не "моделирует ", а аппроксимирует. И, соответственно, вопрос звучит как:

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

Иван FXS
Сорри за занудство, но она не функцию аппроксимирует, а - значения (=обучающие ПРИМЕРЫ) ...

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

Иван FXS
Андрей, мы с Вами одинаково понимаем смысл слова "аппроксимация"?
Что означает утверждение: (нечто) аппроксимирует функцию F(x)=2*x+1 ?

Андрей Плахов
>Арифметические Нейронные Сети - в легкую РЕАЛИЗУЮТ

Дык, обычные тоже :) Речь-то не о том! Речь о том, насколько легко в рамках парадигмы ИНС (или, соответственно, АНС) выразить понятие инварианта (в том смысле выразить, в каком я поставил задачу для "сдвигов"). Вот я пока не умею ни там, ни там.

> Андрей, мы с Вами одинаково понимаем смысл слова "аппроксимация"? Ох, придется строгость, похоже, включать на всю мощность.

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

Теорема ничего не говорит о том, как именно найти такую сеть (как искать ее структуру, обучать, подбирать веса и т.д.), сколько понадобится обучающих примеров и т.п. Она только о том, что такая сеть есть в принципе.

Иван, Вам понятно теперь, что я понимаю под "аппроксимацией "? И что мне вообще хотелось бы от инвариантов?..
Это действительно важно, мне кажется, неумение работать с инвариантами и есть тот самый "камень преткновения " для современных парадигм ИИ...

Иван FXS
О, язык мой - враг мой!!
Вы уверены, что "рамки парадигмы ИНС" предназначены для "выражения понятий", - "понятия инварианта", например?
Другими словами: осмыслена ли вообще эта "задача" - выразить понятие инварианта парадигме ИНС?

Вы согласны, что "парадигма ИНС" может быть сформулирована так: тренируем (=выбираем и настраиваем) сеть на одних примерах и после этого - пытаемся использовать на других.

Да, о теореме аппроксимации я все понял. Однако, точно такие же "Теоремы аппроксимации" верны ведь и для рядов Тейлора, и для рядов Фурье ... то есть СПЕЦИФИКИ инс она не ухватывает! Той, которая как раз заключена в
Кстати, БАНАЛЬНАЯ функция F(x)=2*x+1, - она ведь НЕОГРАНИЧЕНА, правда?

Андрей Плахов
>осмыслена ли вообще эта "задача " -
>выразить понятие инварианта парадигме ИНС

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

1) Для любой ограниченной кусочно-непрерывной функции, инвариантной относительно данной группы преобразований, и для сколь угодно малого числа epsilon > 0, в множестве ... найдется такая сеть и такие веса связей для нее, что значения выхода сети отличаются от значений функции не больше, чем на epsilon, на всем множестве входов.
2) Для любой сети множества ее выход инвариантен относительно данной группы преобразований

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

Иван FXS
Мне кажется, что этой теоремой (ее формулировкой) Вы "выразили понятие инварианта " прежде всего в парадигме ЧЕРНЫХ ЯЩИКОВ, имеющих вход и выход, и МГНОВЕННО (в смысле - ВНЕ ВРЕМЕНИ) преобразующих сигнал (а точнее - ЗНАЧЕНИЯ), подаваемый на "вход " (а точнее - ИМЕЮЩИЙСЯ на входе) в сигнал, появляющийся (имеющийся) на "выходе ".
А ИНС здесь - сбоку-припеку, обсуждаемое Вами свойство "черного ящика " конкретно с ИНС никак ведь не связано ...

Андрей Плахов
Согласен, речь об ИНС зашла только потому, что supremum желает "существовать" именно на них.

Я с радостью приму любой "черный ящик", который будет уметь моделировать инварианты. (думаю, теперь, когда все строго определено, слово "моделировать" уже можно использовать ;)

Иван FXS
Что значит примете - в подарок? ;-)))
Вопрос ведь не в том - "существует - не существует", а в том - как СОЗДАВАТЬ (причем, в условиях ОГРАНИЧЕННЫХ РЕСУРСОВ) ...

Андрей Плахов
В подарок приму просто с радостью )))

Пока что вопрос даже в "существует". По-моему, рано "создавать", пока неизвестно, а существует ли вообще.

Кроме того, если мы научимся строить множество "ящиков", реализующих данную инвариантность, то искать среди них нужный сможем и всеми уже отработанными методами - градиентный спуск aka back propagation, ГП, перебор и т.п.

Иван FXS
О какой инвариантности идет речь?
В чем - в контексте данного обсуждения - разница между "искомый" ("искать среди них") и "реализующий данную инвариантность"?
А плодить ... сорри, - строить, - "ящики" очень легко. Например, методом Монте-Карло: случайным пораждением ящиков случайной структуры со случайными параметрами.
Вам - сколько прислать: миллион ящиков или миллиард? ;-)

Андрей Плахов
>О какой инвариантности идет речь?

О любой. :)
В качестве жизненных примеров групп инвариантных преобразований я предлагал
1) группу параллельных переносов, если вход организован как двумерная матрица
2) группу перестановок части входов, если все входы из этой части "равноправны ".

smollett
О чем речь, можно сформулировать вкратце?

Андрей Плахов
Мы конструктивно ругаем нейросети (ИНС) и арифметические сети (АНС). Вернее, ругаю я, а Иван выясняет, за что :), и почему это конструктивно :))

Есть вот такая теорема об аппроксимации, очень нравится сторонникам ИНС:

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

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

Я бы хотел научиться находить множества конструкций, для которых верна аналогичные
теоремы, вот какие:

Теорема инвариантной аппроксимации
1) Для любой ограниченной кусочно-непрерывной функции, инвариантной относительно данной группы преобразований, и для сколь угодно малого числа epsilon > 0, в множестве ... найдется такая сеть и такие веса связей для нее, что значения выхода сети отличаются от значений функции не больше, чем на epsilon, на всем множестве входов.
2) Для любой сети множества ее выход инвариантен относительно данной группы преобразований.

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

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

Может, мое изложение слишком громоздкое и "наукообразное", но идея-то простая.

Где бы нам взять стадо черных ящиков, которому при обучении не нужно было в каждом примере повторять, что 2*3 = 3*2 = 6; 7*8 = 8*7 = 56; ... а можно было сразу сказать A*B = B*A; и потом уже учить: 2*3 = 6; 7*8 = 56; ...

ИНС - не такие :(
АНС - не такие :((
Традиционные алгоритмы - такие, но они не стадо черных ящиков :))

Функи мои любимые - не такие. Но, может, их можно сделать такими?..

Иван FXS
Ваша инвариантность - это ОБЩАЯ ИДЕЯ, исчерпывающе формализовать которую не так уж и легко!
Смотрите: чтобы обсуждать инвариантность по сдвигу (и всего-то на 1 ячейку!), Вам пришлось потребовать, чтобы в исходном "сигнале" - "полоса значений", выходящая за границу "кадра" при таком сдвиге - имела нулевые значения сигнала ...

Андрей Плахов
>навскидку - аж целых два варианта
Здорово! Я, собственно, и не хотел сказать, что задача в такой постановке так уж сложна... Я предложил обсудить это, чтобы после мы могли перейти к нечетким инвариантам, и чтобы в будущем при обсуждении идей мы принимали во внимание возможность реализации идей инвариантов.

>забраковывать все те из них, которые не обладают данной инвариантностью

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

>в качестве выходного сигнала -
>использовать СРЕДНЕЕ значение (или -
>другую инвариантно-однородную функцию)
>сигналов
Это уже интереснее, но сомнение в этом случае вызывает пункт 1 теоремы. Действительно ли любую ф-ию можно таким образом представить?.. Может быть, не среднее, а что-то другое?...

>чтобы обсуждать инвариантность-по-сдвигу >, Вам
>пришлось потребовать, чтобы...

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

Комбинатор
Видимо, я чего-то недопонимаю. Если то, что A*B= B*A известно априори, то что нам мешает вначале привести функцию, подаваемую на вход ЧЯ к стандартному виду, учитывающему все известные нам инварианты (в данном случае, например, наименьшее число всегда должно стоять первым), а потом уже подавать её на вход ЧЯ? Несколько сложнее, (но и потенциально много интереснее), мне кажется, добиться того, что бы получив в обучающей выборке достаточно много примеров, ЧЯ догадался бы САМ, что А*B= B*A, A+B = B+A, A-B = -(B-A) и т.д., и стал бы использовать эти свойства для получения ответов на тех входных векторах, которых в принципе не было в обучающей выборке.

Андрей Плахов
>Если то, что A*B= B*A известно априори,
>то что нам мешает

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

>Несколько сложнее, (но и потенциально
>много интереснее), мне кажется, добиться
>того, что бы получив в обучающей выборке
>достаточно много примеров, ЧЯ догадался
>бы САМ

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

Иван FXS
А ведь и правда, Андрей, это - решение Вашей проблемы!!!
Например, если хотим инвариантность к сдвигам, то - в качестве предобработки входного сигнала, - находим "центр тяжести " входного паттерна и сдвигаем паттерн так, чтобы этот центр тяжести находился в центральной точке кадра!

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

Андрей Плахов
Иван, это очень плохое решение %)))

Это решение в стиле "а давайте все сделаем руками" :)

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

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

Заметим, "приведение входа" - это не единственный метод... Мне не меньше нравится то, что Вы предлагали ("размазывание ответственности за выход по копиям").

Василий Семи-Булатов
> Несколько сложнее, (но и потенциально много интереснее), мне кажется, добиться того, что бы получив в обучающей выборке достаточно много примеров, ЧЯ догадался бы САМ, что А*B= B*A, A+B = B+A, A-B = -(B-A) и т.д.

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

То есть, рано или поздно значку "*" из обучающей выборки будет сопоставлена функция умножения (если её нет среди исходных - не беда, она будет создана автоматически), "+" - сложение, и т.д., что, в общем-то, и требовалось.

Иван FXS
Хм, а разве из формального описания (=определения) инварианта - не следует ВСЕГДА однозначно то, каков должен (может?) быть АЛГОРИТМ "НОРМАЛИЗАЦИИ" исследуемого объекта по этому инварианту:
перемещение некоторой "имманентной" точки паттерна в некоторую "удобно-выбранную" точку кадра - нормализация по перемещению,
упорядочивание по какому-нибудь "удобному " признаку - нормализация по перемешиванию ... и т.д.

Андрей Плахов
Может, и следует. Даже скорее всего. Я ставлю вопрос не "философский" (существует ли), а практический: в каком виде должно даваться это описание? Как именно построить обобщенный алгоритм нормализации? Что, неужели перемешивание и сдвиг - это все на практике встречащиеся инварианты? Нет, конечно! Группа движений плоскости (в т.ч. повороты), симметричность при замене (вход = -вход), периодичность функции (вход = вход+Т), все это тоже вполне практические инварианты. Да, и к ним можно легко найти соответствующие преобразования. А автоматически? Как ты говоришь, "извините за занудство" :)

> "размазывание ответственности за выход
>по копиям" - ок, но это ведь намного более трудоемко!

Да, к сожалению, но и более универсально.

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

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

Я хочу понять, есть ли парадигма, умеющая их использовать (кроме "парадигмы" "давайте использовать их вручную").

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

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

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

Первый этап не так страшен, как кажется - по идее, сетка Кохонена должна справится. Она всего-то должна переставить входы на выходы так, чтобы учесть инвариантность.

Количество входов аппроксиматора при этом существенно сократится, и он будет заниматься собственно аппроксимацией, например, синуса от -pi до pi, а не лезть в загугольщину.

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

Иван FXS
Андрей Finder Плахов 28 января, 13:04 Например, если выход обозначить f, и входы х и y, то тождество f(y,x) = f(x,y) означает инвариантность выхода относительно перестановки входов.
" " " " " " " " " " " " " " " " " " " " " " "
Подождите, у Вас f - это сеть (=черный ящик) или функция, которую она (он) аппроксимирует?

Если ФУНКЦИЯ инвариантна, а сеть ее аппроксимирует, значит - и сеть тоже получится инвариантной ... То есть пункт 2 следует автоматически из пункта 1!
НП, Иван FXS.

Андрей Плахов
Иван FXS, да нет, не следует же!
Пункт 1 означает, что искомая функция заведомо представляется черным ящиком из данного набора.

А пункт 2 означает, что в данном наборе нет черных ящиков, чьи выходы были бы неинвариантны. Поэтому и поиск не ведется по заведомо неверным решениям.

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

Наглый Змий
>Кажется. И? Как же будет происходить "учет "? Что-то я не понимаю, причем тут сеть Кохонена. Она будет всего лишь кластеризовать входы по евклидову расстоянию, а нам совсем не это нужно...

Я вот как это представляю. Есть два устройства - "кластеризатор " и "апроксиматор ", задача которых - найти аппроксимацию f(g(X)) наблюдаемой функции f^(X).
Задача кластеризатора - искать такие Хi, для которых f(X) равны, и собирать их в кластеры, которым соответствует выход g.
Понятно, что это не чисто кохонен, но работает по тем же принципам.

2All
Кстати, а действительно ли инвариантов (имеющих практическое значение) настолько много, что их нельзя априорно учесть?

Андрей Плахов
"Это справедливо лишь в том случае, если на входе мы имеем белый шум. Но реальные данные, с которыми мы работаем, всегда структурированы, что позволяет избежать экспоненциального роста дерева перебора за счёт учёта тех самых инвариантов."

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

Андрей Плахов
Кстати, а действительно ли инвариантов (имеющих практическое значение) настолько много, что их нельзя априорно учесть?

Это хороший вопрос.
Насчет себя скажу, что мне на практике встречались следующие: топологические инварианты входа; геометрические инварианты (если вход - набор координат точек на плоскости, то повороты, симметрии, растяжения и т.п.); однородность по группам входов (например, если пары входов (1,2), (3,4), (5,6) можно менять местами как угодно); инвариантность при замене X = const - X; инвариантность при замене X = X + T, T - период;
и, видимо, это всё...

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

Inex
Кстати, а действительно ли инвариантов (имеющих практическое значение) настолько много, что их нельзя априорно учесть?

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

ЗЫ поэтому рассматривать однородные системы (такие, например, как сети Кохонена) для решения интеллектуальных задач крайне нерационально

Андрей Плахов
2Inex
Поддерживаю

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

Inex
Согласен. Лениво было подробно писать, я имел в виду, что инварианты нижнего уровня можно зашить аппаратно (вопрос был в том, насколько много инвариантов вообще) и создавать т.н. объектно-независимые алгоритмы. А проблемы возникают на более высоких уровнях, все возможные инварианты которых предусмотреть нельзя. Причем такое разделение наступает, на удивление, весьма резко.

Андрей Плахов
Причем такое разделение наступает, на удивление, весьма резко.

Не понял этой фразы. Какое разделение? На кого наступает?

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

Андрей Плахов
Со своей стороны я бы предложил программу "информация о функции = выдерживаемые четкие, нестрогие и нечеткие инварианты". Кроме того, возможно, понадобится понятие "свойства" функции. А именно, если задана функция f:A- >B, то свойством называется пара (g:AxA->{0,1}, h:BxB->{0,1}) такая, что если g(a1,a2)=1, то и h(f(a1),f(a2))=1. Инварианты - частный случай "свойств".

Андрей Плахов
Другие примеры:
Если g(a1,a2) = a1 >a2, h(b1,b2) = b1 >b2, то такая пара выражает свойство "возрастать ". Если h(a1,a2) = |b1-b2|
И главный вопрос. Как строить "произвольные ф-ии с заданными свойствами "?

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

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

Комбинатор
Я понимаю это так. Вначале ищутся самые очевидные инварианты "нижнего уровня ". После того, как они найдены, в правила мутаций вносятся ограничения, запрещающие мутации, изменяющие инварианты. Другими словами, это означает, что поиск идёт уже в пространстве меньшей размерности. На следующем этапе ищутся уже "инварианты инвариантов ". И всё повторяется с начала... Именно такая тактика позволяет избежать комбинаторного взрыва. Впрочем, об этом, я, кажется уже писал. Да и у Турчина об этом много написано.

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

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

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

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