Во всех трех статьях вы оперируете понятием «бета-граница», но даете ему хоть какое-то определение только в последней, его я и процитировал. Как, читая ваши заметки, я должен был понять, что под бета-границей подразумевались именно
Я пользуюсь альфа-бета ГРАНИЦАМИ (к тому же, ЛОКАЛЬНЫМИ границами мультиузлов, а не границами всей задачи)
...?
Я также посмотрел "вашу с Ромкой" работу, чтобы попробовать там найти определение, нашел только
An efficiency of an inequality (1) as
criterion of termination of depth first search directly
depends on current tour length (beta-boundary).
что, в общем то, не то же самое, что
Бета-граница, напротив, ограничивает длину оптимального тура сверху — хуже уже найденного тура длина тоже быть не может
Чем именно ваш подход отличается от метода ветвей и границ вы так и не объяснили, а только объявили, что не используете его. Я могу предположить, что вы используете не только этот метод, но это не значит, что вы его не используете.
Если Вы о себе, то похоже.
Я всего лишь процитировал ваши слова из этого комментария.
Кстати, говорил уже: я НЕ применяю метод ветвей и границ! Чукча не читатель? ;)
Под альфа-границей понимается такая длина тура, для которой оказано, что ниже этой величины даже оптимальный тур быть не может. Бета-граница, напротив, ограничивает длину оптимального тура сверху — хуже уже найденного тура длина тоже быть не может.
В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти A дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева)
Также хотелось бы обратить внимание на аналог метода ветвей и границ для антагонистических игр с подозрительно знакомой терминологией — Альфа-бета-отсечение, про которое, кстати, на хабре есть отличная статья
И почему оптимизированной реализацией назван другой вариант?
Видите, Вы сами себя поправили: в википедии приведен «оптимизированный» вариант, а не оптимальный. Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики, наверно подразумевалась оптимизация базового алгоритма решета Эратосфена, которая просто убирает ненужные действия.
И где там последовательность (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»
...?
Я также посмотрел "вашу с Ромкой" работу, чтобы попробовать там найти определение, нашел только
что, в общем то, не то же самое, что
Чем именно ваш подход отличается от метода ветвей и границ вы так и не объяснили, а только объявили, что не используете его. Я могу предположить, что вы используете не только этот метод, но это не значит, что вы его не используете.
Я всего лишь процитировал ваши слова из этого комментария.
Из страницы о методе ветвей и границ на вики
Также хотелось бы обратить внимание на аналог метода ветвей и границ для антагонистических игр с подозрительно знакомой терминологией — Альфа-бета-отсечение, про которое, кстати, на хабре есть отличная статья
Это довольно распространенная практика в некоторых алгоритмах, кроме РЭ приходят в голову метод двух указателей и алгоритм Кнута-Морриса-Пратта
Видите, Вы сами себя поправили: в википедии приведен «оптимизированный» вариант, а не оптимальный. Думаю, что здесь есть «стилистическая» ошибка от авторов статьи в вики, наверно подразумевалась оптимизация базового алгоритма решета Эратосфена, которая просто убирает ненужные действия.
Я кидал ссылку на параграф, там описание модификации, но кода нет. В общем то, вы и сами согласились, что модификация не очень хитрая, возможно авторы статьи в вики просто не стали заморачиваться с лишним кодом. Я бы даже предположил, что вот эта страница — оригинал статьи в вики. Если нужен код для проверки решета с линейным временем работы, то его можно взять здесь, советую в нем разобраться.
Я не участвовал в этом обсуждении, но кажется, что асимптотика 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»