Теория алгоритмов

[Mihaylo]

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

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

[Mihaylo]

Mihaylo в сообщении #1449430 писал(а):

$I(S,R,T) = \log N(S,R,T)$, где $S$ и $R$ - состояние и результат работы алгоритма, $T$ - задача.
Совершенно бесполезное определение

Ловлю себя на мысли, что $R$ надо убрать из определения энтропии. Нужно оставить только те данные, которые интерпретируются за единичное $O(1)$ время - состояние программы, счетчики циклов и т.п. Неопределенными должны быть различные массивы размерности $O(n)$, $O(\log n)$ и др., являющиеся результатами промежуточных вычислений, которые я обозначил $R$. То есть данные на бесконечной ленте в машине Тьюринга должны считаться неопределенными.
Иначе можно было бы предъявить модифицированный алгоритм, который помимо прочего копирует входные данные частично или целиком в промежуточный результат $R$. Однако, по практическим представлениям, это на энтропию не должно влиять.

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

[arseniiv]

Mihaylo в сообщении #1449531 писал(а):

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

Ещё и вероятностные распределения тогда задавать надо. И надо будет как-то влияние выбора распределения потом учесть, чтобы такая энтропия не характеризовала в первую очередь его и лишь в последнюю алгоритм.

[Mihaylo]

arseniiv в сообщении #1449562 писал(а):

Ещё и вероятностные распределения тогда задавать надо.

Вероятностные распределения входных данных?

-- 30.03.2020, 19:29 --

Mihaylo в сообщении #1449182 писал(а):

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

Сейчас посетила мысль, что любой алгоритм, который действительно выполняет задачу и останавливается, то значит он выполняет задачу. При подсчете энтропии четкое определение задачи очень и очень важно, так как бывают очень похожие внешне (псевдоидентичные) задачи, но на деле они строго говоря разные. Например, оптимизационная задача предполагает поиск минимального значения. Но это не поиск наименьшего значения! Важно в оптимизационных задачах определить критерий подходящего локального минимума. Бывают алгоритмы, находящие локальные минимумы по разным критериям, соответственно и задачи они решают разные, хотя тело алгоритма может совпадать на 99%... Поэтому я подчеркиваю важность $T$ при расчете энтропии.

[arseniiv]

Mihaylo в сообщении #1449573 писал(а):

Вероятностные распределения входных данных?

Именно. А то вдруг вход — произвольное натуральное число, ну или если числа кажутся ненатуральными, произвольной длины последовательность байтов.

[_Swetlana]

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

Разбиение задачи на подзадачи можно описать формально, используя модель "система продукций". Далее излагаю по книге Нильса Нильсона "Принципы искусственного интеллекта".
Система продукций имеет следующие основные элементы: глобальную базу данных, правила продукции и систему управления.
Глобальная база данных — это описание состояния задачи. Правила продукции применяются к глобальной базе данных и изменяют ее. Для каждого правила имеются предварительное условие, которому глобальная база данных удовлетворяет, либо нет. Если предварительное условие выполняется, то правило может быть применено. Выбор применимого правила осуществляет система управления. Также система управления прекращает вычисления, когда глобальная база данных удовлетворяет терминальному (целевому) условию.

Задача - система продукций.
Задача, которая "бьётся" на подзадачи (которые можно решать независимо друг от друга) - разложимая система продукций:
Системы продукций, глобальные базы данных и терминальные условия которых допускают декомпозицию, называются разложимыми.
Графическим представлением (моделью) разложимой системы продукций является И-ИЛИ граф. Вершина типа «ИЛИ»: для решения этой задачи достаточно ре-шить только одну из ее подзадач-преемников. Вершина типа «И»: для решения этой задачи нужно решить все ее подзадачи. Ну и далее по тексту
На рисунке - вершина типа "И", при обходе графа из вершины-родителя переходим сразу во всех её сыновей.

[Mihaylo]

В развитие подтемы, начатой моим же сообщением:

Mihaylo в сообщении #1444907 писал(а):

Ну ещё вот такой мыслительный эксперимент: есть задача, но не известен алгоритм решения. Эвристическим методом найден один шаг алгоритма, который что-то выполняет с условием задачи, то есть формально этот шаг корректен. Этот шаг решает некую подзадачу.
Мы имеем две задачи, одна из которых претендует быть подзадачей другой. Как проверить, не предъявляя окончательный алгоритм большой задачи?

Возможно вам придется прочитать сообщения всей этой темы, чтобы вспомнить, о чем речь.

Продолжение темы:
В машинном обучении (machine learning) я открыл для себя некий подход к обучению, который работает в том случае, когда нет данных для обучения. Этот подход называется semi-supervised-learning. Суть: имеется неразмеченный датасет, для этого датасета могут генерироваться положительные и отрицательные примеры. Положительные примеры характеризуются тем, что такие примеры заведомо относятся к тому же классу (похожи) на примеры из исходного датасета. Отрицательные примеры, напротив, заведомо не принадлежат классу примеров из датасета.
На практике в компьютерном зрении (CV) используется генерация положительных примеров: берется картинка кошки, масштабируется, обрезается, корректируются цвета всех пикселей. В итоге получается другая картинка, но той же кошки, при этом картинка по-прежнему остается картинкой кошки. Гуглить алгоритм Simclr.
На практике в обработке естественного языка (NLP) используется генерация отрицательных примеров: генерируется набор случайных слов - это становится анти-примером того, как должно формироваться предложение. Подход называется Noise-contrastive estimation (NCE).

Это все к тому, что всегда имеются варианты, когда нет достаточного количества информации. И все это работает даже когда датасет сильно разбалансирован (отсутствует информация об одном из классов - one-class classification). Грубо говоря, вы занимаетесь исследованиями и нет никакой информации, что вы идете по правильному или неправильному пути, но есть чутье, что принятое направление все-таки верное нежели другое. Это чувство почти наверняка испытывали в свое время Ньютон и Гаусс.

Я хотел бы рассмотреть, как это связано с генерацией алгоритмов. То есть, как я ставил задачу в самом первом посте темы: есть задача, но неизвестен алгоритм. Как его сгенерировать? Но теперь с учетом подходов машинного обучения.

-- 13.12.2021, 01:05 --

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

[realeugene]

_Swetlana в сообщении #1525194 писал(а):

правила продукции

Это что-то специфичное для пролога?

[mihaild]

Mihaylo в сообщении #1542668 писал(а):

На практике в компьютерном зрении (CV) используется генерация положительных примеров: берется картинка кошки, масштабируется, обрезается, корректируются цвета всех пикселей.

Это не semi-supervised learning, это data augmentation. Отличие в том, что новые объекты мы генерируем сами, а не берем из неразмеченных.

Mihaylo в сообщении #1542668 писал(а):

На практике в обработке естественного языка (NLP) используется генерация отрицательных примеров

И это тоже не semi-supervised learning.

Semi-supervised learning - это именно когда у нас есть объекты из того же распределения, но мы не знаем для них ответа.

[Mihaylo]

Может будет точнее термин Self-supervised learning?

[_Swetlana]

realeugene в сообщении #1542672 писал(а):

_Swetlana в сообщении #1525194 писал(а):

правила продукции

Это что-то специфичное для пролога?

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

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