Главная » Просмотр файлов » Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации

Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 6

Файл №1187428 Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации) 6 страницаРешение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428) страница 62020-09-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

При вычислениях использовался тип данных numpy.float128 с точностью 1e − 18и максимальным элементом ≈ 1.19e + 4932. Все хранимые данные помещались в оперативной памяти.5.7.1Условия экспериментовВ экспериментах использовались два типа матрицы C и три типа векторов L̃ и W̃ .Рассмотрим транспортную сеть манхэттоновского типа, т.е.

районысети образуют сетку. Для простоты изложения будем считать, что количество районов по вертикали и горизонтали совпадает и равно m. Возьмем матрицу затрат из энтропийной моделиC = exp(−0.065D),где матрицаD = {dij },41i, j = 1, n,(65)а dij - евклидово расстояние между районами i и j. То есть, каждыйрайон задается парой чисел (p, q), индексируются районы по строчкам(район (1, 1) будет иметь индекс 1, а район (2, 1) - индекс n + 1).

Таким образом, матрица D размера (n, n), n = m2 в l-ой строчке содержитевклидовы расстояния от района с индексом l до всех остальных районов.Продемонстрируем построение для сети 2 на 2. Пусть рассматривается сеть(1, 1)(1, 2)(2, 1)(2, 2)Тогда D будет выглядеть следующим образом:√ 0112√ 1021√ 12 01 √2 110Матрицей C второго типа будетC=D,mean(D)(66)где mean(D) - среднее значение из элементов D. Нормирование насреднее значение необходимо для понимания масштаба малости γ.Первым типом векторов L̃ и W̃ будут вектора, элементы которыхвзяты из равномерного распределения на (0, 1), а затем нормированнына сумму элементов, то есть вектора типаviv̄n = { Pn },i vivi ∈ U [0, 1],i = 1, n.(67)Вторым типом векторов будем брать такую конструкцию: для вектора L̃ первая половина элементов берется из равномерного распределенияи затем нормируется на сумму элементов, а вторую половину элементовберем нулями.

Вектор W̃ строим наоборот:42L̃ =v̄ n20̄ n2!,W̃ =0̄ n2v̄ n2!,(68)где 0̄ n2 - нулевой вектор длины n2 , v̄ n2 - вектор из (67).Третьим типом вектором L̃ и W̃ будут отнормированные вектора интенсивностей картинок из датасета MNIST.Стоит обратить внимание, что во всех трёх случаяхPniL̃i =PnjW̃j =1.Под относительной точностью будем понимать числовой коэффициент в условиях остановки.5.7.2ASTM vs STMСравним быстродействие методов ASTM и STM. Для этого будем использовать вектора L̃ и W̃ из (67), матрицы C из (65) и (66).Проведем сравнение сначала с матрицей C из (65). Возьмем m = 10(т.е.

n = 100), относительную точность 0.05 и набор γ = [0.1, 0.2, 0.3, 0.4, 0.5].43Теперь для тех же входных параметров поменяем матрицу C на (66)и набор γ = [0.02, 0.1, 0.2, 0.3, 0.4, 0.5].Как видно на обоих графиках ASTM сильно быстрее STM (время44работы ASTM от 30 до 60 секунд), это наблюдается и при других входныхпараметрах, поэтому далее мы будем рассматривать только ASTM.5.7.3Преимущество подбора точки стартаВ данном разделе используется матрицы С из (65) и (66).Во время проведения экспериментов на картинках из датасета MNISTбыло замечено, что ASTM работал несколько иначе, чем на векторахиз равномерного распределения, нормированного на сумму элементов.Возникло предположение, что такое поведение может быть связано сбольшим количество нулевых элементов в векторах L̃ и W̃ для картинок. Элементы этих векторов являются интенсивностями соответсвующих пикселей, а сама цифра написана на относительно малой площадикартинки.В результате этого наблюдения было решено провести сравнение быстродействия на векторах L̃ и W̃ из (68).

При использовании матрицы Cиз (65) возможна очень красивая физическая интерпретация: в половинерайонов люди почти не работают, а в другой половине почти не живут.В этот момент появилась идея, как ускорить ASTM, стартуя из точки,более близкой к решению. Будем перед выполнением ASTM запускатьдля решаемой задачи метод балансировки с относительно большим параметром γ. На выходе алгоритм балансировки выдаст комбинацию (λ, µ),которую подадим на вход алгоритму ASTM. Исполнение балансировкибудет занимать малую долю времени выполнения алгоритма, но итоговый выигрыш во времени работы алгоритма ASTM с «умным стартом»по сравнению с обыкновенным ASTM будет довольно-таки заметным.Продемонстрируем вышесказанное на примерах.

Для матрицы C из(65) и γ = [0.001, 0.003, 0.005, 0.008, 0.01].45Рис. 2: Сравнение быстродействия ASTM и ASTM с «умным» стартомдля матрицы затрат из энтропийной моделиДля матрицы C из (66) и γ = [0.005, 0.01, 0.015, 0.02, 0.025].46Рис. 3: Сравнение быстродействия ASTM и ASTM с «умным» стартомдля матрицы затрат евклидовых расстояний, нормированных на среднеезначениеВсе параметры запуска эксперимента указаны на графиках. Эксперименты проводились 7 раз, результаты усреднялись.

Такое доминированиев скорости работы прослеживалось и в других экспериментах, поэтомуфинальное сравнение будем проводить между методом балансировки иметодом ASTM с «умным» стартом.5.7.4Сравнение метода балансировки с ASTM с «умным» стартомСравним скорости работы на векторах L̃ и W̃ из (67), с матрицей затрат C (66).

Значения n возьмем из набора [100, 196, 289, 400], значенияε = [0.01, 0.05, 0.1], параметр γ из отрезка [0.005; 0.025]. Параметр γ, скоторым производился запуск ASTM с «умным» стартом указан на каждом графике. Каждая конфигурация запускалась 4 раза, затем значениявремени усреднялись.47Рис. 4: Сравнение производительности метода ASTM с умным стартоми метода балансировки при относительной точности 0.1Рис. 5: Сравнение производительности метода ASTM с умным стартоми метода балансировки при относительной точности 0.0548Рис.

6: Сравнение производительности метода ASTM с умным стартоми метода балансировки при относительной точности 0.01Заметим, что ASTM с «умным» стартом начинает доминировать балансировку до момента (γ0 ≤ γ∗, где γ0 - точка пересечения графиковвремени работы методов ASTM с «умным» стартом), когда энтропийнорегуляризованная и исходная задачи становятся неразличимы и теряются преимущества решения задачи вышеописанными методами. Отметимтакже, что значения γ ∗ , отображенные на графиках, иногда повторяютсялишь потому, что различия между ними наблюдаются в 8-9 знаке послезапятой.Интересно также посмотреть на зависимость времени работы алгоритмов от n.49Рис. 7: Зависимость времени работы от размера задачиПо теории здесь параболическая зависимость, судя по-всему на рассмотренном участке γ она сильно сглажена.Теперь будем использовать матрицу C (65). Проделаем экспериментыдля тех же n, но для одной точности 0.05.50Рис.

8: Сравнение производительности метода ASTM с «умным» стартоми метода балансировки при относительной точности 0.01 для C из (65)Как видно на изображениях, точка персечения графиков γ0 лежитлевее γ ∗ , либо очень близко к нему. Это означает, что для полноты картины необходимо провести сравнение метода ASTM с «умным» стартомс методом решения задачи ЛП. Есть основания полагать, что, например,симплекс-метод будет доминировать ASTM с «умным» стартом лишь вочень малой окрестности 0, но никак не на границе γ ∗ . Однако в даннойработе подобное исследование проводиться не будет, но отмечу следующее: если нормировать матрицу затрат C (65) на среднее значение, какв случае (66), тогда получим следующую картину:51Рис.

9: Сравнение производительности метода ASTM с «умным» стартоми метода балансировки при относительной точности 0.01 для C из (65),нормированной на среднее значениеНапомним, что такое преобразование осуществляется для оценки истинного масштаба γ, и в данном случае оно демонстрирует преимуществометода ASTM с «умным» стартом над балансировкой до γ ∗ .5.7.5Сравнение методов на датасете MNISTПроведем сравнение быстродействия ASTM с «умным» стартом и метода балансировки на датасете MNIST. MNIST - это датасет рукописныхцифр. Инвертированные элементы датасета выглядят так:Рис. 10: Инвертированные элементы датасета MNISTКаждую картинку конвертируем в шкалу интенсивности. Таким образом, значение каждого пикселя принимает значение от 0 до 1, где 0соответсвует чёрному цветы, а 1 - белому. Кроме того каждая картинка52развернута из квадратной матрицы с линейным размером 28 в вектор сразмером 784, отнормированный на сумму элементов.

Матрица C - строится как в случае (66).Всё также хочется сравнить значение γ0 , когда ASTM с «умным»стартом начинает доминировать балансировку, со значением γ ∗ =ε4 ln n .Мы запускаем оба алгоритма для одинакового набора параметров γдля пяти пар картинок. Полученные значения времени мы аггрегируем по γ. Эти действия выполняются для трёх значений относительнойточности из условий остановки [0.01, 0.05, 0.1].535.7.6Обсуждение результатовЭксперименты показали, что при малом параметре γ ASTM работаетбыстрее метода балансировки.

Характеристики

Список файлов ВКР

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6361
Авторов
на СтудИзбе
310
Средний доход
с одного платного файла
Обучение Подробнее