Эта фраза относилась к проблеме рендеринга latex формул (последний пример), а так разумеется основная цель — это подготовка материалов, в том числе и обучающих. Я веду курс лекций в СПбГУ/ВШЭ, хочу перевести его в такой формат
Есть более точный анализ сортировки вставками основанный на инверсиях. Инверсия в перестановке — это такая пара элементов, что больший из них стоит раньше. Единственная перестановка с нулевым количеством инверсий — это тождественная, она же является единственной отсортированной. Утверждается, что если сортировка вставками делает своп, то число инверсий уменьшается ровно на единицу. Отсюда количество свопов — это количество инверсий. Количество сравнений — это количества свопов плюс не больше, чем n холостых проверок, после которых срабатывает break.
Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны
Что еще примечательно, если мы можем менять местами только соседние элементы, то сортировка вставками является оптимальной по количеству свопов, так как своп соседних элементов меняет количество инверсий ровно на единицу, поэтому невозможно в таких условиях сделать свопов меньше, чем количество инверсий. К слову, сортировка пузырьком также обладает этим свойством, но при этом делает много ненужных сравнений.
Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
или в некоторых местах открытую область (не выпуклую область)
Хотя бы один пример можете привести?
Алгоритмы линейной оптимизации начинают с некоторой вершины и следуют по прямой, заданной соответствующим уравнением, до следующей ближайшей точки пересечения (вершины)
Это называется Симплекс-метод, обоснование которого опирается на то, что набор линейных равенств и неравенств всегда задает выпуклый многогранник.
1. Предполагаю, что вы имеете в виду следующий пример: есть два треугольника с вершинами (0, 0), (2, 0), (0, 2) и (1, 1), (1, 0), (0, 1) соответственно; наша область — это пересечение первого треугольника и дополнения второго. Такая область действительно невыпукла, как и дополнение второго треугольника. Дополнение треугольника невозможно получить набором линейных неравенств.
2. Ну это точно никакая не проблема, если у вас задача в духе cx->min, Ax<=b, x>=h, то последнее ограничения можно просто добавить к Ax<=b. Ну или можно сделать замену y=x-h, тогда исходная задача переписывается в виде cy->min, Ay<=b+Ah, y>=0. В любом случае это какие-то азы приведения задачи к нужному виду (канонической или стандартной форме).
По поводу остального — вы приводите поверхностные выводы, понять которые без деталей невозможно. Я не понимаю, про какие «необходимые условия и структуры данных» и «формализацию нелинейности» вы говорите.
Должен признать, я вообще не понял вторую и третью проблемы, слишком мало контекста.
3. Устойчивость в задаче линейного программирования — это получение одинакового результата вне зависимости от начальной точки и метода обхода вершин (по тексту было уточнено).
5. Проблема и условия устойчивости. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование (1998).
Посмотрел в книге, там под устойчивостью подразумевается совершенно другое — как изменится решение, если мы немного поменяем параметры задачи. Вообще обычно это называется «Sensitivity analysis».
4. Почему любая система линейных уравнений и неравенств должна порождать выпуклую область?
Потому что пересечение выпуклых множеств выпукло
Линейное программирование не покрывает большинство потребностей в бизнесе (я такое не писал — видно по ссылке). Более того, оно не соответствует сути большинства задач, подразумевающих наличие нелинейности.
Ну так используйте нелинейное!
Нельзя правильно использовать результат, который непонятно как получен. Получая «оптимальное» решение неким стандартным методом, вы, на самом деле, не знаете, что получили.
Тут то в чем проблема? Если переменные задачи не имеют интерпретацию вида «купить у поставщика АА такой объем угля», «перевезти из пункта А в пункт Б столько то угля», то это не проблема математического метода, это проблема моделирования.
Оптимизация в бизнесе в подавляющем числе случаев связана с применением метода линейного программирования.
Линейное программирование покрывает большой пласт задач, но не точно не большинство потребностей бизнеса. Как минимум можно посмотреть на стандартные пакеты для оптимизации и что они умеют. Вот например Gurobi поддерживает линейное, квадратичное и смешанное программирование. Вообще в науке линейное программирование сейчас подпадает под более широкий класс задач выпуклой оптимизации — для них работает тот же эффективный метод внутренней точки, собственно это помогло бы с вашей первой проблемой. Если хотите попробовать как-то применять выпуклую оптимизацию на практике, советую посмотреть на cvxpy/cvxopt. Отдельно стоит выделить оптимизационные пакеты для машинного обучения (tensorflow, pytorch,… ), они вообще работают с произвольными функциями, но без ограничений. Они заточены под другой пласт задач, но тоже более чем используются на практике.
Честно говоря, ни из картинок, ни из текста почти не понятно, чего вы вообще пытаетесь добиться. Все, что понял лично я — это то, что вместо одной оптимизационной задачи вы решали сразу несколько и за счет этого получили больше информации о возможных стратегиях закупки. Думаю, что довольно наивно считать это чем-то прорывным. Более того, я уверен, что многие проблемы можно было бы решить более детальным моделированием, например почему бы не добавить рейтинг поставщика в целевую функцию?
В теории решения экстремальных задач имеется теорема об устойчивости решения задач линейного программирования. Согласно ей решение устойчиво только при условии выпуклости области определения задачи. При большом количестве переменных и неравенств установить, выпукла ли область определения задачи, не представляется возможным. При этом вероятность не выпуклости велика.
Что вы понимаете под устойчивостью? В задаче линейного программирования ограничения всегда задают выпуклое множество.
Среда выдает Агенту только вознаграждение по результатам его действий, Среда никак своей наградой Агента не обучает и не говорит ему правильно он поступает или нет.
Среда обучает агента и говорит ему, поступает ли он правильно или нет, ровно тем, что дает ему вознаграждение по результатам его действий.
Как обычные задачи обучения с учителем, так и задачи обучения с подкреплением решаются с помощью минимизации некоторого функции потерь. Ключевая разница — в более традиционных задачах, таких как классификация, даны «правильные ответы», и в качестве функции потерь используется какое-то расстояние (среднеквадратиченое отклонение, кросс энтропия) между выходами модели и правильными ответами, так как мы знаем функцию расстояния, то можем её продифференцировать. В обучении с подкреплением функция потерь задана извне, поэтому мы не можем её продифференцировать, в этом и заключается ключевая особенность задач обучения с подкреплением.
Таким образом так же обобщая все вышесказанное, мы приходим к выводу, что алгоритмом обучения без учителя мы называем такие алгоритмы, где нет явных указания для алгоритма как ему поступать, а есть только общая оценка всех его действий в процессе решения задачи.
Не надо свою субъективную классификацию методов выдавать за общепринятую. А в общепринятой обучение без учителя — это не когда вы даете только «общую оценку» действий, а когда вы никакой оценки не даете. Обучение с подкреплением (reinforcement learning) — это вполне себе обучение с учителем.
Спасибо, когда писал уже купил тот, что изначально хотел, доволен как слон. С wifi уже обнаружил, что фильмы в высоком качестве не посмотреть, правда задержи в 2-5 секунд не обнаружил, только артефакты изображения и просадку битрейта. Возможно попробую этот SVP 4, спасибо за наводку. Быть может можете что-нибудь посоветовать про всякие chromecast и подобное?
Не совсем понял, что Вы имеете в виду. Яндекс маркет сам по себе ничего не продает (или я не прав?), а только агрегирует данные, в общем то та же реклама, но, судя по всему, сделанная с большей ответственностью.
Или Вы имеете в виду то, что Яндекс большой и разнообразный, директом и маркетом там занимаются разные команды, которые возможно даже никогда друг с другом не общались?
Вот никогда в жизни не кликал на рекламу, а тут решил попробовать, почему бы и нет? Не могу сказать, что получилось плохо — получил новый для себя опыт.
Как говорится, «Вы там сговорились, что ли?», буквально на днях на хабре статья про ЕМ была.
Для ЕМ алгоритма есть очень хороший и простой пример — метод к средних. Он не использует вероятностную трактовку, но в целом имеет схожую структуру.
Вообще, ЕМ алгоритм — это довольно общая штука. Представьте, что вы как-то разметили данные и обучили на этом некоторую статистическую модель. В некоторых ситуациях может так получиться, что если вы этой же моделью разметите обучающую выборку, а потом переучите модель на новой разметке, то модель станет лучше. В общем то, зациклив эту процедуру и получается ЕМ алгоритм, кластеризацией он не ограничен. Я вот довольно много работаю со скрытыми марковскими цепями, там есть хороший аналог — алгоритм Баума-Велша.
А так, мне кажется, что мануал хороший!
P. S. У вас там кажется пару раз $j$ встречается, видимо забыли $inline$ написать. На мой взгляд в заглавной картинке ну уж очень мерзким шрифтом формулы написаны
Хабр не рендерит букву с двумя индексами, если в выражении есть знак суммы (я писал всё в Chrome). Также я хотел везде написать _{i=1}, а не просто i внизу знака суммы, но это тоже не работает, как показал предпросмотр. Наверно, стоит обратиться в поддержку.
Вот одна из моих статей на хабре, где есть "_{i=1}", пробовал открывать в хроме — вроде бы все отображается. По поводу двух индексов не понял, в чем проблема. Вы уверены, что вы корректное TeX выражение использовали?
Честно говоря, мне кажется, что структура статьи очень плохая. Прочитав раздел «Идея Решения» создается ощущение, что вы описываете не ЕМ алгоритм, а один его шаг.
Зашел на википедию, увидел там описание алгоритма ничуть не хуже, чем у Вас, да еще и с анимированным примером. В чем преимущество вашей статьи?
По формулам: у вас где-то g_{ij}, а где-то g(ij). Предположу, что это одни и те же величины, та как g(ij) не определяется… обычно в математических формулах так не делают и используют одинаковый стиль обозначений (в данном случае индексирования), чтобы лишний раз не путать читателя.
Среднее число инверсий в перестановке — n(n-1)/4. Это легко увидеть, если разбить перестановки на пары: перестановка и её перевернутый вариант (элементы идут в обратном порядке); каждая пара элементов образует инверсию либо в исходной перестановке, либо в её перевертыше, поэтому на две перестановки имеем n(n-1)/2 инверсий. Указанный анализ годится также и для произвольного массива, у которого все элементы различны
Что еще примечательно, если мы можем менять местами только соседние элементы, то сортировка вставками является оптимальной по количеству свопов, так как своп соседних элементов меняет количество инверсий ровно на единицу, поэтому невозможно в таких условиях сделать свопов меньше, чем количество инверсий. К слову, сортировка пузырьком также обладает этим свойством, но при этом делает много ненужных сравнений.
Еще интересным моментом является то, что можно за nlogn (а может и быстрее, если есть знатоки RMQ подскажите пожалуйста) посчитать количество инверсий и, если оно окажется достаточно мало, то использовать сортировку вставками, а если велико — что-нибудь другое
Это называется Симплекс-метод, обоснование которого опирается на то, что набор линейных равенств и неравенств всегда задает выпуклый многогранник.
2. Ну это точно никакая не проблема, если у вас задача в духе cx->min, Ax<=b, x>=h, то последнее ограничения можно просто добавить к Ax<=b. Ну или можно сделать замену y=x-h, тогда исходная задача переписывается в виде cy->min, Ay<=b+Ah, y>=0. В любом случае это какие-то азы приведения задачи к нужному виду (канонической или стандартной форме).
По поводу остального — вы приводите поверхностные выводы, понять которые без деталей невозможно. Я не понимаю, про какие «необходимые условия и структуры данных» и «формализацию нелинейности» вы говорите.
Посмотрел в книге, там под устойчивостью подразумевается совершенно другое — как изменится решение, если мы немного поменяем параметры задачи. Вообще обычно это называется «Sensitivity analysis».
Потому что пересечение выпуклых множеств выпукло
Ну так используйте нелинейное!
Тут то в чем проблема? Если переменные задачи не имеют интерпретацию вида «купить у поставщика АА такой объем угля», «перевезти из пункта А в пункт Б столько то угля», то это не проблема математического метода, это проблема моделирования.
Линейное программирование покрывает большой пласт задач, но не точно не большинство потребностей бизнеса. Как минимум можно посмотреть на стандартные пакеты для оптимизации и что они умеют. Вот например Gurobi поддерживает линейное, квадратичное и смешанное программирование. Вообще в науке линейное программирование сейчас подпадает под более широкий класс задач выпуклой оптимизации — для них работает тот же эффективный метод внутренней точки, собственно это помогло бы с вашей первой проблемой. Если хотите попробовать как-то применять выпуклую оптимизацию на практике, советую посмотреть на cvxpy/cvxopt. Отдельно стоит выделить оптимизационные пакеты для машинного обучения (tensorflow, pytorch,… ), они вообще работают с произвольными функциями, но без ограничений. Они заточены под другой пласт задач, но тоже более чем используются на практике.
Честно говоря, ни из картинок, ни из текста почти не понятно, чего вы вообще пытаетесь добиться. Все, что понял лично я — это то, что вместо одной оптимизационной задачи вы решали сразу несколько и за счет этого получили больше информации о возможных стратегиях закупки. Думаю, что довольно наивно считать это чем-то прорывным. Более того, я уверен, что многие проблемы можно было бы решить более детальным моделированием, например почему бы не добавить рейтинг поставщика в целевую функцию?
Что вы понимаете под устойчивостью? В задаче линейного программирования ограничения всегда задают выпуклое множество.
Those who cannot remember the past are condemned to repeat it
Среда обучает агента и говорит ему, поступает ли он правильно или нет, ровно тем, что дает ему вознаграждение по результатам его действий.
Как обычные задачи обучения с учителем, так и задачи обучения с подкреплением решаются с помощью минимизации некоторого функции потерь. Ключевая разница — в более традиционных задачах, таких как классификация, даны «правильные ответы», и в качестве функции потерь используется какое-то расстояние (среднеквадратиченое отклонение, кросс энтропия) между выходами модели и правильными ответами, так как мы знаем функцию расстояния, то можем её продифференцировать. В обучении с подкреплением функция потерь задана извне, поэтому мы не можем её продифференцировать, в этом и заключается ключевая особенность задач обучения с подкреплением.
Не надо свою субъективную классификацию методов выдавать за общепринятую. А в общепринятой обучение без учителя — это не когда вы даете только «общую оценку» действий, а когда вы никакой оценки не даете. Обучение с подкреплением (reinforcement learning) — это вполне себе обучение с учителем.
Или Вы имеете в виду то, что Яндекс большой и разнообразный, директом и маркетом там занимаются разные команды, которые возможно даже никогда друг с другом не общались?
Для ЕМ алгоритма есть очень хороший и простой пример — метод к средних. Он не использует вероятностную трактовку, но в целом имеет схожую структуру.
Вообще, ЕМ алгоритм — это довольно общая штука. Представьте, что вы как-то разметили данные и обучили на этом некоторую статистическую модель. В некоторых ситуациях может так получиться, что если вы этой же моделью разметите обучающую выборку, а потом переучите модель на новой разметке, то модель станет лучше. В общем то, зациклив эту процедуру и получается ЕМ алгоритм, кластеризацией он не ограничен. Я вот довольно много работаю со скрытыми марковскими цепями, там есть хороший аналог — алгоритм Баума-Велша.
А так, мне кажется, что мануал хороший!
P. S. У вас там кажется пару раз $j$ встречается, видимо забыли $inline$ написать. На мой взгляд в заглавной картинке ну уж очень мерзким шрифтом формулы написаны
Вот одна из моих статей на хабре, где есть "_{i=1}", пробовал открывать в хроме — вроде бы все отображается. По поводу двух индексов не понял, в чем проблема. Вы уверены, что вы корректное TeX выражение использовали?
Зашел на википедию, увидел там описание алгоритма ничуть не хуже, чем у Вас, да еще и с анимированным примером. В чем преимущество вашей статьи?
По формулам: у вас где-то g_{ij}, а где-то g(ij). Предположу, что это одни и те же величины, та как g(ij) не определяется… обычно в математических формулах так не делают и используют одинаковый стиль обозначений (в данном случае индексирования), чтобы лишний раз не путать читателя.