with Cat The Cat

Интересно делать то, что все делают, но не так, как делают все

На этот раз речь снова пойдёт о тренировке нейросетей по всему набору данных.

Как и все, я вычисляю усреднённый градиент и далее начинается интересное. Собственно, если использовать просто усреднённый градиент с поиском минимума по его направлению, то в некоторый момент времени поиск начинает происходить в некотором небольшом объёме пространства параметров и это почти бесконечный процесс. Вроде, потери уменьшаются, но очень слабо.

Разумно применить спуск по сопряжённому градиенту и это очень улучшает работу - уменьшение потерь происходит быстрее, условие останова достигается быстрее.

Как можно улучшить спуск по сопряжённому градиенту? Правильно, добавив "кривизну пространства" - выполняя спуск по естественному градиенту (natural gradient), например. Или выполнить умножение на обратный гессиан с некоторой точностью, но это у меня только в планах.

Оный естественный градиент g' определён через градиент g и матрице Фишера F: g'=F-1g.

Сама матрица Фишера, для случая, когда мы работаем с вероятностями, определена, как среднее для внешнего произведения градиентов:

F=(1/N)ΣggT

Простое приближение матрицы Фишера это диагональ.

Представим себе, что у градиента есть размерность, Гт, и у параметров есть размерность Пв. Тогда матрица Фишера имеет размерность Гт2, а произведение градиента на обратную матрицу Фишера будет Гт-1. И даже если мы будем считать, что множитель для поиска по лучу (или для ограничения шага в обычном градиентном спуске) имеет размерность Пв*Гт, это всё равно отдаёт махинациями.

Считается, что ADAM использует приближение матрицы Фишера. Но вы посмотрите на него и увидите, что он использует корень квадратный из диагонального приближения матрицы Фишера, фактически получая безразмерную величину.

И вот тут интересное: в настоящий момент у меня получается, что надо иметь разложение F=ATA и градиент надо умножать на A: g'=A-1g.

В этом случае спуск по сопряжённому "естественному" градиенту вполне работает. При использовании матрицы Фишера, как она есть, градиент получается "урезанный" - чем более большой был коэффициент gi усредненного градиента, тем меньше он получается после умножения на матрицу Фишера.

Сама идея про наличие размерностей довольно богата, она вносит физику.

Из физики получается, что градиент это ускорение. Тогда типическая формула обновления координат с использованием момента должна выглядеть вот так:

xk+1(t)=xk+vkte-bt+(1/2)gkt2
vk+1(t)=vke-bt+gkt

Экспонента при "скорости" это "сила трения".

Но это уже полная спекуляция, я ещё не проверял.

Добавлю, что поиск ошибок в программе машинного обучения весьма интересен. Отладчик-то ничего хорошего не покажет - "вот тебе результат поэлементного умножения того и этого, наслаждайся".
with Cat The Cat

Знаки

Чтобы система поддержки цепочки блоков была по-настоящему справедливой, необходимо, чтобы любой бит в блоке был неотличим от любого другого бита. В противном случае, будет торговля помещением транзакций в цепочку блоков, возможность препятствовать размещению и тому подобное.

То есть, система разделяется на "поддержание источника белого шума" и "вычисление смысла белого шума". Или, на кофейную гущу и её толкователей.

Это живо напомнило мне фильм Пи с поисками имени бога главного героя.
with Cat The Cat

Случайный поиск.

Вот пример решателя SAT, основанного на случайном поиске вокруг текущего присваивания: http://fmv.jku.at/yalsat/

Основной алгоритм у него таков:
  1. если нет неудовлетворённых ограничений, остановиться
  2. если есть неудовлетворённые ограничения, взять первое (или второе - или какое-то, там шесть эвристик) из очереди добавленных неудовлетворённых ограничений
  3. выбрать случайным образом литерал ограничения для изменения значения на противоположное
  4. изменить значение выбранного литерала на противоположное и пересчитать неудовлетворённые ограничения
Как легко заметить, мы не отмечаем путь и если мы два раза (четное количество раз) выбрали литерал одной и той же переменной, то мы будем крутиться на одном месте.

Типичный способ ведения пути это табу-список: мы ведём список нескольких последних переменных и запрещаем изменение значения переменной, если она в запрещённом списке. Для такого метода легко понять ограничения: если "окружность" задачи больше размера запрещённого списка, то мы не выйдем из локального минимума. Или мы можем сделать ненужные действия, если наш глобальный минимум (решение) ближе, чем размер запрещённого списка. Обычно, запрещённый список имеет размер в пару десятков переменных, а в задаче у нас пара сотен переменных.

Если же мы будем отмечать несколько сотен (тысяч, десятков, сотен тысяч или даже миллионов) конфигураций присваиваний (a ∧ b отличается от a ∧ -b - две разные конфигурации), то мы можем вести запрещённый список конфигураций в виде фильтра Блюма или хэша кукушки - очень близко к теоретическому минимуму и позволяя перещёлкивать переменные, если они приводят к действительно новому состоянию.

Таким образом мы приближаем локальный поиск к систематическому (DPLL). Мы вынуждены искать наиболее выгодные изменения состояния, которые мы ещё не посещали, что близко к DPLL.
with Cat The Cat

Котлетки

Жарим филе утки, нарезаем ломтиками и в кастрюльку.

На жиру от филе жарим лук, в процессе перемалываем филе блендером - наверное, лучше не большими ножами, а маленькими.

Перемалываем, также, хлеб с небольшим количеством молока. И туда же отправляем лук. Вместе с жиром. ;)

После чего котлетки обваливаем в сухарях, выкладываем на противень на бумагу и запекаем. 180 градусов, наверное.

В принципе, фарш-то уже готов к потреблению, поэтому, я думаю, самое важное это подсушить корочку и дать воде внутри закипеть, чтобы создать воздушность.

Семье нравится. ;)
with Cat The Cat

Неудобный вопрос.

https://en.wikipedia.org/wiki/NP_(complexity)

Если у нас обычная машина Тьюринга и мы можем искать только одно решение (ну, d=2O(1) решений), мы можем решить NP-полную проблему за время 2O(N). Если у нас не детерминированная машина Тьюринга и мы можем одновременно искать d=2O(N) решений, мы можем решить NP-полную проблему за время 2O(log(poly(N))).

Экспоненциальное количество поисков приводит к полиномиальному времени. Один поиск приводит к экспоненциальному времени.

Собственно, неудобный вопрос: а что находится посередине? Где d=O(poly(N)), больше, чем константа и меньше, чем экспонента.

Как известно, CDCL (поиск решения NP-полной задачи с запоминанием ограничений, вызванных конфликтами) экспоненциально быстрее обычного DPLL. Всего 4 процесса CDCL с немного разными параметрами, пущенные параллельно и имеющие возможность обмениваться найденными ограничениями, быстрее, чем один процесс CDCL.

А если таких процессов запустить O(poly(N))? Каково будет время решения?
with Cat The Cat

ZDD

https://gist.github.com/thesz/8b68b09df36c6b1bfca757dea7485bbf - операции с ZDD, как я их представляю.

Содержат объединение, разность, пересечение, поиск наименьшего подмножества (подмножеств, на самом деле) и ещё операцию "распределения" (distribution), это декартово произведение двух множеств подмножеств с применением операции объединения подмножеств.

Как легко увидеть, эта красота очень, очень динамически программируется. ;)

Если хочешь написать операцию над ZDD, подумай, как она выглядит над частью ZDD.
with Cat The Cat

Вашему вниманию...

...предлагается взглянуть на DOP, применённый к HIGGS.

DOP - это сокращение от "diagonal outer product". В выражении для аффинного преобразования Ax+b плотная матрица A заменена на сумму diag(d)+uvT. То есть, теперь выражение выглядит, как (diag(d)+uvT)x+b. Вместо N(N+1) коэффициентов мы получаем 4N коэффициентов.

Проверял я это на HIGGS - он относительно небольшой и на нём тяжело получить высокую точность.

В сумме всё выглядит, что оный ДВП ("диагональ и внешнее произведение") вполне себе работает. Не будучи снабжён ДВП уровнями, последний сигмоид сам по себе показывает точность в 64,1%, что подтверждает, что моя реализация сопряжённого градиента вполне работает. Добавление ДВП уровней повышает точность, и 12 уровней дотренировываются до 65,9%, на 0,2% меньше, чем логистическая регрессия на расширенных квадратами векторах.

В своё время OpenAI выполнили работы по тренировке сетей с уровнями, в которых разреженность либо задавалась случайным образом (как безмасштабный граф), либо тренировалась. У них получалось, что разреженные уровни позволяют хранить в 10 раз меньше коэффициентов - то есть, всё равно O(N2). При поднятии количества коэффициентов до прежнего уровня (через расширение и углубление сети) они получали улучшение предсказания.

Меня хватило только на один эксперимент. ;)

Ещё интересно, что с увеличением глубины сила предсказания растёт и глубокие сети могут быть более мощными, чем неглубокие и широкие.

В любом случае, мне было интересно и, наверное, будет полезно в каком-либо будущем.
with Cat The Cat

Читая про некое средство резервнное копирование данных...

...подумал интересную мысль.

(собственно, ссылка на средство, оно довольно любопытно)

Я вспомнил про мой недавний краткий пост про арифметическое кодирование с сохранением порядка.

Модель для кодирования является ключом. Само кодирование данных является симметричным шифрованием с ключом-моделью.

На этом всё. ;)
with Cat The Cat

zdd

Вот эти вот.

ZDD в своём построении требуют условия уникальности: если мы создаём узел с переменной i и двумя подузлами (ссылками) A и B, то ссылка на такой узел должна быть одной и той же всегда .

Обычно это выполняется с помощью хэш-таблиц для запоминания уже созданных узлов. И это ключ к использованию хэша от содержимого узла в качестве ссылки на него.

Вместо вычисления "ссылки по содержимому" мы просто создаём узел с его хэшем и добавляем его в таблицы (хэш->узел, ссылающиеся на узел хэши и тп). Последнее можно делать по завершению основной работы.

Соответственно, работа разбивается на 1) насоздавать узлов и 2) отсечь только достижимые. 1-я часть весьма параллельна, мы можем создавать узлы независимо от работающих рядом процессов. 2-я часть так же весьма параллельна - это, фактически, слияние с фильтрацией. Мы можем сделать настолько много (или мало) потоков выполнения для операций слияния, насколько это нам выгодно.

Если я всё правильно понимаю, это позволяет сделать довольно экономный вариант работы с ZDD на GPU.