GotAI.NET

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

 

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

 Все темы | Новая тема Стр.1 (4)След. > >>   Поиск:  
 Автор Тема: Теория Сложности
Львович
Сообщений: 303
Теория Сложности
Добавлено: 29 сен 08 14:20
Решил вынести на отдельно обсуждение понятие "Сложность". Пока отдельные мысли на эту тему:
0) Понятие сложности нужно для сравнения разных задач и оценки ресурсов на их решение.
1) Сложность это интегральное свойство любого объекта в рамках некоторого контекста.
2) Контекст в данном случае - априорно известная информация об объекте.
3) Сложность это минимальное среднестатистическое количество вопросов с ответами ДА/НЕТ после которых становится известна вся информация об объекте.
Пример:
Контекст - "равновероятное целое число от 0 до 15"
Количество необходимых вопросов - 4
Сложность - 4
4) Контекстом также является распределение вероятности любых параметров объекта. Если распределение вероятности не задается, то для конечного количества значений принимается равновероятное рапределение.
5) Контекст может предполагать конечное или бесконечное количество объектов или значений для свойств объекта.
6) Для бесконечного количества значений (объектов) должно обязательно задаваться распределение вероятности так, чтобы . Одним из простейших распределений является

Пример:
Контекст - "целое неотрицательное число с вероятностью распределения (1)"
Объект - число 8.
Вопросы (по методу половинного деления с учетом вероятности):
это число 1?
это число 2?
...
Количество необходимых вопросов -8.
Сложность - 8.

Пример:
Контекст - "граф переходов с n вершинами и m переходами из каждой вершины"
Количество вопросов (сложность):

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

7) Сложность может быть введена и определена и для непрерывных свойств. Но тогда в контексте должна быть определена погрешность определения этого свойства. И конечно же плотность распределения вероятности особенно для бесконечных значений.

Напомню, что это только мысли...
Может быть я изобретаю велосипед. Любая конструктивная информация приветствуется.
[Ответ][Цитата]
гость
89.208.11.*
На: Теория Сложности
Добавлено: 29 сен 08 14:42
в тексте применены математические символы:
нечетал кг/ам
[Ответ][Цитата]
гость
195.93.160.*
На: Теория Сложности
Добавлено: 29 сен 08 15:33
http://ru.wikipedia.org/wiki/Теория_сложности_вычислений
[Ответ][Цитата]
гость
195.93.160.*
На: Теория Сложности
Добавлено: 29 сен 08 15:35
http://www.dlutskiy.com/theory/systems4.htm
Теория сложности М. Джексон
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Теория Сложности
Добавлено: 29 сен 08 16:11
Двусмысленное понятие сложность я бы разделил на два понятия:
- комплексность, как совокупность связей системы задачи (именно в этом смысле развивается контекст Львовича), в идеале независящая от наблюдателя;
- трудность, как мера необходимых затрат для решения конкретной задачи, конкретным решателем, в конкретных условиях (контексте).

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

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

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

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

Цитата:
Автор: Львович
Сложность системы, состоящей из нескольких невзаимодействующих подсистем, равна сумме сложностей этих систем
В общем можно с этим согласиться, только нужно уточнить что понятие "сумма систем" тут не однозначное. Разные системы могут быть "суммированны" разными связями. Например, завод и магазин - отдельные системы. Если мы их объединим какой-то одной связью (например завод поставляет чашки в магазин, а магазин возвращает заводу деньги от продаж) - то это одна сумма. А если мы, например, директорами этих предприятий назначим двух родных братьев - то это будет уже совсем другая сумма с другими взаимодействиями и последствиями
[Ответ][Цитата]
Virtual_Graph
Сообщений: 594
На: Теория Сложности
Добавлено: 30 сен 08 0:53
Сложность - понятие относительное и субъективное. Зависит от того, насколько точно модель объекта отражает ту или иную сторону реального объекта. Чем больше расхождение, тем "сложнее" объект.

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

Поэтому сложность "живет" не в самом объекте, а в голове исследователя (если это конечно не программная модель или какая-то иная), но которая, в конечном итоге, все равно разрабатывается человеком.
Примечание: речь не идет о ТВС и прочих математических теориях
[Ответ][Цитата]
гость
89.208.11.*
На: Теория Сложности
Добавлено: 30 сен 08 11:04
"сложность-не объективная характеристика",

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


после этого ложного утверждения надо ставить сразу крест на человеке, он бездарен по определению.
сложность, да и вообще всякое понятие, понятие системное, и там, где это понятие определено, у него есть своя сложность ОБЪЕКТИВНАЯ для этой системы. Если система субъект, то сложность будет не объективной, естесственно, НО, если вы берете в качестве системы не субъект, а реальность, то в ней понятие сложности уже ОБЪЕКТИВНО.
[Ответ][Цитата]
гость
89.208.11.*
На: Теория Сложности
Добавлено: 30 сен 08 12:08
"НО, если вы берете в качестве системы не субъект, а реальность, то в ней понятие сложности уже ОБЪЕКТИВНО." причем само по себе, независимо от вас. она просто ЕСТЬ, потому что есть сам объект в реальности, и если бы он не обладал какой то объективной сложностью, то его ВООБЩЕ БЫ не могло существовать. В природе есть ее СОБСТВЕННЫЕ абсолютные еденицы измерения и она их использует для своего СОБСТВЕННОГО корректного функционирования как системы, независимо от того, знаете вы об этом что то или нет. У вас есть вопросы к корректности выполнения закона ома в природе? Нет, тогда примите как данность тот факт, что объект и его сложность, понятия ОБЪЕКТИВНЫЕ и безусловные, и не ВПАРИВАЙТЕ ни себе ни народу бред о том, что сложность понятие субъективное. Оно субъективное только в вашей голове, относительно реальности, которую мы принимаем за абсолютную истину по умолчанию.

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

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


Полученное вами значение сложности для таких объектов, будет ЛОГИЧЕСКИ считаться объективным несмотря на то, что вы субъект. Просто ваше субъективное мнение будет СОВПАДАТЬ с объективной данностью.

Всякое иное конструирование модели мира и последующий расчет сложности объекта, будет СУБЪЕКТИВНОЙ, хотя вероятность ее объективности сохраняется.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Теория Сложности
Добавлено: 30 сен 08 15:04
а я бы для начала определил о сложности чего идет речь.
и только после этого можно вообще обсуждать эту самую сложность.
просто говорить о сложности объекта как такового... бессмысленно.
О комплексности наверное можно, основываясь на каком-то базисе элементарных единиц, но говорить о сложности... как мне кажется, надо всегда в связи с каким-то процессом. Да конечно, эти два понятия имеют связь, так как чем выше комплексность, тем сложнее для процесса обработки становится этот объект. Но кстати я не согласен, что это линейная зависимость, так что о сумме не стоит говорить.
просто для иллюстрации:
1. Сложность задачи в ТВС рассматривается в связи с процессом решения этой задачи.
2. Сложность функции, к примеру, может рассматриваться относительно процесса ее аппроксимации. Причем, я думаю, что здесь будет играть роль еще и сам способ этой аппроксимации (Возможно что в конце концов, сложности по всем способам окажутся эквивалентными, но зря утверждать не буду). Так например, для ИНС можно говорить что функция для обучения сложнее, чем требуется больше базисных функций для ее представления в теореме Калмогорова (забыл как эта форма называется). Или скажем, если мы говорим об аппроксимации полиномом, то... чем выше степень полинома, для аппроксимации, тем сложнее функция. Ну и так для каждого способа можно говорить о своем базисе элементарных составляющих и относительно их, о сложности какого-то процесса взаимодействия с этим объектом.
3. Сложность окружающей среды, так же подходит под такое рассмотрение.
Формально среда в конце концов представляется набором объектов и правил над ними. Поэтому и надо рассматривать сложность именно относительно этих множеств. От сюда и всем известные свойства среды: динамичность, доступность, детерминированность и т.д.
Все это различия в кол-ве правил, которые вкупе с правилами поставленной задачи, определяют формально то, что и требуется решать агенту. Кстати, вот вам и пример, когда "сложение" задачи которую агент должен решить, со средой в которой он должен это решать, не является (чаще всего) суммой сложности двух этих объектов.
[Ответ][Цитата]
Львович
Сообщений: 303
На: Теория Сложности
Добавлено: 01 окт 08 13:21
Цитата:
Virtual_Graph:
Поэтому сложность - не есть объективная (интегральная) характеристика объекта. Это - характеристика модели объекта.

Замечание справедливо. Конечно же речь идет о моделях. А если еще точнее, то я хочу определить это понятие для сред (задач), в которых действуют агенты. Это даст возможность сравнивать разные среды (задачи) и определять эффективность алгоритмов агентов (коэффициент интеллекта) независимо от вида конкретной задачи.
Кроме того это поможет отделить априорные знания агента от приобретенных в процессе обучения.
Цитата:
89.208.11.*:
сложность ВСЯКОГО объекта системы расчитывается по количеству бит в неизбыточном алгоритме

Логично, если объекты описываются алгоритмами. Только любой алгоритм предполагает наличие базовых инструкций, которые в данном случае должны быть отнесены к контексту.
[Ответ][Цитата]
гость
195.93.160.*
На: Теория Сложности
Добавлено: 01 окт 08 13:43
Цитата:
Кстати, вот вам и пример, когда "сложение" задачи которую агент должен решить, со средой в которой он должен это решать, не является (чаще всего) суммой сложности двух этих объектов.


И где пример?
П.С. Разве решение задачи агентом не подразумевает как контекст решения (сумму условий задачи) состояние среды, при котором данное решение является истинным, работающим, и выведено из правил, которые действуют (истинные) именно для ДАННОГО состояния среды?

Как в таком случае можно говорить об "отнятии" или "сложении" задачи и среды (которая фактически является частью задачи)?
[Ответ][Цитата]
daner
Сообщений: 4593
На: Теория Сложности
Добавлено: 01 окт 08 15:56
Цитата:
Автор: Львович
Логично, если объекты описываются алгоритмами. Только любой алгоритм предполагает наличие базовых инструкций, которые в данном случае должны быть отнесены к контексту.

совершенно не логично.
инструкций для решения задачи А может быть меньше, чем инструкций для решения задачи Б, но при этом действий для решения А потребуется на порядки больше чем действий для решения задачи Б. Биты тут, ни к селу ни к городу.
[Ответ][Цитата]
daner
Сообщений: 4593
На: Теория Сложности
Добавлено: 01 окт 08 16:08
QUOTE Автор: гость 195.93.160.*
Цитата:
И где пример?

среда с заданием -- и есть пример.
Цитата:
П.С. Разве решение задачи агентом не подразумевает как контекст решения (сумму условий задачи) состояние среды, при котором данное решение является истинным, работающим, и выведено из правил, которые действуют (истинные) именно для ДАННОГО состояния среды?

Как в таком случае можно говорить об "отнятии" или "сложении" задачи и среды (которая фактически является частью задачи)?

Здесь просто требуется определить некоторые понятия.

Попробую на примере: Скажем

1. есть задача посика флага на карте. Ну карту ввиде графа можно представить ну и т.д. Думаю формализм этой задачи всем (нормальным собеседникам) знаком.

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

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

Надеюсь спора не вызовет тот факт, что все 3 пункта могут рассматриваться как отдельные объекты. Предлагая называть их 1)Заданием, 2)Окр.Средой и 3)Задачей.

Поэтому очивидно (ну как минимум мне ) что Сложность(Задание) Сложность(Окр.Среда) Сложность(Задача)
[Ответ][Цитата]
гость
195.93.160.*
На: Теория Сложности
Добавлено: 02 окт 08 12:39
1 Допустим мне не знаком. Давайте разговаривать о универсальном формализме, в котором можно представить любую задачу

2. Допустим, есть универсальная среда, которая содержит все возможные среды, которые производят переходы друг в друга по массиву правил

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

Итак, задача заключается в трёх пунктах:
а) Начальное состояние
б) Запланированное состояние
в) Конечное состояние

При этом:

в агента проникают данные , меняя состояние его памяти (Воздействие Окр. Среды);
Агент сам меняет состояние своей собственной памяти;
Интерфейс (место сопряжение Окр. Среды и Агента должен быть таким, чтобы он сам не мог менять свои состояния, а ВСЕ воздействия считались воздействиями Окр. Среды (включая действия Агента);

Таким образом, Заданием будет являться Состояние Агента в произвольный промежуток времени, достигнутое Агентом самостоятельно ИЛИ, если оно не удовлетворяет условию Задания, достигнутое вручную, путём редактирования входящих данных Агента или

путём модификации Окр. Среды, что в дальнейшем, через ИЗВЕСТНЫЙ промежуток времени приведёт к желаемому состоянию Агента.

Задачей, в таком случае будет формальная запись состояния (состояний), которого необходимо достичь, которая должна содержаться :
Или в самом Агенте;
Или в Окр. Среде, а затем путём преобразований или в том же виде попасть в Агента (стать ему известной);
Или образоваться в Агенте после преобразований заложенных данных (сделанных модификаций).
[Ответ][Цитата]
daner
Сообщений: 4593
На: Теория Сложности
Добавлено: 02 окт 08 15:48
QUOTE Автор: гость

Цитата:
1 Допустим мне не знаком. Давайте разговаривать об универсальном формализме, в котором можно представить любую задачу

Ну значит не знаком. у меня сейчас нет желания расписывать столь тривиальные вещи.
Впрочем, это и не важно сейчас. Считайте, что формализм этой задачи есть. Причем он достаточно общего плана и для ИДЕАЛЬНОЙ СРЕДЫ. А вообще, это обыкновенная задача поиска узла в графе. В общем случае, решается через DFS или BFS алгоритм.

Цитата:
2. Допустим, есть универсальная среда, которая содержит все возможные среды, которые производят переходы друг в друга по массиву правил

Вообще, этого предложения не понял. Что это за реды, которые производят переходы...

Цитата:
3. В конце концов:
а) Агент решает (меняет своё внутреннее состояние)
б) Задачу (начальное своё состояние)
в) Находит ответ (конечное состояние(я), которое позволяет передать среде параметры, управляющие ею так, чтобы добиться жалемого (запланированного) состояния(состояний))

Поиск ответа и решение задачи -- это одно и тоже. Не придумывайте какие-то странные термины. И тем более "Задача (начальное своё состояние)" совершенно не верно.
Начальное состояние, это одно из условий задачи. И с чего вы взяли, что решение это только изменение внутреннего состояния? Вы когда нибудь про on-line algorithms слышали? Мы не ограничиваем наши рассуждения в данной теме только планированием. Так что я не согласен, с такими определениями.

Цитата:
Итак, задача заключается в трёх пунктах:
а) Начальное состояние
б) Запланированное состояние
в) Конечное состояние

Причем тут запланированное состояние? Да, в задачу входит начальное и целевое состояние, но это не единственное что в него входит.

Цитата:
При этом:
в агента проникают данные , меняя состояние его памяти (Воздействие Окр. Среды);
Агент сам меняет состояние своей собственной памяти;
Интерфейс (место сопряжение Окр. Среды и Агента должен быть таким, чтобы он сам не мог менять свои состояния, а ВСЕ воздействия считались воздействиями Окр. Среды (включая действия Агента);

А о чем вообще разговор? Причем тут все эти интерфейсы?

Цитата:
Таким образом, Заданием будет являться Состояние Агента в произвольный промежуток времени, достигнутое Агентом самостоятельно ИЛИ, если оно не удовлетворяет условию Задания, достигнутое вручную, путём редактирования входящих данных Агента или
путём модификации Окр. Среды, что в дальнейшем, через ИЗВЕСТНЫЙ промежуток времени приведёт к желаемому состоянию Агента.

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

Цитата:
Задачей, в таком случае будет формальная запись состояния (состояний), которого необходимо достичь, которая должна содержаться :
Или в самом Агенте;
Или в Окр. Среде, а затем путём преобразований или в том же виде попасть в Агента (стать ему известной);
Или образоваться в Агенте после преобразований заложенных данных (сделанных модификаций).

Состояние -- это состояние, а Задача это задача!!!!

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

я бы мог говорить о более конкретных примерах... но я просто не хочу говорить о вещах, которые (возможно) собеседнику будут не понятны. Просто, что бы понять, на одном ли мы языке говорим, несколько вопросов к вам:
Вы знакомы с алгоритмами поиска DFS,BFS,Dijkstra,DJKASTRA,A*,D*? Иначе нет смысла давать примеры на их основе.
[Ответ][Цитата]
 Стр.1 (4): [1]  2  3  4След. > >>