Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Для обсуждения предлагается оригинальный способ машинного обучения. Предполагается способность обучатся на коротких, организованных выборках. Может быть актуально в областях, где нет больших данных.
Центральный вопрос:
При каких условиях конечное число примеров вход-выход позволяет однозначно восстановить программу?
Формализм:
Назовем программируемым устройством четверку {PRG, IN, OUT, COMPUTE}, где PRG, IN и OUT — алфавиты, PRG*, IN*, OUT* — множества слов в них. COMPUTE — функция, сопоставляющая паре слов из PRG и IN слово из OUT
COMPUTE: PRG* × IN* → OUT*. Или:
где program, input, output — слова в PRG*, IN*, OUT* соответственно.
Программируемое устройство COMPUTE является универсальным, если для любой вычислимой функции из IN в OUT существует реализующая ее программа из PRG.
Примером назовем пару (input, output) ∈ {IN* × OUT*} для которой выполнено равенство (I). Выборкой примеров будем называть любое их конечное множество.
Пусть program ∈ PRG*. Будем называть символ α из program значимым, если в области определения программы для него существует пример, для которого равенство (I) может быть нарушено при замене α другим символом из PRG.
Будем говорить, что выборка покрывает программу, если для любого значимого символа программы в этой выборке найдется пример, подтверждающий его значимость.
Теорема:
Для любой программы существует пара выборок — опорная и управляющая — позволяющих идентифицировать эту программу с точностью до эквивалентности.
Доказательство:
Очевидно, для любой программы существует конечная покрывающая выборка, поскольку конечна запись программы. Сформируем такую выборку и назовем опорной. Множество всех программ, покрываемых опорной выборкой перечислимо, поскольку перечислимо множество вообще всех программ вообще. Перенумеруем все программы этого множества. Примеры для управляющей выборки станем подбирать из области определения нашей программы так, чтобы поочередно
исключить все программы с номерами меньше номера искомой программы.
Процесс остановится на программе, эквивалентной искомой, или же на ней
самой. Очевидно, потребуется лишь конечное число примеров для управляющией выборки.
Пояснение:
Конечное число примеров можно обобщить бесконечным, вообще говоря, числом способов. Выводы соответствующих программ будут совпадать только на множестве примеров и различаться за его пределами. Однако, выбором варианта обобщения можно управлять, подбирая контрольные вопросы с известными экзаменатору ответами так, чтобы программы, отличные от искомой, приводили бы к ошибкам и пройти все тесты смогла бы только эквивалентная искомой программа.
По аналогии с учебным процессом покрывающими выборку будем будем называть опорными фактами (для краткости, просто факты), управляющую — контрольными вопросами (тестами). Чтобы однозначно (с точностью до эквивалентности) идентифицировать программу обучающая выборка должна состоять из двух частей — опорной и управляющей.
Обучающая выборка упорядочена и размечена, состоит из уроков. Урок состоит из двух частей — фактов и тестов. Для каждого урока создается своя программа. Программы программы предыдущих уроков используются как строительный материал для последующих в качестве подпрограмм или шаблонов.
Множество примеров не упорядочено и не размечено. Требуется найти минимальную обучающую выборку, необходимую для построения программы, для которой (I) справедливо на всех примерах множества.
Общее решение — полный перебор вариантов нумерации примеров и индуктивный синтез для каждого, с отслеживанием минимума. Отбрасывая проверку вариантов, когда количество фактов превысило уже известный минимум.
Программа известна. Требуется для нее построить обучающую выборку так, чтобы минимизировать сложность обучения для ученика. Учитель не может передать ученику свои знания и умения (программу) непосредственно, он должен создать условия для их самостоятельного приобретения учеником.
Задача учителя для роботов приобретет смысл, когда искусственный интеллект превзойдет человеческий. Важно будет не только найти решение сложной задачи, но понятно его объяснить людям.
©2019 Аверин А.В.
Центральный вопрос:
При каких условиях конечное число примеров вход-выход позволяет однозначно восстановить программу?
Формализм:
Назовем программируемым устройством четверку {PRG, IN, OUT, COMPUTE}, где PRG, IN и OUT — алфавиты, PRG*, IN*, OUT* — множества слов в них. COMPUTE — функция, сопоставляющая паре слов из PRG и IN слово из OUT
COMPUTE: PRG* × IN* → OUT*. Или:
output = COMPUTE(program, input) |
(I) |
где program, input, output — слова в PRG*, IN*, OUT* соответственно.
Программируемое устройство COMPUTE является универсальным, если для любой вычислимой функции из IN в OUT существует реализующая ее программа из PRG.
Примером назовем пару (input, output) ∈ {IN* × OUT*} для которой выполнено равенство (I). Выборкой примеров будем называть любое их конечное множество.
Пусть program ∈ PRG*. Будем называть символ α из program значимым, если в области определения программы для него существует пример, для которого равенство (I) может быть нарушено при замене α другим символом из PRG.
Будем говорить, что выборка покрывает программу, если для любого значимого символа программы в этой выборке найдется пример, подтверждающий его значимость.
Теорема:
Для любой программы существует пара выборок — опорная и управляющая — позволяющих идентифицировать эту программу с точностью до эквивалентности.
Доказательство:
Очевидно, для любой программы существует конечная покрывающая выборка, поскольку конечна запись программы. Сформируем такую выборку и назовем опорной. Множество всех программ, покрываемых опорной выборкой перечислимо, поскольку перечислимо множество вообще всех программ вообще. Перенумеруем все программы этого множества. Примеры для управляющей выборки станем подбирать из области определения нашей программы так, чтобы поочередно
исключить все программы с номерами меньше номера искомой программы.
Процесс остановится на программе, эквивалентной искомой, или же на ней
самой. Очевидно, потребуется лишь конечное число примеров для управляющией выборки.
Пояснение:
Конечное число примеров можно обобщить бесконечным, вообще говоря, числом способов. Выводы соответствующих программ будут совпадать только на множестве примеров и различаться за его пределами. Однако, выбором варианта обобщения можно управлять, подбирая контрольные вопросы с известными экзаменатору ответами так, чтобы программы, отличные от искомой, приводили бы к ошибкам и пройти все тесты смогла бы только эквивалентная искомой программа.
По аналогии с учебным процессом покрывающими выборку будем будем называть опорными фактами (для краткости, просто факты), управляющую — контрольными вопросами (тестами). Чтобы однозначно (с точностью до эквивалентности) идентифицировать программу обучающая выборка должна состоять из двух частей — опорной и управляющей.
Способы управляемого машинного обучения
Организованное обучение («задача ученика»)
Обучающая выборка упорядочена и размечена, состоит из уроков. Урок состоит из двух частей — фактов и тестов. Для каждого урока создается своя программа. Программы программы предыдущих уроков используются как строительный материал для последующих в качестве подпрограмм или шаблонов.
Индуктивное программирование («жизненный опыт»)
Обучающая выборка упорядочена но не размечена, разделения на факты и тесты нет. Задача состоит в последовательной адаптации программы (знания) к каждому новому примеру (опыту). Для этого необходимо поддерживать собственную (внутреннюю) обучающую выборку и модифицировать (пополнять) ее каждый раз когда текущая программа приводит к ошибке.
Предсказательная сила («задача ученого»)
Множество примеров не упорядочено и не размечено. Требуется найти минимальную обучающую выборку, необходимую для построения программы, для которой (I) справедливо на всех примерах множества.
Общее решение — полный перебор вариантов нумерации примеров и индуктивный синтез для каждого, с отслеживанием минимума. Отбрасывая проверку вариантов, когда количество фактов превысило уже известный минимум.
Организация обучения («задача учителя»)
Программа известна. Требуется для нее построить обучающую выборку так, чтобы минимизировать сложность обучения для ученика. Учитель не может передать ученику свои знания и умения (программу) непосредственно, он должен создать условия для их самостоятельного приобретения учеником.
Задача учителя для роботов приобретет смысл, когда искусственный интеллект превзойдет человеческий. Важно будет не только найти решение сложной задачи, но понятно его объяснить людям.
©2019 Аверин А.В.
