Объяснение формулы Байеса

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

Рассмотрим следующую задачу:

> Пусть существует заболевание с частотой распространения среди населения 0,001 и метод диагностического обследования, который с вероятностью 0,9 выявляет больного, но при этом имеет вероятность 0,01 ложноположительного результата — ошибочного выявления заболевания у здорового человека. Найти вероятность того, что человек здоров, если он был признан больным при обследовании.

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

Понятно, что можно решать ее, используя формулу Байеса напрямую (посчитать P(A), P(B), P(B|A) и из этого вывести ответ на задачу P(A|B)), но есть и более короткий путь.

Поскольку вероятность быть больным до теста равна 0.001, то получается, что шансы болезни изначально 1:999 (или отношение больных и здоровых равно 1/999). Далее нам требуется поделить вероятность true positive на вероятность false positive — получится 0.9/0.01 = 90. Наконец, умножаем 1/999 на 90 и получаем 90/999, или в переводе обратно в вероятность быть здоровым, 999/(90+999) ≈ 0.9174.

Строгое математическое доказательство остается в качестве упражнения читателю :) Но интуитивно это решение можно понимать с помощью водопада (картинка взята отсюда) На картинке синяя вода — это вероятность здорового, а красная — вероятность больного. Фиолетовая область — это то, что мы наблюдаем после теста: либо больного с положительным тестом, либо здорового с ложноположительным тестом. При этом доля обнаруженных случаев (true positive rate, TPR) — 90%, а ложноположительных срабатываний (false positive rate, FPR) — 30%. Тогда изначально отношение синей и красной воды было 80/20 = 4, а в фиолетовой области оно стало (80*30)/(20*90) = 4/3, т.е. разделилось на 90/30 = 3 — отношение TPR и FPR.

(продолжение ниже)

(начало в предыдущем посте)

Теперь разберем вот этот xkcd. Машина дает true positive с вероятностью 1 и false positive с вероятностью 1/36. Даже если пессимистично предположить, что Солнце взорвется с вероятностью 10^-9 (т.е. шансы равны примерно 1:10^9), то получается, что после теста шансы взрыва Солнца оказываются 36:10^9. Это пренебрежимо мало, и скорее всего результат был false positive.

Отсюда, кстати, следует интересный вывод: экстраординарные заявления (т.е. те, у которых изначальная вероятность ничтожно мала) требуют экстраординарных доказательств (т.е. таких, у которых высокая вероятность true positive и крайне низкая вероятность false positive)

В целом, на формулу Байеса можно смотреть как на способ корректировать вероятности после получения дополнительной информации. Если мы получили положительный тест, то требуется скорректировать изначальную вероятность, причем чем больше отношение TPR и FPR, тем более надежный тест и тем больше он скорректирует вероятность.

Вместо одного надежного теста можно также использовать много ненадежных, если они независимы. Так, если запустить машину из xkcd выше десять раз, и все десять раз она заявит, что Солнце взорвалось, то тогда шансы из 1:10^9 превратятся примерно в 3*10^6:1, и можно будет почти наверняка заявлять, что взрыв Солнца произошел.

- Why was the multithreaded programmer's house robbed?
- Because his door was lock-free.

200'000 в ~/.bash_history

Сегодня у меня случился исторический момент — суммарно в ~/.bash_history оказалось 200'000 команд :)

Историю bash'а я веду с мая 2018 года — т.е. на достижение такого числа ушло примерно пять лет. Конечно, по умолчанию bash сохраняет только небольшое число последних команд, но я с самого начала сильно поднял лимит:

HISTSIZE=10000000
HISTFILESIZE=20000000

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

За эти пять лет я не один раз переставлял ОС, но историю перенести очень нетрудно: достаточно просто сохранить файлик ~/.bash_history. При этом польза от сохранения длинной истории весомая. Иногда хочется сделать что-то, что ты уже делал раньше, но точные команды уже давно забыты. Тогда можно просто пройтись поиском по истории и найти нужное :)

https://xn--r1a.website/itpgchannel/1124

(для связности поделюсь ответом на мой пост)

История одного дебага

Так уж получилось, что я использую версию Telegram Desktop из репозиториев Debian. Обычно оно работает без проблем, но изредка возникают и ошибки, которых нет в upstream. Например, в сентябре 2022 года существовал вот такой страшный баг. Здесь репорт содержит, по сути, две проблемы:
- во-первых, анимированные стикеры и реакции отображались криво, а их части отстутствовали
- во-вторых, при попытке воспроизвести определенный анимированный стикер Telegram начинал кушать ядро CPU и не останавливался до выхода из приложения

У меня проявлялись оба бага. А лучший способ показать, как эти баги стриггерить, конечно же, — создать канал, на котором проблемы заметны :)

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

Итак, что же можно сделать, если программа начинает есть много CPU? Конечно же, снять perf :) Увы, здесь perf особо не прояснил ситуацию: он лишь показал на функции внутри QBuffer, по которым мало что понятно.

Надо пробовать что-то еще. Раз программа без необходимости на чем-то съедает CPU, значит можно запустить gdb, остановить в случайный момент и посмотреть на стек. Это уже помогло: наверху оказались все те же методы QBuffer, а ниже по стеку — внутренности ffmpeg. После этого я поставил breakpoint и посмотрел, выйдем ли мы когда-то из кода ffmpeg и вернемся ли обратно в код приложения. Этого не произошло — а, значит, при отрисовке что-то зависает.

После чтения кода методом пристального взгляда выяснилось вот что. Чтобы ffmpeg считывал видео для отрисовки, ему надо передать контекст с указателем на функцию read(). При этом read() должен вести себя не совсем так, как принято в UNIX: при достижении конца файла надо возвращать AVERROR_EOF, а не 0. А Telegram возвращал 0, и происходило вот что: ffmpeg пытался читать данные и постоянно получал 0 байт. Он не считал этот ноль концом файла, и ему были нужны новые данные, поэтому он продолжал свои попытки чтения в бесконечном цикле. А коллбэк на read(), установленный из кода Telegram, как раз использовал QBuffer, который я и видел в perf'е. Вот и вся разгадка :)

При этом забавно, что баг не проявлялся в официальной сборке, которая использует более старый ffmpeg, чем упакованный в Debian. Почему так — я детально не разбирался ¯\_(ツ)_/¯

Дальше все стандартно: я создал PR, его поревьюили, влили и притащили патчем в Debian. На этом проблема оказалась решена :)

Что интересно, Telegram Desktop — штука довольно жирная:
- билд телеграма с debug information весит около двух гигабайт o_O
- gdb на нем заметно подтормаживает
- у меня он собирался примерно минут 30-40; при этом для сборки нужно минимум 16 ГБ памяти, иначе линковка падает с OOM

Update: мой (наполовину мой) pull request в Poco наконец-то залили 🎉

Осталось только дождаться, когда они выкатят очередной релиз

http://lib.ru/INOFANT/BRAUN_F/etaoin.txt

Нашел вот такой вот фантастический рассказ 1942 года. Забавно, насколько он связан с современными большими языковыми моделями :)

Every cloud has a server lining.

(за пояснительной бригадой сюда)

Так, автор канала вышел из творческого кризиса длиною в месяц, и теперь здесь снова будут посты 🎉

Falsehoods Programmers Believe About Phone Numbers

https://github.com/google/libphonenumber/blob/master/FALSEHOODS.md

Забавно, кстати, что эта статья лежит прямо в репозитории libphonenumber — библиотеки для работы с телефонными номерами :)

Угадайте, что делает следующий код:

int foo(int b, int a, int r) {
if (a > 2) a += 1; else a += 13, b -= 1;
return b*1461/4 - b/100 + b/400 + a*153/5 + r - 428;
}

Названия переменных здесь специально изменены, чтобы чуть затруднить угадывание :)

Разгадка (и объяснение!) будет завтра

Итак, разгадка

Функция из предыдущего поста принимает год, месяц и день, и возвращает порядковый номер дня с 1 января 1 года. При этом високосные годы учтены правильно:

foo(1, 1, 1) = 1
foo(1, 1, 31) = 31
foo(1, 2, 1) = 32
foo(2000, 2, 28) = 730178
foo(2000, 3, 1) = 730180
foo(2100, 2, 28) = 766703
foo(2100, 3, 1) = 766704
foo(2023, 8, 16) = 738748

Объяснение, как это работает, можно почитать здесь: https://dotat.at/@/2008-09-10-counting-the-days.html

Там же описана и обратная операция (по номеру дня вычислить дату), но она уже производится несколько сложнее: https://dotat.at/@/2008-09-15-the-date-of-the-count.html

Код для обратной операции выглядит вот так:

void G(int d, int *py, int *pm, int *pd) {
  int y, m;
  d += 305;
  y = d*400/146097 + 1;
  y -= y*1461/4 - y/100 + y/400 > d;
  d -= y*1461/4 - y/100 + y/400 - 31;
  m = d*17/520;
  d -= m*520/17;
  if (m < 11) m += 2; else m -= 10, y += 1;
  *py = y, *pm = m, *pd = d;
}

Тонкости парсинга JSON

Казалось бы, JSON — формат очень простой, и сложно его интерпретировать неправильно. Но на самом деле у него есть свои тонкости, которые в разных языках и библиотеках учитываются очень по-разному. Например:

* 1, false, null, "valid json" — валидные JSON'ы? Или на верхнем уровне могут встречаться лишь массивы и объекты?
* насколько большие числа допускаются в JSON? Обязан ли парсер обрабатывать целые числа больше 2^31? А целые числа больше 2^53 без округления? А больше 2^63?
* повторяющиеся ключи — это ошибка или валидный JSON? Если второе, то какое значение стоит брать?
* какова должна быть кодировка самого JSON-файла? Произвольная? UTF-8? UTF-16?
* что считать валидными строками? Любая ли последовательность байт допустима? Если строка состоит из Unicode-кодпоинтов, то допустимо ли в ней нахождение суррогатных пар UTF-16?
* какие символы в JSON-файле считать пробелами? Допустимы ли '\r' и '\n'? А таб? А U+2060, который по стандарту Unicode считается пробелом?

Чтобы ответить на многие из этих вопросов, были придуманы разные RFC: RFC 7159, RFC 7493 (I-JSON) и, наконец, RFC 8259.

Более подробно можно почитать здесь. Автор этого поста сравнивает огромное число парсеров JSON на соответствие RFC 8259 на указанных выше (и других!) примерах.

Канал про C++: дайте буст
C++: у нас уже есть буст дома
Буст дома: boost

How to sound smart in your TEDx Talk

https://www.youtube.com/watch?v=8S0FDjFBj8o

Посмотрите, очень забавно :) Спойлер: там спикер своей манерой выступления и речи производит впечатление, будто он рассказывает что-то важное, а на самом деле он несет чепуху и рассказывает о том, как он притворяется

(для тех, кто cannot unsterstand English speech good enough, есть неплохие русские субтитры)