Обсудив предыдущий список задач на форуме, я пришел к выводу, что задача номер 2 сформулирована недостаточно строго, а задача номер 1 «без звездочки» не очень-то полезна, т.к. ее обсуждение превращается в обсуждение деталей реализации самой простой стратегии.
Пока что я, тем не менее, не буду отменять дискуссию по их поводу, а вместо этого сделаю некоторые уточнения и добавлю еще одну, возможно, более перспективную, задачу.
Задача 3. Требуется построить пару (А, VM), где VM – некоторая «виртуальная машина», а А – некоторый алгоритм, генерирующий управляющие последовательности (программы) для этой VM, решающие следующую задачу:
Дано достаточно много пар примеров Xi → Yi и число ε > 0.
На вход А подаются все эти пары, на выходе мы должны получить управляющую последовательность для VM, имеющую минимальную длину, такую, что под ее управлением |VM(Xi) - Yi| < ε.
При этом:
1) VM должна быть достаточно «мощной», то есть, как минимум, уметь производить любое кусочно-гладкое преобразование с точностью до сколь угодно малой константы.
2) VM должна быть «аддитивной по суперпозиции», то есть, если мы знаем, что существует управляющая последовательность длины N1, реализующая ф-ию F1, и управляющая последовательность длины N2, реализующая ф-ию F2, то должна существовать и управляющая последовательность длины не более N1+N2+const, реализующая ф-ию F1◦F2 («F1, примененная к F2»).
Таким требованиям удовлетворяют, например, все алгоритмически полные языки программирования. Можно также описать 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 - число пар. Разрешается, чтобы равенства выполнялись не точно, а с некоторой наперед заданной точностью.