Обсудив предыдущий список задач на форуме, я пришел к выводу, что задача номер 2 сформулирована недостаточно строго, а задача номер 1 «без звездочки» не очень-то полезна, т.к. ее обсуждение превращается в обсуждение деталей реализации самой простой стратегии.

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

Задача 3. Требуется построить пару (А, VM), где VM – некоторая «виртуальная машина», а А – некоторый алгоритм, генерирующий управляющие последовательности (программы) для этой VM, решающие следующую задачу:

            Дано достаточно много пар примеров X_i → Y_i и число ε > 0.

            На вход А подаются все эти пары, на выходе мы должны получить управляющую последовательность для VM, имеющую минимальную длину, такую, что под ее управлением |VM(X_i) - Y_i| < ε.

            При этом:

1) VM должна быть достаточно «мощной», то есть, как минимум, уметь производить любое кусочно-гладкое преобразование с точностью до сколь угодно малой константы.

2) VM должна быть «аддитивной по суперпозиции», то есть, если мы знаем, что существует управляющая последовательность длины N₁, реализующая ф-ию F₁, и управляющая последовательность длины N₂, реализующая ф-ию F₂, то должна существовать и управляющая последовательность длины не более N₁+N₂+const, реализующая ф-ию F₁◦F₂ («F₁, примененная к F₂»).

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

3) Алгоритм А должен иметь полиномиальную сложность как по длине управляющей последовательности, так и по количеству пар примеров. Порядок полинома и будет мерой качества решения этой задачи.

Пояснение к задачам 1 и 1*. Предполагается, что человек никак не участвует в решении задачи. К примеру, в алгоритме участвует нейронная сеть, то ее архитектура (количество слоев, топология связей, обучающее правило и т.п.) должна выбираться автоматически. Функция F является кусочно-гладкой. На вид функции F нельзя накладывать никаких других ограничений (единственность локального максимума по Y при фиксированном Х, гладкость по Y при фиксированном Х и т.п). Решающий алгоритм может работать более оптимально в указанных случаях, но он должен работать и в тех случаях, когда эти ограничения не выполнены.

Пояснение к задаче 2. Повторю здесь пример, который я показал на форуме:

Пусть даны пары

1 → 2

1 → 17

1 → -6

3 → 8

3 → 4

15 → -90

15 → 16

Действительно, несложно определить, что в данном случае можно добиться выполнения не более, чем трех равенств. Однако это можно сделать многими способами. Но если для «реализации» выбраны равенства 1 → 2, 3 → 4, 15 → 16, то реализующая их функция

(Х → Х+1) оказывается самой гладкой. Именно она должна быть найдена.

Чтобы исключить «глупые» переборные алгоритмы, стоит поставить дополнительное требование: итоговый алгоритм должен иметь сложность P(N), P – некоторый полином, N - число пар. Разрешается, чтобы равенства выполнялись не точно, а с некоторой наперед заданной точностью.