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

РЕДАКТИРОВАТЬ : я перевожу это на cstheory.stackexchange.com

Я хочу двоичное решение о входной последовательности целых чисел. Для заданного n в последовательности выведите, является ли оно простым или нет. Не используйте AKS, не используйте Миллера Рабина, не используйте пробное деление, даже не используйте жесткий код, последняя цифра должна быть 1,3,7,9, и она должна быть равна 1 или 5 по модулю 6.

Используйте только машинное обучение.

Я не знаю наверняка, но я оцениваю, что «общий консенсус» заключается в том, что методы машинного обучения (нейронные сети, SVM, двоичные классификаторы, кластеризация, байесовский вывод и т. д.) не смогут решить эту проблему проблема?

Что думают люди?

Хорошо, а во-вторых, что если у нас есть какое-то векторное представление целых чисел, несущее некоторую полезную информацию (неизвестно), есть ли принципиальные возражения против того, чтобы машинное обучение могло классифицировать n как простое или составное, если мы могли "выбрать правильные функции", так сказать?

Давайте проигнорируем тривиальный случай, когда вектор содержит, скажем, факторизацию n.

4 голоса | спросил Cris Stringfellow 11 Jam1000000amFri, 11 Jan 2013 00:10:02 +040013 2013, 00:10:02

1 ответ


0

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

По определению: простое число - это натуральное число, большее 1, которое не имеет положительных делителей, кроме 1 и самого себя.

Основная сложность здесь заключается в том, что последовательность простых чисел

2, 3, 5, 7, 11, 13, 17, 19, 23,. , .

ведет себя «непредсказуемо» или «случайно», у нас нет (полезной) точной формулы для n-го простого числа!

Даже если вы попытаетесь обучить алгоритм, у вас будет нечто, приближенное к решению. Вы не можете выбрать достаточно хорошие функции, чтобы предсказать решение.

Скажем, трудный путь состоит в том, чтобы обучить вашу модель этим функциям:

  • Любое число, заканчивающееся четным числом (кроме 2), не является простым числом.
  • Любое число, для которого все добавленные цифры равны 3, 6, 9 или его делителям, не является простым числом.
  • Любое число, заканчивающееся на 5, не является простым числом. (кроме 5)
  • Любое число с одинаковыми цифрами не является простым числом. (если не заканчивается на 1)

В итоге все простые числа заканчиваются цифрами 1, 3, 7 или 9, но не все являются простыми числами.

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

ответил ThiS 11 Jam1000000amFri, 11 Jan 2013 04:26:31 +040013 2013, 04:26:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132