Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 6
Текст из файла (страница 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√ 1021√ 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 работаетбыстрее метода балансировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
