Может ли нейронная сеть обнаруживать простые числа?

21

Я не ищу эффективный способ найти простые числа (что, конечно, решаемая проблема ). Это больше вопрос «что если».

Итак, теоретически: не могли бы вы обучить нейронную сеть предсказывать, является ли данное число n составным или простым? Как будет создана такая сеть?

Fullk33
источник
1
Взгляните на cs.indstate.edu/~legri/prime06.pdf
VividD
2
Если простые числа следуют шаблону и кто-то просто обучает нейронную сеть с достаточным количеством скрытых узлов, чтобы определить границу классификации, я полагаю, это сработает. Однако мы не знаем, существует ли эта классификация, и даже если бы она существовала, нам пришлось бы доказать, что такое граница, чтобы доказать, что нейронная сеть действительно нашла правильный шаблон.
пятнадцатое

Ответы:

11

Ранний успех тестирования простых чисел через искусственные сети представлен в «Композиционном нейросетевом решении для тестирования простых чисел» , Ласло Эгри, Томас Р. Шульц, 2006 . Основанный на знаниях подход каскадной корреляции (KBCC) показал наибольшую перспективу, хотя практичность этого подхода затмевается другими простыми алгоритмами обнаружения, которые обычно начинаются с проверки младшего значащего бита, немедленного сокращения поиска вдвое и последующего поиска. на основе теоремы и другие эвристические вплоть до . Однако работа была продолжена с помощьюобучения на основе знаний с KBCC, Shultz et. и др. 2006еLоор(Икс)

02N-1N

  1. Можно ли просто запоминать простые числа в диапазоне целых чисел?
  2. Может ли это, научившись вычленять и применять определение простого числа?
  3. Можно ли это, изучив известный алгоритм?
  4. Может ли это быть путем разработки собственного алгоритма во время тренировок?

Прямой ответ - да, и это уже было сделано в соответствии с 1. выше, но это было сделано путем подбора, а не изучения метода определения простых чисел. Мы знаем, что человеческий мозг содержит нейронную сеть, которая может выполнять задачи 2, 3 и 4, поэтому, если искусственные сети развиты в той степени, в которой большинство считают, что это возможно, то ответ для них будет положительным. На момент написания этого ответа не существует контраргумента для исключения какой-либо из них из диапазона возможностей.

Неудивительно, что была проделана работа по обучению искусственных сетей тестированию простых чисел из-за важности простых чисел в дискретной математике, ее применении в криптографии и, более конкретно, в криптоанализе. Мы можем определить важность обнаружения простых чисел в цифровой сети в исследованиях и разработках интеллектуальной цифровой безопасности в таких работах, как «Первое исследование подхода нейронной сети в криптосистеме RSA» , Gc Meletius et. al., 2002 . Связь криптографии с безопасностью наших стран также является причиной того, что не все текущие исследования в этой области будут публичными. Те из нас, кто может иметь разрешение и воздействие, могут говорить только о том, что не засекречено.

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

Что касается когнитивной математики, то развитие математики неожиданности, такой как « Обучение с сюрпризом: теория и приложения» (тезис), Мохаммаджавад Фараджи, 2016, может продолжить то, что начали Эрги и Шульц.

Дуглас Дасеко
источник
1

Теоретически, нейронная сеть может отображать любую заданную функцию ( источник ).

Однако, если вы тренируетесь сеть с номерами 0к N, вы не можете гарантировать , что сеть будет правильно классифицировать номера за пределами этого диапазона ( n > N).

Такая сеть была бы обычной сетью прямой связи ( MLP ), поскольку рекуррентность ничего не добавляет к классификации данного входа. Количество слоев и узлов можно найти только методом проб и ошибок.

Томас В.
источник
1
Универсальные теоремы применяются к непрерывным функциям на компактных подмножествах. Премьер / не премьер не такая функция.
Пасаба Пор Акви
1
@pasabaporaqui: В этом случае функция простых чисел может быть достаточно хорошо аппроксимирована непрерывной функцией с пиками при значениях простых чисел. Таким образом, NN может выдавать 90% шансов быть простым для 6,93 - это явно бессмыслица, но если вы дискретизируете входы и выходы, вас не особо волнует, что NN прогнозирует для нецелых чисел. Я думаю, что этот ответ в основном правильный.
Нил Слэйтер
1

Я научный сотрудник в университете Prairie View A & M. Я подумал, что прокомментирую, потому что я потратил несколько недель на настройку модели MLPRegressor для предсказания n-го простого числа. Недавно он наткнулся на супернизкие минимумы, где первые 1000 экстраполяций за пределами обучающих данных дали ошибку менее 0,02 процента. Даже при 300000 простых чисел он был примерно на 0,5 процента меньше. Моя модель была проста: 10 скрытых слоев, обученных на одном процессоре менее 2 часов.

Для меня напрашивается вопрос: есть ли разумная функция, которая производит n-е простое число? Прямо сейчас алгоритмы становятся очень сложными в вычислительном отношении для экстремальных n. Проверьте временные промежутки между самыми последними найденными простыми числами. Некоторые из них лет друг от друга. Я знаю, что было доказано, что если такая функция существует, она не будет полиномиальной.

Коди К
источник
Добро пожаловать в AI.SE! Обратите внимание, что мы разрешаем только ответы (в отличие от комментариев) в разделе ответов, поэтому я немного усовершенствовал ваш пост, чтобы сосредоточиться на решении вопроса. Для ознакомления с нашим сайтом, смотрите тур .
Бен Н
Привет, Коди, это было не так давно. Но я хотел бы поговорить с вами о тесте, который вы сделали. Хотели бы вы жить в чате о том, что вы сделали и что вы восприняли? Я хотел бы посмотреть, есть ли возможность поэкспериментировать с этим.
Момо
-1

да это возможно, но считает , что проблема целочисленной факторизации является проблема NP-то , и проблема BQP .

из-за этого невозможно, чтобы нейронная сеть, основанная исключительно на классических вычислениях, находила простое число со 100% точностью, если только P = NP.

ncomputers
источник
Как объясняет вопрос, проверьте, является ли число простым, не проблема NP.
pasaba por aqui