Category: it

Category was added automatically. Read all entries about "it".

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

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

...предлагается взглянуть на 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

Порядок

Сперва о порядке байтов в представлении слов.

У нас есть два порядка байтов в слове: LSB, младший (наименее значимый) байт вперёд и MSB, старший (наиболее значимый) байт вперёд. В первой случае проще преобразовывать между значениями разных размеров, второй случай проще сравнивать побайтово (memcmp).

Можно считать, что для MSB порядка байтов "вес" i-го (от адреса значения, i=1..size, 1 это байт по адресу значения) байта равен 256(size-i).

Теперь о порядке строк.

Строки мы сравниваем побайтово, как "целые в кодировке старший байт вперёд". Однако от целых строки отличны наличием длины, строка может содержать и ноль байтов и теребайт. В библиотеке crit bit trees предлагают считать все строки представленными бесконечной последовательностью байтов с дополнением нулями справа.

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

Арифметическое кодирование так же представляет последовательности символов в виде бесконечных дробей.

Про порядок арифметически закодированных строк.

Сперва предложу рассмотреть кодирование битов. Если мы используем одну и ту же, сколь угодно динамическую модель, то конкретный i-й бит 0 всегда будут закодирован в диапазоне [0..pi), а 1 всегда будет закодирован в диапазоне [pi..1). То есть, последовательность битов, начинающаяся с 0, будет иметь закодированное представление меньшее (в смысле сравнения получившихся строк - получившаяся дробь будет меньше), чем последовательность битов, начинающихся с 1.

В случае кодирования битов мы кодируем полный алфавит.

И если мы кодируем полный алфавит, как это принято в побуквенных языковых моделях (charRNN, TDCN, побуквенная SNMLM и тп), мы сохраняем свойство выше.

Типичный PPM* подход кодирует не полный алфавит, а алфавит текущего контекста и символ неудачи. Поэтому к нему вывод выше не применим. Но если заставить PPM разворачивать вероятности всех символов в полный контекст, то мы можем сравнивать кодированные (сжатые) представления с сохранением порядка несжатых.

Итак, основной вывод: при арифметическом кодировании с использованием полного алфавита мы получаем сохранение порядка несжатых строк при сравнении сжатых представлений.
with Cat The Cat

XKCD

https://xkcd.com/538/

- У него же ключ в 4096 битов!
- Вот тебе гаечный ключ, стучи ему по коленке, пока не выдаст пароль.

Если у кого-то есть перевес в способности (способность здесь это возможность, умноженная на желание) применения насилия, то у него есть перевес в способности влиять на некоторые теоретические выкладки.

На поверхности сейчас это гендерная всякая теория, но это распространяется и на биткойн в том числе и другие системы реестров.
with Cat The Cat

Потеря памяти при чтении газет

Она же амнезия Гель-Манна.

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

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

Могу ли я получить правильные сведения от людей, что проваливаются там, сям, там, тут и сям?

Наверное, могу, если учту, что эти люди 1) использовали даже явно неправильные сведения полезным образом, и 2) не смогли найти занятия лучше, чем выпускать видео на ютьюбе дважды в день.

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

Здесь интересно, насколько может быть упрощено мышление и насколько повышается продуктивность.

Я считаю, среди всего прочего, что использование IDE вредно - оно снижает неприятные ощущения от ведения сложного кода и вместо упрощения, код усложняется. Может ли аналогия с уменьшением боли от сложного кода помочь в анализе упрощения мышления? Не знаю.
with Cat The Cat

Повою про БД

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

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

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

"Туман войны"

Перегрузка информацией привела к появлению целе-ориентированной системы отдачи приказов.

Рассчитывать на то, что какой-то супермозг сможет вычленить нужное из всякого, не стоит.

Собирать надо важное, а не всё подряд.

Ну, и посмотрите на количество коэффициентов в GPT-3 - 175 миллиардов чисел. Эта штука способна запомнить текст в 175 гигабайт (вообще, не байтов, а символов - то есть, ещё больше) дословно. Это уровень Шерешевского, так сказать, который был способен поражать способностью к запоминанию своего редактора (обычного умного человека) в начале прошлого века. Способность к "пониманию" у GPT-3 отлично продемонстрирована текстом про единорогов с четырьмя рогами.
with Cat The Cat

Описание систем.

По какой-то причине программисты любят программировать. Хотя уже лет 10, как минимум, программирование это конструирование систем, и чем дальше, тем это более выражено.

Я написал программу - но это только полдела. Программа должна быть обёрнута в окружение и подключена к, как минимум, одной другой программе (серверу БД, обычно). Что в этом окружении важно? Как другие программы влияют на то, что я должен написать?

Дальше больше. Вот мы склеили систему, обычно, сценариями на Питоне или bash. Является ли эта система оптимальной? Склейка же, обычно, рассчитывает на разделение работы - вот тут у нас балансировка нагрузки, а вот тут мы эти запросы обрабатываем, рассчитывая, что подключение к программе не будет установлено, пока не обработаем запрос. Прогоняя запрос через ядро ОС, с копированием и прочими атрибутами разделения.

Можем ли мы склеить nginx и приложение, склеенные Питоном? Чтобы сэкономить процентов десять-двадцать энергии системы в целом. Да ни за что - почти никому, кроме Microsoft, это даже в голову не приходит.

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

Остановлюсь.
with Cat The Cat

Блок чейны.

Чтобы бы мне не высказаться.

Биткойн и Эфириум - число-отгадка (nonce) стоит последним в заголовке блока. Поэтому клиенту можно передавать не весь заголовок, а лишь состояние SHA-256 (или что там у эфира) перед отгадкой. Это позволяет использовать плохо ("хорошо" с точки зрения авторов - обдимиcация!) написанные клиенты шахтёрских артелей вслепую, что позволяет выполнять перестройку цепочек. Что и произошло с Эфириумом несколько раз. И что позволяет переносить мощности вычисления SHA-256 между криптовалютами.

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

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

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

HotStuff - "если потребовать от сетевого уровня гарантий, что не предоставляет даже TCP, то у нас всё получится! а на краевые случаи мы не будем обращать внимания" Тоже получаются волшебные числа пропускной способности. Но в случае Libra Foundation (авторы) все же джентельмены, на слово верят.

В общем, я разочарован - и это слабо сказано.