BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration
https://arxiv.org/pdf/2007.14381v1.pdf
🍭️️️ В чем понт
Человечество давно находится в поисках универсального джина-программиста, которому можно показать ртуть и золото и попросить выработать универсальный способ получать из первого второе, не вникая в детали реализации. Исследователи из Google Brain предложили новый способ генерировать программы по набору входов и выходов. Основная идея — последовательно искать подпрограммы, приводящие к валидным промежуточным результатам. Способ превосходит предыдущие решения.
💻 Подробности
🏋️️ Алгоритм
Генерировать программы нужно итеративно — наша задача постепенно получать небольшие подпрограммы, из промежуточных результатов которых строить следующие подпрограммы, и так далее до финального результата. В самом простом и невозможно долгом варианте мы перебираем все комбинации подпрограмм. Однако, хочется отранжировать промежуточные результаты по вероятности того, что они входят в финальную истинную программу. Итак, наша задача — по паре вход-выход и паре промежуточное значение-выход давать оценку на вероятность того, что взятое промежуточное значение — это часть итогового решения задачи.
Сначала определим набор преобразований над входами и выходами. Пример команд — взять строку, прибавить число, перемножить переменные, обьединить результат других операций с помощью оператора ”ИЛИ”. Затем из этих команд предлагается составить свойства — набор-комбинацию команд, которые берут на вход набор входов и выходов и выдают значения True или False. Пример свойств можно найти на картинке под постом.
Далее для всех промежуточных результатов-выходов и свойств мы выписываем вектор истинности свойства для пары. Аналогично делаем для пары вход-выход и всех заданных свойств. Соединяем эти вектора, получаем единые вектор значений True-False. Обучаем модель по этому вектору предсказывать, принадлежит ли промежуточное решение истинной программе. Таким образом, мы нашли способ по паре вход-выход и паре промежуточное значение-выход оценивать вероятность того, что взятое промежуточное значение — это часть итогового решения задачи. Это позволит нам качественно улучшить перебор.
🔎 Эксперименты
Авторы сравнивали число операций и время, которое надо затратить для успешной генерации программ с помощью разных способов ранжирования промежуточных результатов. Один из способов — алгоритм машинного обучения, другой — эвристики, написанные человеком, еще один — эвристическое ранжирование промежуточных результатов по длине программы, в результате исполнения которой они получены. Сравнение производилось на написанном людьми датасете из программ. Например, для успешной генерации 70% программ из датасета способу с алгоритмом машинного обучения потребовалось в 10 раз меньше времени, чем алгоритмам с эвристиками, а 100% успешных генераций программ с помощью эвристического перебора за сколь нибудь разумное время достичь не представляется возможным.
🧐 Что в итоге
Авторы интересным образом скрестили алгоритмический перебор с машинным обучением, значительно ускорив и качественно улучшив финальный алгоритм. Также при ранжировании кандидатов учитывается контекст и семантические свойства прошлых подпрограмм. Такой способ напоминает декомпозицию задачи и дальнейшее копирование подпрограмм со StackOverflow программистом) Надеемся, что и дальше будут появляться такие же интересные и успешные примеры соединения ML с алгоритмами поиска.
https://arxiv.org/pdf/2007.14381v1.pdf
🍭️️️ В чем понт
Человечество давно находится в поисках универсального джина-программиста, которому можно показать ртуть и золото и попросить выработать универсальный способ получать из первого второе, не вникая в детали реализации. Исследователи из Google Brain предложили новый способ генерировать программы по набору входов и выходов. Основная идея — последовательно искать подпрограммы, приводящие к валидным промежуточным результатам. Способ превосходит предыдущие решения.
💻 Подробности
🏋️️ Алгоритм
Генерировать программы нужно итеративно — наша задача постепенно получать небольшие подпрограммы, из промежуточных результатов которых строить следующие подпрограммы, и так далее до финального результата. В самом простом и невозможно долгом варианте мы перебираем все комбинации подпрограмм. Однако, хочется отранжировать промежуточные результаты по вероятности того, что они входят в финальную истинную программу. Итак, наша задача — по паре вход-выход и паре промежуточное значение-выход давать оценку на вероятность того, что взятое промежуточное значение — это часть итогового решения задачи.
Сначала определим набор преобразований над входами и выходами. Пример команд — взять строку, прибавить число, перемножить переменные, обьединить результат других операций с помощью оператора ”ИЛИ”. Затем из этих команд предлагается составить свойства — набор-комбинацию команд, которые берут на вход набор входов и выходов и выдают значения True или False. Пример свойств можно найти на картинке под постом.
Далее для всех промежуточных результатов-выходов и свойств мы выписываем вектор истинности свойства для пары. Аналогично делаем для пары вход-выход и всех заданных свойств. Соединяем эти вектора, получаем единые вектор значений True-False. Обучаем модель по этому вектору предсказывать, принадлежит ли промежуточное решение истинной программе. Таким образом, мы нашли способ по паре вход-выход и паре промежуточное значение-выход оценивать вероятность того, что взятое промежуточное значение — это часть итогового решения задачи. Это позволит нам качественно улучшить перебор.
🔎 Эксперименты
Авторы сравнивали число операций и время, которое надо затратить для успешной генерации программ с помощью разных способов ранжирования промежуточных результатов. Один из способов — алгоритм машинного обучения, другой — эвристики, написанные человеком, еще один — эвристическое ранжирование промежуточных результатов по длине программы, в результате исполнения которой они получены. Сравнение производилось на написанном людьми датасете из программ. Например, для успешной генерации 70% программ из датасета способу с алгоритмом машинного обучения потребовалось в 10 раз меньше времени, чем алгоритмам с эвристиками, а 100% успешных генераций программ с помощью эвристического перебора за сколь нибудь разумное время достичь не представляется возможным.
🧐 Что в итоге
Авторы интересным образом скрестили алгоритмический перебор с машинным обучением, значительно ускорив и качественно улучшив финальный алгоритм. Также при ранжировании кандидатов учитывается контекст и семантические свойства прошлых подпрограмм. Такой способ напоминает декомпозицию задачи и дальнейшее копирование подпрограмм со StackOverflow программистом) Надеемся, что и дальше будут появляться такие же интересные и успешные примеры соединения ML с алгоритмами поиска.