И почему оптимизированной реализацией назван другой вариант?
Видите, Вы сами себя поправили: в википедии приведен «оптимизированный» вариант, а не оптимальный. Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики, наверно подразумевалась оптимизация базового алгоритма решета Эратосфена, которая просто убирает ненужные действия.
И где там последовательность (3)?
Я кидал ссылку на параграф, там описание модификации, но кода нет. В общем то, вы и сами согласились, что модификация не очень хитрая, возможно авторы статьи в вики просто не стали заморачиваться с лишним кодом. Я бы даже предположил, что вот эта страница — оригинал статьи в вики. Если нужен код для проверки решета с линейным временем работы, то его можно взять здесь, советую в нем разобраться.
Обладая более чем скудными знаниями по ФП, не берусь судить об ответах, но другие участники обсуждения забраковали некоторые из предложенных сходу решений, указав, что вместо теоретической сложности
Я не участвовал в этом обсуждении, но кажется, что асимптотика n^2/log(n) относится не к решету Эратосфена, а к алгоритму, предложенному в этом комментарии, дело в том, что если вы просто напишете цикл типа: for i:=1 to n do «перебрать все простые делители от 2 до i-1 и проверить делится ли i хотя бы на один из них», то получите ровно такую ассимптотику, так как количество простых чисел от 2 до i — это примерно i / log(i). А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.
Скорее всего, авторы Википедии сами утонули в море информации по РЭ и пропустили эту работу.
Ничего авторы не утонули, просто вы поленились прочитать статью полностью, ну или хотя бы пролистать оглавление. Пролистали бы — обратили бы внимание на решето только по нечетным числам, а заодно более интересное решето за линейное время
UPD. Пардон, я не посмотрел суть обсуждения, пакет выше — это вообще говоря DSL для описания задач выпуклой оптимизации, но в общем предполагается использование градиентных методов
Обратите внимание, что метод Ньютона применяется для градиента fi(x, t), т.е. мы действительно ищем 0 градиента функции, что соответствует минимуму самой функции в случае, когда она выпукла и дифференцируема, у нас как раз такой.
Итак, есть направленный граф с двумя вершинами (узлами)
Серьезно, вы применяете аппарат теории графов для графа из двух вершин?
Насколько будут ближе районы, если построить еще одну полосу в одном направлении?
[trolling] А что, добавление новой дороги меняет положение районов в пространстве? Напоминает мне старый подкол «Что тяжелее: килограмм ваты или килограмм гвоздей?»[/trolling]
А если серьезно
Вопрос — насколько изменится расстояние между узлами, если проводимость в одном из направлений увеличить вдвое?
Связь «расстояния» и «пропускной» способности у вас нигде не задается, поэтому все, что написано в статье — это просто набор алгебраических преобразований без какого-либо смысла.
З.Ы. Если словосочетания network flows, wardrop equilibria ничего вам не говорят, то скорее всего в тематике пропускных способностей на графах вы новичок.
Это ведь геометрическое число. Понимаю е — чисто математическое, но Pi — длина единичной окружности, и кроме как из окружности его не достать.
Не уверен, что вы под этим подразумеваете. В математике pi, как и е задается через предел некоторой последовательности. В случае pi — это предел последовательности периметров правильных вписанных в окружность единичного диаметра n-угольников. Это определение согласовано с дифференциальным исчислением и определением длины кривой, в частности длина кривой x^2+y^2=1 — это 2pi.
Что меня смущает в подходе с ReLU, так это то, что нейросетевая функция, вообще говоря, превращается, если не ошибаюсь, в обычный полином от множества переменных.
Нейросеть на ReLU не может превратиться в полином хотя бы потому, что ReLU — недифференцируемая функция (и вообще говоря это должно смущать больше, так как все обучение нейросетей основано в первую очередь на градиентном спуске).
Со всеми недостатками чисто полиномиальной интерполяции, например, с не очень качественным приближением заранее неизвестных точек
Ну вот вы сами об этой проблеме пишете. Зачем же было тогда от сигмоид возвращаться обратно к полиномам (пусть и с отрицательными степенями, степенями кратности 1/2)? Вообще из статьи не очевидны некоторые существенные детали, например если вы обучали и тестировали нейросеть на одних и тех же данных, тогда результат вообще не имеет никакой ценности.
Можно попробовать немного пожертвовать качеством за счет выигрыша в скорости, приближенно заменив расчет классической активационной функции на расчет более простой функции, которая (на имеющихся входных данных) дает примерно те же результаты. Это, вообще говоря, классическая задача интерполяции: имеем набор значений, вычисленных исходной функцией A(s), и подбираем более простую функцию, которая дает очень похожие значения.
Если не придираться к формальностям, то по сути нейронные сети точно также решают задачу интерполяции. Следует очень аккуратно отнестись к тому, что вы подбираете приближение на имеющихся входных данных, так как рискуете нарваться на переобучение, т.е. вообще говоря можно просто запомнить все входные данные и получить на них идеальную точность и скорость работы. Вопрос всегда в том, чтобы делать предсказания на данных, которые модель не видела.
Другое дело, что функция активации — одномерная, можно например делать приближение не по набору точек, а по всей вещественной прямой, что вроде как возможно. Но вроде как методологически вернее просто брать простую функцию уже на этапе обучения, как например уже писали про ReLU.
Если говорить о количестве итераций до достижения определенной точности, то да — чем выше порядок метода, тем быстрее он сходится. Однако есть и другая сторона медали — чем выше порядок метода, тем сложнее одна итерация, и тем сложнее применять эти методы в пространствах очень больших размерностей. Например, градиентный спуск очень распространен в нейронных сетях, где обычно не меньше миллиона параметров, причем в основном его «стохастический» вариант, который очень хорошо укладывается в парадигму ML. Применять его в пространствах размера < 10000 практически бессмысленно, есть достаточно методов, которые будут работать быстрее.
Я только хотел поставить лайк статье, но мне на глаза попалось вот это
Благодарим бога за формат CSC!
Вы как хотите, а лично я буду благодарить тех ребят, которые в свое время придумали это для матриц (а может и для графов).
Теперь по делу.
А дело в том, что данная процедура прямого хода с разреженной правой частью сама часто используется во внешних циклах и лежит в основе разложения Холецкого и левостороннего (left-looking) LU-разложения.
Но, как уже было сказано ранее, этот аппарат незаменим при факторизациях Холецкого, поэтому помидорами в меня кидаться не стоит.
Я правильно понимаю, что вы утверждаете, что если A — разреженная симметричная матрица, то её разложение Холецкого тоже разреженное? Если это так, то где можно об этом почитать? Если честно я всегда считал, что это неверно.
Я использовал t=0.1, alpha=2. В некоторых экспериментах Ньютон на первом шаге уходил за пределы области. Студенты, которым давал задание реализовать метод внутренней точки, говорил, что тоже иногда Ньютон не выдавал точку внутри. В статье правку сделал
Логарифмический барьер — правильный. К сожалению тут есть небольшие тонкости с выбором начальных данных. Готового рецепта на все случаи жизни я к сожалению не готов дать. Когда готовил анимации у меня возникла проблема, что Ньютон разваливался. Тогда я это решил методом научного тыка.
Про BFGS и все его вариации не могу ничего сказать, лично я пробовал применять градиентный спуск вместо Ньютона — ничего хорошего не выходило. Всегда можно самому попробовать, но думаю, что уже пробовали не один раз. Метод внутренней точки придумали давно и Ньютон там засел намертво.
Смотря для каких целей. Если для прикладных — не стоит задумываться о том, как и какой метод реализован, лучше просто использовать готовый пакет оптимизации типа гуроби, cvxopt или scipy.optimize. Есть например хороший интерфейс на питон — cvxpy. В matlab точно что-то есть, скорее всего и в подобных математических продуктах тоже.
Если нужно «пощупать» руками, я могу дать свои реализации, по которым анимации строил.
Я бы скорее рекомендовал книгу Бойда&Ванденберге (ссылка на нее есть в этой статье), вот например на страницах 230 и 239 есть интерпретация на примере матричных игр: играют двое друг против друга, прямая задача — это задача первого игрока побольше заработать, двойственная — это задача второго игрока поменьше проиграть.
Или вот есть совсем классический, но частный случай: максимальный поток — минимальный разрез. С одной стороны «какой максимальный объем воды можно пропустить по трубам из S в T», с другой «Какой минимальный набор труб (по суммарной пропускной способности) нужно убрать, чтобы разделить S и T»
DC подразумевает, что вы решаете задачу на множествах. DP тоже применяется на множествах, но не ограничивается ими.
В бинарном поиске — это массив/отрезок. Важно то, что есть выбор, как именно поделить его. Можно поделить пополам, а можно на 1/3 и 2/3. Понятно, что худший случай лучше, если делить пополам. Можно вообще делить на несколько отрезков, например так работают B-деревья. Главное, что как бы вы не поделили, задачу можно решить из одного конкретного деления.
Парочка чуть менее тривиальных примеров:
1) Сортировка слиянием: делим массив на две части, сортируем каждую по отдельности и делаем слияние. Ключевой момент — слияние двух отсортированных массивов можно сделать за линейное время. Опять же, достаточно сделать одно разделение
2) Построение выпуклой оболочки: берем какую-то прямую, она как-то разделяет множество точек на два подмножества. Строим выпуклые оболочки на подмножествах и объединяем. Опять же, основная сложность — это сделать объединение. И снова, важно то, что одного разбиения достаточно.
С DP ситуация немного иная: DP обычно фокусируется на добавлении элементов по одному, чтобы уменьшить издержки на «переход» от подзадачи к задаче. Вот пара примеров
1) Задача коммивояжера, точное решение DP за 2^n * n^2. Предлагается считать функцию: f(S, i)=«минимальный путь, проходящий ровно один раз по всем вершинам из S и ни по каким другим, и при этом заканчивающийся на вершине i». Стандартный переход — перебрать предпоследнюю вершину j из S и взять минимум по f(S\{i}, j) + cost(i, j). Так или иначе нужно сделать хоть и минимальный но перебор нескольких разбиений. При этом пересчет f(S, i) по произвольному разбиению S не проще исходной задачи.
2) Задача о рюкзаке: есть набор предметов разного целочисленного объема, нужно набрать ровно V. Можно считать функцию f(W, i)=«можно ли набрать первыми i предметами объем W». Такую функцию относительно легко пересчитать, добавляя предметы по одному, а не разделяя на произвольные подмножества.
По поводу постановки задачи: «максимальный этаж, с которого можно бросить яйцо, не разбив» — это не ваша функция f(n, m). Если яйцо не разбивается с этажа k, но разбивается с этажа k+1, то f(n, m) — это максимальное такое число h, что с запасом n яиц и m попыток мы можем гарантировано найти k, если известно, что k<=h.
В финальном коде есть строчка
h += t
Быть может там имелось в виду
h += bk
?
Особых надежд на что-то более быстрое практически нет.
Вроде бы есть. Вообще задача о назначениях часто в научных статьях называется «задачей о паросочетании минимальной стоимости» (minimum cost bipartite matching problem), обычно рассматривается как подкласс задачи о потоке минимальной стоимости (minimum cost flow problem). По этим названиям можно поискать и найти кучу всего, что напридумывали.
Беглый поиск в goolge scholar выдал вот эту статью, судя по абстракту там лучше, чем n^3, но асимптотика содержит величины стоимостей. Скорее всего это не первый подобный алгоритм. Работают ли они быстрее на практике — другой вопрос. Опять же, кажется, что отдельно с задачей о назначениях особо не заморачиваются, штурмуют как минимум потоки.
Это довольно распространенная практика в некоторых алгоритмах, кроме РЭ приходят в голову метод двух указателей и алгоритм Кнута-Морриса-Пратта
Видите, Вы сами себя поправили: в википедии приведен «оптимизированный» вариант, а не оптимальный. Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики, наверно подразумевалась оптимизация базового алгоритма решета Эратосфена, которая просто убирает ненужные действия.
Я кидал ссылку на параграф, там описание модификации, но кода нет. В общем то, вы и сами согласились, что модификация не очень хитрая, возможно авторы статьи в вики просто не стали заморачиваться с лишним кодом. Я бы даже предположил, что вот эта страница — оригинал статьи в вики. Если нужен код для проверки решета с линейным временем работы, то его можно взять здесь, советую в нем разобраться.
Я не участвовал в этом обсуждении, но кажется, что асимптотика n^2/log(n) относится не к решету Эратосфена, а к алгоритму, предложенному в этом комментарии, дело в том, что если вы просто напишете цикл типа: for i:=1 to n do «перебрать все простые делители от 2 до i-1 и проверить делится ли i хотя бы на один из них», то получите ровно такую ассимптотику, так как количество простых чисел от 2 до i — это примерно i / log(i). А проблема заключалась ровно в том, что ФП не очень хорошо подходит для реализации РЭ, как и для многих других нетривиальных алгоритмов.
Ничего авторы не утонули, просто вы поленились прочитать статью полностью, ну или хотя бы пролистать оглавление. Пролистали бы — обратили бы внимание на решето только по нечетным числам, а заодно более интересное решето за линейное время
www.cvxpy.org
UPD. Пардон, я не посмотрел суть обсуждения, пакет выше — это вообще говоря DSL для описания задач выпуклой оптимизации, но в общем предполагается использование градиентных методов
Серьезно, вы применяете аппарат теории графов для графа из двух вершин?
[trolling] А что, добавление новой дороги меняет положение районов в пространстве? Напоминает мне старый подкол «Что тяжелее: килограмм ваты или килограмм гвоздей?»[/trolling]
А если серьезно
Связь «расстояния» и «пропускной» способности у вас нигде не задается, поэтому все, что написано в статье — это просто набор алгебраических преобразований без какого-либо смысла.
З.Ы. Если словосочетания network flows, wardrop equilibria ничего вам не говорят, то скорее всего в тематике пропускных способностей на графах вы новичок.
Не уверен, что вы под этим подразумеваете. В математике pi, как и е задается через предел некоторой последовательности. В случае pi — это предел последовательности периметров правильных вписанных в окружность единичного диаметра n-угольников. Это определение согласовано с дифференциальным исчислением и определением длины кривой, в частности длина кривой x^2+y^2=1 — это 2pi.
Нейросеть на ReLU не может превратиться в полином хотя бы потому, что ReLU — недифференцируемая функция (и вообще говоря это должно смущать больше, так как все обучение нейросетей основано в первую очередь на градиентном спуске).
Ну вот вы сами об этой проблеме пишете. Зачем же было тогда от сигмоид возвращаться обратно к полиномам (пусть и с отрицательными степенями, степенями кратности 1/2)? Вообще из статьи не очевидны некоторые существенные детали, например если вы обучали и тестировали нейросеть на одних и тех же данных, тогда результат вообще не имеет никакой ценности.
Если не придираться к формальностям, то по сути нейронные сети точно также решают задачу интерполяции. Следует очень аккуратно отнестись к тому, что вы подбираете приближение на имеющихся входных данных, так как рискуете нарваться на переобучение, т.е. вообще говоря можно просто запомнить все входные данные и получить на них идеальную точность и скорость работы. Вопрос всегда в том, чтобы делать предсказания на данных, которые модель не видела.
Другое дело, что функция активации — одномерная, можно например делать приближение не по набору точек, а по всей вещественной прямой, что вроде как возможно. Но вроде как методологически вернее просто брать простую функцию уже на этапе обучения, как например уже писали про ReLU.
Вы как хотите, а лично я буду благодарить тех ребят, которые в свое время придумали это для матриц (а может и для графов).
Теперь по делу.
Я правильно понимаю, что вы утверждаете, что если A — разреженная симметричная матрица, то её разложение Холецкого тоже разреженное? Если это так, то где можно об этом почитать? Если честно я всегда считал, что это неверно.
Про BFGS и все его вариации не могу ничего сказать, лично я пробовал применять градиентный спуск вместо Ньютона — ничего хорошего не выходило. Всегда можно самому попробовать, но думаю, что уже пробовали не один раз. Метод внутренней точки придумали давно и Ньютон там засел намертво.
Если нужно «пощупать» руками, я могу дать свои реализации, по которым анимации строил.
Или вот есть совсем классический, но частный случай: максимальный поток — минимальный разрез. С одной стороны «какой максимальный объем воды можно пропустить по трубам из S в T», с другой «Какой минимальный набор труб (по суммарной пропускной способности) нужно убрать, чтобы разделить S и T»
В бинарном поиске — это массив/отрезок. Важно то, что есть выбор, как именно поделить его. Можно поделить пополам, а можно на 1/3 и 2/3. Понятно, что худший случай лучше, если делить пополам. Можно вообще делить на несколько отрезков, например так работают B-деревья. Главное, что как бы вы не поделили, задачу можно решить из одного конкретного деления.
Парочка чуть менее тривиальных примеров:
1) Сортировка слиянием: делим массив на две части, сортируем каждую по отдельности и делаем слияние. Ключевой момент — слияние двух отсортированных массивов можно сделать за линейное время. Опять же, достаточно сделать одно разделение
2) Построение выпуклой оболочки: берем какую-то прямую, она как-то разделяет множество точек на два подмножества. Строим выпуклые оболочки на подмножествах и объединяем. Опять же, основная сложность — это сделать объединение. И снова, важно то, что одного разбиения достаточно.
С DP ситуация немного иная: DP обычно фокусируется на добавлении элементов по одному, чтобы уменьшить издержки на «переход» от подзадачи к задаче. Вот пара примеров
1) Задача коммивояжера, точное решение DP за 2^n * n^2. Предлагается считать функцию: f(S, i)=«минимальный путь, проходящий ровно один раз по всем вершинам из S и ни по каким другим, и при этом заканчивающийся на вершине i». Стандартный переход — перебрать предпоследнюю вершину j из S и взять минимум по f(S\{i}, j) + cost(i, j). Так или иначе нужно сделать хоть и минимальный но перебор нескольких разбиений. При этом пересчет f(S, i) по произвольному разбиению S не проще исходной задачи.
2) Задача о рюкзаке: есть набор предметов разного целочисленного объема, нужно набрать ровно V. Можно считать функцию f(W, i)=«можно ли набрать первыми i предметами объем W». Такую функцию относительно легко пересчитать, добавляя предметы по одному, а не разделяя на произвольные подмножества.
В финальном коде есть строчка
h += t
Быть может там имелось в виду
h += bk
?
Вроде бы есть. Вообще задача о назначениях часто в научных статьях называется «задачей о паросочетании минимальной стоимости» (minimum cost bipartite matching problem), обычно рассматривается как подкласс задачи о потоке минимальной стоимости (minimum cost flow problem). По этим названиям можно поискать и найти кучу всего, что напридумывали.
Беглый поиск в goolge scholar выдал вот эту статью, судя по абстракту там лучше, чем n^3, но асимптотика содержит величины стоимостей. Скорее всего это не первый подобный алгоритм. Работают ли они быстрее на практике — другой вопрос. Опять же, кажется, что отдельно с задачей о назначениях особо не заморачиваются, штурмуют как минимум потоки.