Почему машинное обучение не может распознавать простые числа?

13

Скажем, у нас есть векторное представление любого целого числа n, V_n

Этот вектор является входом в алгоритм машинного обучения.

Первый вопрос: для какого типа представлений можно узнать первичность / составность n, используя нейронную сеть или какое-либо другое ML-отображение векторов в биты. Это чисто теоретически - нейронная сеть может быть неограниченной по размеру.

Давайте проигнорируем представления, которые уже связаны с проверкой простоты, такие как: список факторов n, разделенных нулем, или наличие свидетеля композитности, такого как у Миллера Рабина. Вместо этого давайте сконцентрируемся на представлениях в разных направлениях или представлениях как векторы коэффициентов (возможно, многомерных) полиномов. Или другие экзотические, как положено.

Второй вопрос: для каких, если таковые имеются, типов алгоритма ML будет учиться это невозможно независимо от специфики вектора представления? Опять же, давайте оставим «запрещенные тривиальностью» представления, примеры которых приведены выше.

Выход алгоритма машинного обучения - один бит, 0 для простого, 1 для составного.

Название этого вопроса отражает мою оценку того, что консенсус по вопросу 1 «неизвестен», а консенсус по вопросу 2 - «вероятно, большинство алгоритмов ОД». Я спрашиваю об этом, потому что я не знаю больше, чем это, и я надеюсь, что кто-то может указать путь.

Основная мотивация, если таковая имеется, в этом вопросе: существует ли «информационный теоретический» предел для структуры набора простых чисел, который может быть захвачен в нейронной сети определенного размера? Поскольку я не специалист в такого рода терминологии, позвольте мне несколько раз перефразировать эту идею и посмотреть, получу ли я приближение Монте-Карло к понятию: какова алгоритмическая сложность множества простых чисел? Может ли тот факт, что простые числа являются рекурсивно перечислимым диофантовым (и может удовлетворять конкретному большому диофантовому уравнению ), использоваться для захвата той же структуры в нейронной сети с входами и выходами, описанными выше.

Крис Стрингфеллоу
источник
12
С точки зрения теории, ваша проблема не является четко определенной. Каковы входные данные для алгоритма машинного обучения? Как они генерируются? Что алгоритм знает заранее до своей задачи обучения?
Лев Рейзин
3
Я не думаю, что это хороший вопрос в его нынешней форме для этого сайта.
Каве
4
Он может. Но в машинном обучении мы хотим минимизировать ошибки при тестировании набора данных. Теперь, если вы тренируетесь на вы можете в конечном итоге выучить f ( n ) = n 2 - n + 41, и это прекрасно работает для чисел меньше 41 . Но после этого его производительность не годится. Люди пробовали это (вручную :-)) и пока без особого успеха . В ML мы пытаемся найти шаблоны, но что, если нет шаблонов? [1,20]f(n)=n2n+4141
Pratik Deoghare
1
Вы, кажется, спрашиваете, существует ли алгоритм, который дает функцию из конечных последовательностей натуральных чисел для предикатов на натуральных числах, может правильно вывести предикат простоты, заданный последовательностью простых чисел, при условии дополнительных ограничений алгоритма. Выражение вашего ограничения далее нетривиально, если вообще возможно. Если вы попытаетесь уточнить это, вы можете увидеть.
Виджай Д
1
Простой ответ, потому что трудно аппроксимировать пространство поиска искомой функции f простых чисел, которую вы ищете (то есть f ( n ) возвращает 1, если n простое, и 0 в противном случае для каждого n ). В связи с @PratikDeoghare комментарием, что трудно найти образец в S . Sff(n)nnS
AJed

Ответы:

-8

это старый вопрос / проблема со многими, многими связями, которые глубоко связаны с теорией чисел, математикой, TCS и, в частности, с автоматическим доказательством теорем. [5]

старый, почти древний вопрос: есть ли формула для вычисления простых чисел?

Ответ, да, в некотором смысле, есть различные алгоритмы для его вычисления.

дзета-функция Римана может быть переориентирована как «алгоритм» для поиска простых чисел.

Мне кажется возможным, что подход ГА, основанный на генетическом алгоритме, может когда-нибудь преуспеть в этой проблеме с оригинальной установкой, то есть ГА являются ближайшей известной технологией, у которой больше всего шансов на успех. [6] [7] Это проблема поиска алгоритма из конечного набора примеров, то есть машинного обучения, которое очень похоже на математическую индукцию. однако до сих пор, кажется, нет большого исследования применения GA в теории чисел.

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

Другой подход - это программа, которая имеет большой набор таблиц стандартных функций, а также сложную логику преобразования для распознавания стандартных целочисленных последовательностей. это новая функция, встроенная в Mathematica под названием findsequence[3]

он также связан с относительно новой областью, называемой «экспериментальной математикой» [9,10] или тем, что также называют «эмпирическими» исследованиями в TCS.

Еще один основной момент, который следует здесь подчеркнуть, состоит в том, что последовательность простых чисел не является «гладкой», сильно нерегулярные, хаотические, фрактальные и стандартные алгоритмы машинного обучения исторически основаны на численной оптимизации и минимизации ошибок (например, градиентного спуска) и не делают этого хорошо на поиске точных ответов на дискретные проблемы. но опять же ГА могут преуспеть, и было доказано, что они преуспевают в этой области / режиме.

[1] есть математическое уравнение для n-го простого числа, math.se

[2] формула для простых чисел , википедия

[3] функция поиска последовательности Вольфрама

[4] дзета-функция Римана

[5] главные успехи автоматического доказательства теорем

[6] применения генетических алгоритмов в реальном мире

[7] применение генетических алгоритмов к автоматическому доказательству Ван

[8] Автоматизированное построение гипотез в теории чисел с использованием HR, Otter и Maple colton.

[9] Есть ли приложения экспериментальной математики в TCS?

[10] Список чтения по экспериментальной алгоритмике

ВЗН
источник
1
это отличный ответ. Не уверен, что сайт согласится, но это было то, что я искал. Куча новых направлений для изучения и вековых связей. Спасибо, очень ценю это. Особенно ГА. Кроме того, вы читаете между строк и обобщены от машинного обучения до «формула для простых чисел». Это очень полезно, спасибо.
Крис Стрингфеллоу
11
@ Крис, в этом ответе почти ничего не говорится о машинном обучении. Из вашего комментария к ответу Арье мне кажется, что вы не знакомы с машинным обучением (могу ли я спросить, где вы видели, как машина изучает алгоритм, такой как тест на простоту, из списка примеров?)
Kaveh
6
Г.А. может «выучить» алгоритм тестирования простоты в том же смысле, в котором бесконечная обезьяна, которая пресловута, однажды напечатает все произведения Шекспира
Сашо Николов
@sasho, это еще не было продемонстрировано, но (да, imho), вероятно, не из-за ограничений в технологии, а из-за отсутствия попыток. Коза продемонстрировал GA алгоритмы «решения / изучения» сложных видеоигр, например, pacman (через lisp-деревья примитивов), а также построение схем с использованием подкомпонентов. разве это не так сложно, как поиск простых чисел? реальный вопрос заключается в том, какие типы примитивов будет иметь система, и насколько примитивными они могут быть и все еще находят решение?
vzn
19

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

Есть две области информатики, которые непосредственно изучают такие проблемы. Индуктивный вывод и теория компьютерного обучения . Эти две области очень тесно связаны, и различие является скорее социальным и эстетическим, чем формальным.

AP(A)AAFP(A)

f:NA

iNf(i)=T, for some T in F.

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

RepMRepL(M)

p:NRepL(p(i))f(j)jikjkL(p(j))=L(p(j+1))

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

Золото [1967] Ни одно семейство языков, которое содержит все конечные языки и хотя бы один сверхконечный язык, не может быть пассивно изучено только на основе положительных данных.

Нужно быть очень очень осторожным в интерпретации этого результата. Например, Дана Англуин в 80-х годах показала, что

k

k

Angluin [1987] Регулярные языки можно узнать у учителя, который отвечает на запросы эквивалентности и предоставляет контрпримеры. Алгоритм является полиномиальным по множеству состояний минимального DFA и длине максимального контрпримера.

Это довольно сильный и положительный результат и в последнее время нашел несколько применений. Тем не менее, как всегда, важны детали, как уже предполагает название статьи ниже.

Минимальная непротиворечивая проблема DFA не может быть аппроксимирована в пределах полинома , Pitt and Warmuth, 1989.

Теперь вы можете задаться вопросом, какое отношение это имеет к вашему вопросу? На что я отвечаю, что пространство для математического определения вашей проблемы очень велико, и конкретная точка, которую вы выберете в этом пространстве, повлияет на то, какие ответы вы получите. Вышесказанное не является всеобъемлющим обзором того, как формализовать проблему обучения. Это просто для того, чтобы продемонстрировать направление, которое вы можете исследовать. Все ссылки и результаты, которые я цитирую, чрезвычайно устарели, и с тех пор эта область многое сделала. Существуют основные учебники, с которыми вы могли бы ознакомиться, чтобы получить достаточную справочную информацию для точной формулировки вашего вопроса и определения, существует ли уже найденный ответ.

Виджай Д
источник
Это здорово @Vijay D, спасибо тебе за это.
Крис Стрингфеллоу
Это плохо сформированный вопрос. Мой ответ (и комментарии) ниже показывают, почему. ML может распознавать простые числа, но ни в каком практическом смысле это не займет слишком много времени. Такова природа этого конкретного зверя.
Доминик Черизано
12

Успех алгоритма обучения в решающей степени зависит от представления. Как вы представляете вход для алгоритма? В крайнем случае, предположим, что вы представляете числа как последовательности простых факторов - в этом случае обучение довольно тривиально. В другом крайнем случае рассмотрим представление чисел в виде двоичных строк. Все стандартные алгоритмы обучения, которые я знаю, потерпят неудачу здесь. Вот тот, который будет работать: найдите самую маленькую машину Тьюринга, которая принимает все положительные примеры и отвергает все отрицательные. [Упражнение: докажите, что это универсальный ученик.] Одна из проблем заключается в том, что задача не является вычислимой по Тьюрингу. Можно ли научиться распознавать первичность на основе только двоичного представления?

Арье
источник
Я могу научиться распознавать первичность, основанную на двоичном повторении, если я «научусь», скажем, алгоритму Миллера Рабина. Но я хочу выйти за рамки подобных вещей и посмотреть, есть ли что-то еще. Почему упомянутое вами задание не является вычислимым по Тьюрингу?
Крис Стрингфеллоу
6
Я не понимаю, как здесь можно говорить о проблеме обучения, не ссылаясь, например, на целевой класс функций.
Лев Рейзин
1
Лев, конечно, прав - но я думал, что обсуждение классов функций выходит за рамки вопроса ... :)
Aryeh
-1

Эта проблема является частью современного исследования: с учетом входных и выходных данных найти простейший алгоритм, который производит выходные данные из входных данных. Сети RNN полны по Тьюрингу, поэтому теоретически с помощью бесконечной SGD вы можете оказаться в RNN, что эквивалентно следующему коду:

bool isPrime(int n, int d) {
    if(n<2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}

в этом наборе данных: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... и т. д.

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

https://en.wikipedia.org/wiki/Neural_Turing_machine

https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf

использовать Google ученый для поиска по ключевым словам ...

Степан Яковенко
источник
-3

Машинное обучение подчиняется законам вычислительной сложности.

Основная проблема факторизации находится в классе сложности NP, возможно, даже NP-hard (не доказано).

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

Квантовые компьютеры (КК) могут делать это за полиномиальное время, но Шора - это детерминизм грубой силы, а не машинное обучение.

Возможно, алгоритм обучения КК на основе Шора является подходом. Я на самом деле просто стучу по камням, предлагая это.

Доминик Черизано
источник
1
PRIMES находится в P, поэтому я бы не сказал, что «обнаружение простых чисел» является одной из самых сложных проблем в ML - или любой другой отрасли компьютерной науки, если на то пошло. «Это все о представительстве», которое звучит намного ближе к дому - как объясняется в моем ответе и комментариях под ним.
Арье
Извините, P ≠ NP! PRIMES - это co-NP, и для его решения в P в настоящее время потребуется галактический алгоритм, совершенно не подходящий для любой компьютерной парадигмы - особенно для машинного обучения, независимо от того, как вы его представляете. В любом практическом смысле это NP, и, возможно, NP-hard, спасибо.
Доминик Черизано
1
@Birkensocks, вы, кажется, связали тестирование Primality с Factoring. «PRIMES in P» - это название статьи, в которой впервые был предложен алгоритм полиномиального времени для проверки простоты, en.wikipedia.org/wiki/AKS_primality_test . Также обратите внимание, что Факторинг в NP и co-NP, так что очень маловероятно, чтобы он был NP-сложным, см., Например, blog.computationalcomplexity.org/2002/09/…
Рахул Савани
Да, я думаю, что уже сказал это ...
Доминик Черизано