Forwarded from Data Blog
Закон Гутхарта — неожиданная сторона критичности в сторону объяснения моделей.
Привет, друзья! Сегодня прям о вкусном:
когда метрика становится целью, она перестаёт быть хорошей метрикой
Или в оригинале:
any observed statistical regularity will tend to collapse once pressure is placed upon it for control purposes
Именно так звучит закон Гудхарта, пришедший из экономики, чтобы в машинном обучении просто «с ноги» заставить исследователей обратить внимание на метрики. Изначально он появился примерно в такой амплуа:
если государство вводит KPI для измерения успеха, бюрократическая система начинает оптимизировать именно этот KPI, а не реальный результат.
Если это амплуа перенести в машинное обучение, то получается такой сценарий:
если задача обучения модели — оптимизация метрики, то модель может подогнаться под эту метрику вместо реального улучшения качества решения задачи.
Примеров исследований мало. Из игрушечных примеров (и вдогонку — обзор, почему метрика может быть проблемой):
* Переобучение модели в соревновании на оценку лидерборда.
* В результате оптимизации под CTR (click-through rate) можно прийти к показу провокационного (кликбейтного) контента, потому что он вызывает больше реакций, даже если это негативный эффект.
Из реальных, практико-ориентированных и связанных непосредственно с XAI мне удалось найти статью
Goodhart’s Law Applies to NLP’s Explanation Benchmarks.
Тейк статьи: показывают, что эти метрики объяснимости можно искусственно завысить, не улучшая реальную объяснимость модели.
Метод статьи: при помощи метрик — comprehensiveness (измеряет, насколько ухудшится предсказание модели, если убрать "объясняющие" токены) и sufficiency (оценивает, насколько хорошо модель предсказывает только по выделенным токенам) — показывают, что можно значимо увеличить значения этих метрик, не изменяя сами объяснения и предсказания модели.
Это достигается за счёт того, что удалённые и оставленные токены принадлежат разным распределениям, что приводит к "подгонке" модели под метрику.
Кроме того, с критической точки зрения, можно выдвинуть гипотезу о том, что в случае unlearning’а, модель обучается скорее «скрывать» свое поведение, а не реально избавляется он bias’а. Однако это нельзя однозначно подтвердить и здесь очень важен вопрос о способе отучения.
Таким образом, критическая пища на эти выходные (мне хватило на неделю):
Оценка объяснимости остаётся нерешённой проблемой: существующие метрики можно обмануть и, как следствие, можно измерить определенные показатели, но важно понимать их текущую уязвимость.
Оценку модели, оценку её прозрачности, как и вообще весь процесс разработки, стоит планировать аккуратно. И чем сложнее модель, тем больше зон, которые нужно учитывать.А так всё хорошо начиналось, когда нужно было просто решить задачу MNIST.
Хороших вам выходных, друзья! И множества критических вопросов при оценке моделей!
P.S. Знаю, что обещала вам туториал, но последнее время много учусь и работаю. Делаю интересный проект на учебе, пишу диплом — скоро буду математиком. Плюс подтягиваю навыки, чтобы больше уметь в оценку больших моделей. И чем больше я изучу, тем больше интересного смогу сделать, разобрать и показать)
Всё допишем, оформим, иначе никак 😌
Ваш,
Дата-автор!
Привет, друзья! Сегодня прям о вкусном:
когда метрика становится целью, она перестаёт быть хорошей метрикой
Или в оригинале:
any observed statistical regularity will tend to collapse once pressure is placed upon it for control purposes
Именно так звучит закон Гудхарта, пришедший из экономики, чтобы в машинном обучении просто «с ноги» заставить исследователей обратить внимание на метрики. Изначально он появился примерно в такой амплуа:
если государство вводит KPI для измерения успеха, бюрократическая система начинает оптимизировать именно этот KPI, а не реальный результат.
Если это амплуа перенести в машинное обучение, то получается такой сценарий:
если задача обучения модели — оптимизация метрики, то модель может подогнаться под эту метрику вместо реального улучшения качества решения задачи.
Примеров исследований мало. Из игрушечных примеров (и вдогонку — обзор, почему метрика может быть проблемой):
* Переобучение модели в соревновании на оценку лидерборда.
* В результате оптимизации под CTR (click-through rate) можно прийти к показу провокационного (кликбейтного) контента, потому что он вызывает больше реакций, даже если это негативный эффект.
Из реальных, практико-ориентированных и связанных непосредственно с XAI мне удалось найти статью
Goodhart’s Law Applies to NLP’s Explanation Benchmarks.
Тейк статьи: показывают, что эти метрики объяснимости можно искусственно завысить, не улучшая реальную объяснимость модели.
Метод статьи: при помощи метрик — comprehensiveness (измеряет, насколько ухудшится предсказание модели, если убрать "объясняющие" токены) и sufficiency (оценивает, насколько хорошо модель предсказывает только по выделенным токенам) — показывают, что можно значимо увеличить значения этих метрик, не изменяя сами объяснения и предсказания модели.
Это достигается за счёт того, что удалённые и оставленные токены принадлежат разным распределениям, что приводит к "подгонке" модели под метрику.
Кроме того, с критической точки зрения, можно выдвинуть гипотезу о том, что в случае unlearning’а, модель обучается скорее «скрывать» свое поведение, а не реально избавляется он bias’а. Однако это нельзя однозначно подтвердить и здесь очень важен вопрос о способе отучения.
Таким образом, критическая пища на эти выходные (мне хватило на неделю):
Оценка объяснимости остаётся нерешённой проблемой: существующие метрики можно обмануть и, как следствие, можно измерить определенные показатели, но важно понимать их текущую уязвимость.
Оценку модели, оценку её прозрачности, как и вообще весь процесс разработки, стоит планировать аккуратно. И чем сложнее модель, тем больше зон, которые нужно учитывать.
Хороших вам выходных, друзья! И множества критических вопросов при оценке моделей!
P.S. Знаю, что обещала вам туториал, но последнее время много учусь и работаю. Делаю интересный проект на учебе, пишу диплом — скоро буду математиком. Плюс подтягиваю навыки, чтобы больше уметь в оценку больших моделей. И чем больше я изучу, тем больше интересного смогу сделать, разобрать и показать)
Всё допишем, оформим, иначе никак 😌
Ваш,
Дата-автор!
Forwarded from Artificial stupidity
#statistics
Недавно прочитал статью "Choosing a Proxy Metric from Past Experiments". В авторах челики из google и deepmind. Сама статья, как можно понять из названия, про выбор правильных прокси-метрик.
Пока читал, не покидало ощущение, что что-то тут не так. Вроде идея интересная, какие-никакие аргументы в пользу их решения есть, но все равно интуитивно кажется, что решение в реальности не полетит. Ну да ладно, будущее покажет.
В общем, основных идей несколько:
1. Давайте введем метрику "качества прокси", которая будет зависеть от скрытой корреляции между долгосрочным и прокси эффектами и от соотношения сигнал/шум прокси-метрики.
2. Давайте будем выводить оптимальную прокси-метрику в виде линейной комбинации других прокси. Получаем такую себе портфельную оптимизацию, где мы хотим оптимально "вложиться" в наши прокси, чтобы получить наилучшее решение.
3. Для оценки скрытых параметров давайте будем использовать иерархическую модель (добро пожаловать в Байесовский мир).
4. Ну и все это вместе собирается в некий "фреймворк" для оценки и выбора наилучшего прокси.
Идея прикольная. Я думал о похожем, но скорее в плане вложений в результаты на основе А/Б тестов. У нас же есть какие-то оценки результатов (и в плане ожидания, и в плане неуверенности оценки). Так почему бы не пытаться из этого "портфеля" инициатив собрать оптимальный "портфель". Но я так эту идею и не добил (если кто вдруг знает такую статью или напишет таковую - скиньте почитать).
А вот по статье у меня есть вопросики:
1. Предполагается, что у нас набор все эксперименты i.i.d., что весьма сильное предположение. В статье идет сравнение с мета-анализом. И в мета-анализе это как раз более или менее логичное предположение, Но вот просто в наборе А/Б тестов слишком уж сильное.
2. По тому, как мы получаем итоговую прокси в виде комбинации других прокси с максимизации "хорошести" прокси, у меня есть вопросики к возможному переобучению. В статье вроде даже есть кросс-валидация, но я это ставлю на уровень "сомнительно, но окэй".
3. Не факт, что эта история хорошо обобщается. Впрочем, авторы так явно и заявляют в статье. Но там реально примеры весьма специфичные. Рек. системы, еще и на каких-то гигантских объемах выборок (гугл же). И вроде как еще и группа тестов с примерно одной системой (ну как я понял, иначе откуда i.i.d.).
4. Кажется, что иерархическая модель может быть не такой уж быстрой. Там будет много MCMC симуляций же. Но тут надо тестить, может и все быстро будет работать.
5. В appendix'е какая-то странная матрица ошибок с отсечениями по размеру t-статистик на тестах по двум метрикам (прокси и north-star). Выглядит скорее эвристикой. Возможно, даже рабочей, но как-то не очень надежно выглядит на такое смотреть.
Если подводить итог.
Идея прикольная, но про реальное применение большие вопросики. Может как-то руки дойдут с чем-нибудь таким поковыряться. Ну или в какой-нибудь из докладов утащу как идею.
Недавно прочитал статью "Choosing a Proxy Metric from Past Experiments". В авторах челики из google и deepmind. Сама статья, как можно понять из названия, про выбор правильных прокси-метрик.
Пока читал, не покидало ощущение, что что-то тут не так. Вроде идея интересная, какие-никакие аргументы в пользу их решения есть, но все равно интуитивно кажется, что решение в реальности не полетит. Ну да ладно, будущее покажет.
В общем, основных идей несколько:
1. Давайте введем метрику "качества прокси", которая будет зависеть от скрытой корреляции между долгосрочным и прокси эффектами и от соотношения сигнал/шум прокси-метрики.
2. Давайте будем выводить оптимальную прокси-метрику в виде линейной комбинации других прокси. Получаем такую себе портфельную оптимизацию, где мы хотим оптимально "вложиться" в наши прокси, чтобы получить наилучшее решение.
3. Для оценки скрытых параметров давайте будем использовать иерархическую модель (добро пожаловать в Байесовский мир).
4. Ну и все это вместе собирается в некий "фреймворк" для оценки и выбора наилучшего прокси.
Идея прикольная. Я думал о похожем, но скорее в плане вложений в результаты на основе А/Б тестов. У нас же есть какие-то оценки результатов (и в плане ожидания, и в плане неуверенности оценки). Так почему бы не пытаться из этого "портфеля" инициатив собрать оптимальный "портфель". Но я так эту идею и не добил (если кто вдруг знает такую статью или напишет таковую - скиньте почитать).
А вот по статье у меня есть вопросики:
1. Предполагается, что у нас набор все эксперименты i.i.d., что весьма сильное предположение. В статье идет сравнение с мета-анализом. И в мета-анализе это как раз более или менее логичное предположение, Но вот просто в наборе А/Б тестов слишком уж сильное.
2. По тому, как мы получаем итоговую прокси в виде комбинации других прокси с максимизации "хорошести" прокси, у меня есть вопросики к возможному переобучению. В статье вроде даже есть кросс-валидация, но я это ставлю на уровень "сомнительно, но окэй".
3. Не факт, что эта история хорошо обобщается. Впрочем, авторы так явно и заявляют в статье. Но там реально примеры весьма специфичные. Рек. системы, еще и на каких-то гигантских объемах выборок (гугл же). И вроде как еще и группа тестов с примерно одной системой (ну как я понял, иначе откуда i.i.d.).
4. Кажется, что иерархическая модель может быть не такой уж быстрой. Там будет много MCMC симуляций же. Но тут надо тестить, может и все быстро будет работать.
5. В appendix'е какая-то странная матрица ошибок с отсечениями по размеру t-статистик на тестах по двум метрикам (прокси и north-star). Выглядит скорее эвристикой. Возможно, даже рабочей, но как-то не очень надежно выглядит на такое смотреть.
Если подводить итог.
Идея прикольная, но про реальное применение большие вопросики. Может как-то руки дойдут с чем-нибудь таким поковыряться. Ну или в какой-нибудь из докладов утащу как идею.
Forwarded from Valuable AI / Валентин Малых
второе видео, которым хотел поделиться - выступление для ИТМО про то, что NLP было до LLM
Дзен | Видео
Краткая история NLP – Валентин Малых | Valuable AI / Валентин Малых | Дзен
Видео автора «Valuable AI / Валентин Малых» в Дзене 🎦: МегаШкола ИТМО 2024
Forwarded from Сиолошная
ООООЧень краткое объяснение того, почему ризонеры так сильно прокачивают модели, и почему они выигрывают «модели следующего поколения», обученные на в 10-15-20 раз большем количестве мощностей:
— увеличение вычислений во время инференса (предсказания) в большинстве своём сопоставимо с увеличением мощностей во время тренировки, однако связь не 1-к-1. Какая она точно — мы не знаем (я не знаю), но например в одной из работ по анализу нейросетей для настольных игр каждые x10 тренировочных мощностей были эквиваленты увеличению мощностей на инференс x15
— то есть можно тренировать и модель меньше, и сама тренировка короче, но использовать много "рассуждений" (инференса), и тогда она будет круче
— чем лучше базовая модель, тем очевидно более эффективно расходуются мощности на инференсе
— то есть условная o3, построенная на GPT-4o, может генерировать цепочки рассуждений в 50 раз длиннее, что условно равно увеличению мощностей на тренировку в 40 раз (цифры из головы). А поскольку GPT-4.5 тренировалась всего лишь в 15-20 раз больше, то получается, что ризонер на модели прошлого поколения как бы лучше
— однако эти цифры перемножаются, и ризонер на основе новой модели <должен быть> существенно лучше. Если модель ошибается реже на каждом шаге, то все мощности будут уходить в правильное русло, а не на исправление ошибок
Как итог на примере игры в Го: никто не обучил ОДНУ нейросеть, которая играет на уровне чемпионов мира. Они все хуже. Однако при добавлении времени на перебор (рассуждения) и последовательном многократном применении модели для одного хода качество прыгает до недостижимого человеком уровня — это и отражено на картинке.
Больше вот тут в лекции Noam Brown
— увеличение вычислений во время инференса (предсказания) в большинстве своём сопоставимо с увеличением мощностей во время тренировки, однако связь не 1-к-1. Какая она точно — мы не знаем (я не знаю), но например в одной из работ по анализу нейросетей для настольных игр каждые x10 тренировочных мощностей были эквиваленты увеличению мощностей на инференс x15
— то есть можно тренировать и модель меньше, и сама тренировка короче, но использовать много "рассуждений" (инференса), и тогда она будет круче
— чем лучше базовая модель, тем очевидно более эффективно расходуются мощности на инференсе
— то есть условная o3, построенная на GPT-4o, может генерировать цепочки рассуждений в 50 раз длиннее, что условно равно увеличению мощностей на тренировку в 40 раз (цифры из головы). А поскольку GPT-4.5 тренировалась всего лишь в 15-20 раз больше, то получается, что ризонер на модели прошлого поколения как бы лучше
— однако эти цифры перемножаются, и ризонер на основе новой модели <должен быть> существенно лучше. Если модель ошибается реже на каждом шаге, то все мощности будут уходить в правильное русло, а не на исправление ошибок
Как итог на примере игры в Го: никто не обучил ОДНУ нейросеть, которая играет на уровне чемпионов мира. Они все хуже. Однако при добавлении времени на перебор (рассуждения) и последовательном многократном применении модели для одного хода качество прыгает до недостижимого человеком уровня — это и отражено на картинке.
Больше вот тут в лекции Noam Brown
Forwarded from Math and ML stuff
LLM с диффузией. Почти прорыв.
В последнее время в топах среди тем на AI конференциях можно встретить LLM и диффузию. Нетрудно догадаться, что научный хайп-трейн наконец-то заставит разработать эффективный метод языкового моделирования с помощью диффузии. На самом деле, попытки уже ведутся давно, например в прошлом году появились MDLM и Score Entropy Discrete Diffusion.
Это вопрос может особо остро встать, когда обычные LLM зайдут в тупик и окончательно выйдут на плато. Может быть уже?
У авто-регрессионных (AR) моделей из-за последовательного (слева-направо) вывода есть ограничения: односторонний контекст и усложнен параллелизм. При этом диффузионные dLLM (двунаправленные) языковые модели могут генерировать токены параллельно, но они ограничены фиксированной длиной контекста и на практике все предложенные ранее dLLM показывали перформанс сильно хуже AR.
В работе "Block Discrete Denoising Diffusion Language Models (BD3-LMs)", ICLR 2025, предлагается гибридный подход, использующий лучшее из обеих парадигм вместе.
Принцип архитектуры блочной диффузии BD3-LMs.
Последовательность разбивается на блоки токенов, на уровне каждого блока реализуется диффузионный процесс через зашумление (маскирование ) части токенов и денойзинг (демаскирование через значение logitа). На уровне всей последовательности, сами блоки генерируются авто-регрессионно. В результате преодолеваются проблемы обеих парадигм, и интегрально оно должно работать лучше, в теории .
Эвристики при дизайне нейросеток. Когда разрабатываешь архитектуру, сталкиваешься с инженерными проблемами, которые затрудняют масштабирование и использование моделей в реальных сценариях. Мне иногда интересно проследить, какие трюки дизайнерской эквилибристики разрабатываются для их разрешения, для dLLM они следующие:
1.Выбор диапазона для уровня шума. Нетрудно заметить, что в предельном случае, когда размер блока = 1, dLLM подход эквивалентен просто AR-подходу, но на практике обнаруживается сильное различие в perplexity для BD3-LMS и AR-модели на одних и тех же данных. Это объясняется повышенной дисперсии градиентов, так происходит из-за того, что для диффузии вычисления градиентов идут только по зашумленным токенам, если установить уровень зашумления в максимум, perplexity выравниваются. Возникает проблема: поиск границ (clipped) для оптимального диапазона уровня зашумления, для этого предлагается data-driven noise schedules - поиск границ вероятности маскирования на основе данных, минимизирующий дисперсию градиентов по батчу данных.
2.KV-кэширование в трансформерах - это трюк для ускорения вычислений для однонаправленного внимания: чтобы не вычислять KV контекст на каждом шаге заново, мы кэшируем отвечающие за контекст Key и Value представления токенов с прошлых шагов и итеративно его пополняем, подобно тут. Проблема кэширования усугубляется для dLLM из-за двунаправленного контекста, т.е. KV должны пересчитываться заново на каждом шаге, что дезавуирует возможные бонусы от диффузии. Эта проблема преодолевается эвристикой через "холостой" прогон по всем токенам для вычисления и кэширования только KV значений и последующего их использования для демаскирования при диффузии.
Эксперименты на датасетах LM1B и OpenWebText показывает заметное превосходство BD3-LMs над всеми предыдущими dLLM (D3PM, S2DD, MDLM), но она все еще немного уступает AR LLM.
Революции и чуда не случилось, по-прежнему сидим с GPT. Но из примечательного, недавно появился dLLM Mercury Coder, который в 5-10 раз быстрее AR-LLM. А также Large Language Diffusion Models (LLaDa) бросает вызов тейку, что LLM хороши, потому что авто-регрессионны. В общем, работа ведется.
Здесь больше статей про LLM, особенно в странных сеттингах.
В последнее время в топах среди тем на AI конференциях можно встретить LLM и диффузию. Нетрудно догадаться, что научный хайп-трейн наконец-то заставит разработать эффективный метод языкового моделирования с помощью диффузии. На самом деле, попытки уже ведутся давно, например в прошлом году появились MDLM и Score Entropy Discrete Diffusion.
Это вопрос может особо остро встать, когда обычные LLM зайдут в тупик и окончательно выйдут на плато. Может быть уже?
У авто-регрессионных (AR) моделей из-за последовательного (слева-направо) вывода есть ограничения: односторонний контекст и усложнен параллелизм. При этом диффузионные dLLM (двунаправленные) языковые модели могут генерировать токены параллельно, но они ограничены фиксированной длиной контекста и на практике все предложенные ранее dLLM показывали перформанс сильно хуже AR.
В работе "Block Discrete Denoising Diffusion Language Models (BD3-LMs)", ICLR 2025, предлагается гибридный подход, использующий лучшее из обеих парадигм вместе.
Принцип архитектуры блочной диффузии BD3-LMs.
Последовательность разбивается на блоки токенов, на уровне каждого блока реализуется диффузионный процесс через зашумление (маскирование ) части токенов и денойзинг (демаскирование через значение logitа). На уровне всей последовательности, сами блоки генерируются авто-регрессионно. В результате преодолеваются проблемы обеих парадигм, и интегрально оно должно работать лучше
Эвристики при дизайне нейросеток. Когда разрабатываешь архитектуру, сталкиваешься с инженерными проблемами, которые затрудняют масштабирование и использование моделей в реальных сценариях. Мне иногда интересно проследить, какие трюки дизайнерской эквилибристики разрабатываются для их разрешения, для dLLM они следующие:
1.Выбор диапазона для уровня шума. Нетрудно заметить, что в предельном случае, когда размер блока = 1, dLLM подход эквивалентен просто AR-подходу, но на практике обнаруживается сильное различие в perplexity для BD3-LMS и AR-модели на одних и тех же данных. Это объясняется повышенной дисперсии градиентов, так происходит из-за того, что для диффузии вычисления градиентов идут только по зашумленным токенам, если установить уровень зашумления в максимум, perplexity выравниваются. Возникает проблема: поиск границ (clipped) для оптимального диапазона уровня зашумления, для этого предлагается data-driven noise schedules - поиск границ вероятности маскирования на основе данных, минимизирующий дисперсию градиентов по батчу данных.
2.KV-кэширование в трансформерах - это трюк для ускорения вычислений для однонаправленного внимания: чтобы не вычислять KV контекст на каждом шаге заново, мы кэшируем отвечающие за контекст Key и Value представления токенов с прошлых шагов и итеративно его пополняем, подобно тут. Проблема кэширования усугубляется для dLLM из-за двунаправленного контекста, т.е. KV должны пересчитываться заново на каждом шаге, что дезавуирует возможные бонусы от диффузии. Эта проблема преодолевается эвристикой через "холостой" прогон по всем токенам для вычисления и кэширования только KV значений и последующего их использования для демаскирования при диффузии.
Эксперименты на датасетах LM1B и OpenWebText показывает заметное превосходство BD3-LMs над всеми предыдущими dLLM (D3PM, S2DD, MDLM), но она все еще немного уступает AR LLM.
Революции и чуда не случилось, по-прежнему сидим с GPT. Но из примечательного, недавно появился dLLM Mercury Coder, который в 5-10 раз быстрее AR-LLM. А также Large Language Diffusion Models (LLaDa) бросает вызов тейку, что LLM хороши, потому что авто-регрессионны. В общем, работа ведется.
Здесь больше статей про LLM, особенно в странных сеттингах.
Forwarded from Евгений Козлов пишет про IT (Eugene Kozlov)
Fundamentals of Data Engineering. Глава №5. Data Generation in Source Systems. Часть №3 Виды СУБД
🔹Реляционные базы данных для Data инженера
Идеально подходят для хранения быстро меняющегося состояния приложения. Задача дата инженера - сформировать алгоритм, как извлекать информацию о состоянии приложения с течением времени.
Данные хранятся в таблицах. Таблица содержит:
- отношения (строки)
- поля (столбцы).
- схема (последовательность столбцов с назначенными статическими типами, такими как string, integer или float)
- первичный ключ (уникальное поле для каждой строки таблицы)
- индекс внешних ключей (обычно с помощью первичного ключа)
Нормализация - это стратегия, гарантирующая, что данные в записях не будут дублироваться, что позволяет избежать необходимости обновлять состояния сразу в нескольких местах и предотвращает несоответствия.
🔹Not only SQL
К NoSQL относится огромное количество баз данных, отказавшихся от классической реляционной модели, чтобы дать другие бенефиты.
🔹Key-Value
Доступ к данным осуществляется по некоторому ключу, возможность использовать гибкие фильтры в большинстве случаев отсутствует.
Одной из наиболее популярных реализаций такого подхода являются Redis и Memcached как СУБД хранящие данные в памяти.
🔹Wide column СУБД
Преимущества:
- способны хранить огромные объемы (петабайты данных),
- высокая скорость транзакций (миллионы запросов в секунду),
- обеспечивают низкую задержку (менее 10 мс) и
могут масштабироваться до экстремальных значений.
- быстрое сканирование огромных объемов данных
Недостатки вытекающие из преимуществ:
- не поддерживаются сложные запросы
- для поиска используется только один индекс (ключ партиции),
что означает, что для аналитических сценариев такие СУБД непригодны практически полностью и необходимо настроить экспорт данных в подходящее место.
🔹СУБД для полнотекстового поиска (Elasticsearch, Apache Solr, Sphinx)
- Данные превращаются в инвертированные индексы, что ускоряет поиск.
- Поиск по синонимам, морфологии, опечаткам, стемминг (cats → cat).
- Поддержка ранжирования (релевантность результатов).
🔹Time Series СУБД
Time series (временной ряд) - это последовательность значений, упорядоченных по времени. Любые события, которые регистрируются с течением времени регулярно или нерегулярно являются данными временного ряда.
- оптимизированы для извлечения и статистической обработки данных временных рядов.
- способны справляться с больши потоками данных
- используют буферизацию в памяти для поддержки быстрой записи и чтения.
- подходят для оперативной аналитики.
Примеры: Prometheus, VictoriaMetrics.
🔹Реляционные базы данных для Data инженера
Идеально подходят для хранения быстро меняющегося состояния приложения. Задача дата инженера - сформировать алгоритм, как извлекать информацию о состоянии приложения с течением времени.
Данные хранятся в таблицах. Таблица содержит:
- отношения (строки)
- поля (столбцы).
- схема (последовательность столбцов с назначенными статическими типами, такими как string, integer или float)
- первичный ключ (уникальное поле для каждой строки таблицы)
- индекс внешних ключей (обычно с помощью первичного ключа)
Нормализация - это стратегия, гарантирующая, что данные в записях не будут дублироваться, что позволяет избежать необходимости обновлять состояния сразу в нескольких местах и предотвращает несоответствия.
🔹Not only SQL
К NoSQL относится огромное количество баз данных, отказавшихся от классической реляционной модели, чтобы дать другие бенефиты.
🔹Key-Value
Доступ к данным осуществляется по некоторому ключу, возможность использовать гибкие фильтры в большинстве случаев отсутствует.
Одной из наиболее популярных реализаций такого подхода являются Redis и Memcached как СУБД хранящие данные в памяти.
🔹Wide column СУБД
Преимущества:
- способны хранить огромные объемы (петабайты данных),
- высокая скорость транзакций (миллионы запросов в секунду),
- обеспечивают низкую задержку (менее 10 мс) и
могут масштабироваться до экстремальных значений.
- быстрое сканирование огромных объемов данных
Недостатки вытекающие из преимуществ:
- не поддерживаются сложные запросы
- для поиска используется только один индекс (ключ партиции),
что означает, что для аналитических сценариев такие СУБД непригодны практически полностью и необходимо настроить экспорт данных в подходящее место.
🔹СУБД для полнотекстового поиска (Elasticsearch, Apache Solr, Sphinx)
- Данные превращаются в инвертированные индексы, что ускоряет поиск.
- Поиск по синонимам, морфологии, опечаткам, стемминг (cats → cat).
- Поддержка ранжирования (релевантность результатов).
🔹Time Series СУБД
Time series (временной ряд) - это последовательность значений, упорядоченных по времени. Любые события, которые регистрируются с течением времени регулярно или нерегулярно являются данными временного ряда.
- оптимизированы для извлечения и статистической обработки данных временных рядов.
- способны справляться с больши потоками данных
- используют буферизацию в памяти для поддержки быстрой записи и чтения.
- подходят для оперативной аналитики.
Примеры: Prometheus, VictoriaMetrics.
Forwarded from Гречневые мысли
Курс молодого ресёрчера
Меня в последнее время уж слишком часто спрашивают, чё почитать, чтобы вкатиться в нлп, а я каждый раз пересылаю целую батарею из ссылок, которую я создал год назад. Пришло время обновить ссылки, организовать их в аккуратненький пост и потом кидать уже его.
Ссылки для обучения базе:
- HF NLP Course — Платиновая база. Это надо прочитать, чтобы научиться делать свои минимальные штуки на уровне инженера. Курс больше прикладной, не теоретический, учит взаимодействию с transformers. Он постоянно обновляется и там появляются туториалы по next big thing — например, там уже есть глава про reasoning models.
- Плейлист с лекциями Карпатого и его же гитхаб — Ещё более платиновая и ещё более база. Я очень плохо воспринимаю лекции и обычно смотрю их на х2, но тут и очень понятные объяснения, и иллюстрации в виде питоновского кода в тетрадках, и скорость изложения ровно такая, какая надо. В описаниях к видео есть домашки, если чувствуете, что надо получше разобраться, делайте их :)
- Зоопарк трансформеров — Чуть устаревшая статья на хабре, где описываются разные модификации трансформеров. Для каждой архитектуры и модели кратко описаны ключевые изменения. Новых моделей за последние пару лет тут, к сожалению, нет, но чтобы понять как всё развивалось, этого будет достаточно.
- Attention is all you need — Самая главная статья из современного NLP. Стоит прочитать, осознать и запомнить, потому что по сути с тех пор языковые модели практически не менялись.
- NLP Course For You — Классический курс по базе NLP, есть много про дотрансформерные методы. Мне кажется, что он уже не так актуален, но ознакомиться всё равно стоит.
- NLP чат — Уютненький чятик, где обсуждают новости и задают вопросы. Ваш покорный слуга выступает там в роли бесплатной добровольной техподдержки.
Ссылки для "уже смешариков", чтобы читать новости и развиваться дальше
- LocalLLaMA — Самый популярный сабреддит про локальный инференс ллмок. Все новости обычно появляются там.
- HF Daily Papers — Рассылка свежих статей по DL. Очень советую подписаться по почте, чтобы утром просматривать заголовки и читать интересующее. Помогает очень сильно расширить кругозор.
- lmarena.ai — Тут можно потыкать разные модельки руками, сравнить их и посмотреть, как они отвечают. Удобно, если надо быстро сделать сбс или проверить какую-то гипотезу.
- openrouter.ai — Сайт, где можно использовать модели через апи. Очень дёшево (по сравнению с аналогами), очень удобно. Оплачивается криптой, иностранной картой или через платиру/ggsel.
- 5 Levels of Text Splitting и RAG Techniques — Всё, что вы хотели знать про RAG, других ссылок, по сути, не нужно. В первой разбираются, как правильно сплитить текст для базы знаний, во второй рассматривают все типичные архитектуры и трюки, связанные с рагом.
- MTEB — Рейтинг эмбеддеров. Чем выше, тем лучше. Не спрашивайте в нлп чате, что выбрать, если предварительно не посмотрели сюда!
- HF Cookbook — Список готовых советов и рецептов для решения прикладных задач. Есть и код, и описание задачи, оформлено в виде блогпостов.
- vLLM, llama.cpp, TGI, sglang, exllamav2, Infinity Embeddings, CTranslate2 — Движки для инференса. vLLM, TGI, exllamav2 и sglang для быстрого инференса декодеров на гпу, llama.cpp на цпу. Infinity Embeddings это движок для энкодеров, CTranslate2 для энкодер-декодеров.
Ссылки для совсем опытных Кар-Карычей
- Quantization Deep Dive — офигенный хабрапост от Яндекса, где расписывают математическую базу квантизации и про типы данных
- Ускорение LLM: универсальные методы для популярных архитектур — тоже офигенный хабрапост и тоже от Яндекса, где расписывают варианты ускорения инференса
- Статьи от Давида Дале на Хабре — все очень увлекательны и прекрасны. Мои любимые — про декодирование из эмбеддингов LaBSE, про прунинг токенизатора у mt5 и про дистилляцию берта.
- 100 questions about NLP — универсальный список вопросов для подготовки к собесам. Не на все вопросы есть ответы, но все вопросы хорошие.
Этот список, конечно же, неполный, но как база для вката работает на ура. Если есть что-то ещё полезного — кидайте в комменты.
Меня в последнее время уж слишком часто спрашивают, чё почитать, чтобы вкатиться в нлп, а я каждый раз пересылаю целую батарею из ссылок, которую я создал год назад. Пришло время обновить ссылки, организовать их в аккуратненький пост и потом кидать уже его.
Ссылки для обучения базе:
- HF NLP Course — Платиновая база. Это надо прочитать, чтобы научиться делать свои минимальные штуки на уровне инженера. Курс больше прикладной, не теоретический, учит взаимодействию с transformers. Он постоянно обновляется и там появляются туториалы по next big thing — например, там уже есть глава про reasoning models.
- Плейлист с лекциями Карпатого и его же гитхаб — Ещё более платиновая и ещё более база. Я очень плохо воспринимаю лекции и обычно смотрю их на х2, но тут и очень понятные объяснения, и иллюстрации в виде питоновского кода в тетрадках, и скорость изложения ровно такая, какая надо. В описаниях к видео есть домашки, если чувствуете, что надо получше разобраться, делайте их :)
- Зоопарк трансформеров — Чуть устаревшая статья на хабре, где описываются разные модификации трансформеров. Для каждой архитектуры и модели кратко описаны ключевые изменения. Новых моделей за последние пару лет тут, к сожалению, нет, но чтобы понять как всё развивалось, этого будет достаточно.
- Attention is all you need — Самая главная статья из современного NLP. Стоит прочитать, осознать и запомнить, потому что по сути с тех пор языковые модели практически не менялись.
- NLP Course For You — Классический курс по базе NLP, есть много про дотрансформерные методы. Мне кажется, что он уже не так актуален, но ознакомиться всё равно стоит.
- NLP чат — Уютненький чятик, где обсуждают новости и задают вопросы. Ваш покорный слуга выступает там в роли бесплатной добровольной техподдержки.
Ссылки для "уже смешариков", чтобы читать новости и развиваться дальше
- LocalLLaMA — Самый популярный сабреддит про локальный инференс ллмок. Все новости обычно появляются там.
- HF Daily Papers — Рассылка свежих статей по DL. Очень советую подписаться по почте, чтобы утром просматривать заголовки и читать интересующее. Помогает очень сильно расширить кругозор.
- lmarena.ai — Тут можно потыкать разные модельки руками, сравнить их и посмотреть, как они отвечают. Удобно, если надо быстро сделать сбс или проверить какую-то гипотезу.
- openrouter.ai — Сайт, где можно использовать модели через апи. Очень дёшево (по сравнению с аналогами), очень удобно. Оплачивается криптой, иностранной картой или через платиру/ggsel.
- 5 Levels of Text Splitting и RAG Techniques — Всё, что вы хотели знать про RAG, других ссылок, по сути, не нужно. В первой разбираются, как правильно сплитить текст для базы знаний, во второй рассматривают все типичные архитектуры и трюки, связанные с рагом.
- MTEB — Рейтинг эмбеддеров. Чем выше, тем лучше. Не спрашивайте в нлп чате, что выбрать, если предварительно не посмотрели сюда!
- HF Cookbook — Список готовых советов и рецептов для решения прикладных задач. Есть и код, и описание задачи, оформлено в виде блогпостов.
- vLLM, llama.cpp, TGI, sglang, exllamav2, Infinity Embeddings, CTranslate2 — Движки для инференса. vLLM, TGI, exllamav2 и sglang для быстрого инференса декодеров на гпу, llama.cpp на цпу. Infinity Embeddings это движок для энкодеров, CTranslate2 для энкодер-декодеров.
Ссылки для совсем опытных Кар-Карычей
- Quantization Deep Dive — офигенный хабрапост от Яндекса, где расписывают математическую базу квантизации и про типы данных
- Ускорение LLM: универсальные методы для популярных архитектур — тоже офигенный хабрапост и тоже от Яндекса, где расписывают варианты ускорения инференса
- Статьи от Давида Дале на Хабре — все очень увлекательны и прекрасны. Мои любимые — про декодирование из эмбеддингов LaBSE, про прунинг токенизатора у mt5 и про дистилляцию берта.
- 100 questions about NLP — универсальный список вопросов для подготовки к собесам. Не на все вопросы есть ответы, но все вопросы хорошие.
Этот список, конечно же, неполный, но как база для вката работает на ура. Если есть что-то ещё полезного — кидайте в комменты.
huggingface.co
Introduction - Hugging Face LLM Course
We’re on a journey to advance and democratize artificial intelligence through open source and open science.
Forwarded from Information Retriever
Видеозапись воркшопа LargeRecsys x VideoRecSys c RecSys 2024.
Оказывается, на ютуб уже выложили часть выступлений с воркшопа LargeRecsys x VideoRecSys!
В том числе выложили и выступление от Ed Chi, с которого начался весь хайп семантических айдишников. Я в день самого выступления уже писал краткий tdlr, но советую всё равно его посмотреть. Там будет и увлекательный экскурс в историю рекомендаций и генеративных моделей, и рассказ про связь рексистем с распределением Больцмана, и демка Project Astra. А ещё, они не все свои наработки по семантическим айдишникам опубликовали :)
Также на канале доступно выступление от Derek Cheng (с наработками от той же гугловской рекомендательной группы), в котором мимолётно упоминаются DCN-v3 и DCN-v4, а также есть рассказы про HSTU и про инференс рекомендательных нейросетей.
Надо смотреть! Ссылка на весь плейлист.
Если интересно получить больше контекста, можно почитать:
* пост про Ed Chi
* мои заметки по докладу про ранжирование в Ютубе с прошлой итерации этого воркшопа
* серию постов про RecSys 2024
Оказывается, на ютуб уже выложили часть выступлений с воркшопа LargeRecsys x VideoRecSys!
В том числе выложили и выступление от Ed Chi, с которого начался весь хайп семантических айдишников. Я в день самого выступления уже писал краткий tdlr, но советую всё равно его посмотреть. Там будет и увлекательный экскурс в историю рекомендаций и генеративных моделей, и рассказ про связь рексистем с распределением Больцмана, и демка Project Astra. А ещё, они не все свои наработки по семантическим айдишникам опубликовали :)
Также на канале доступно выступление от Derek Cheng (с наработками от той же гугловской рекомендательной группы), в котором мимолётно упоминаются DCN-v3 и DCN-v4, а также есть рассказы про HSTU и про инференс рекомендательных нейросетей.
Надо смотреть! Ссылка на весь плейлист.
Если интересно получить больше контекста, можно почитать:
* пост про Ed Chi
* мои заметки по докладу про ранжирование в Ютубе с прошлой итерации этого воркшопа
* серию постов про RecSys 2024
YouTube
Keynote: The Future of Discovery Assistance - Ed Chi | VideoRecSys Workshop | RecSys 2024
"The Future of Discovery Assistance" Keynote Talk by Ed Chi (Google DeepMind,) at the Large-Scale Video Recommender Systems Workshop (VideoRecSys) 2024.
It was organized by: Khushhall Chandra Mahajan, Amey Porobo Dharwadker, Saurabh Gupta and Brad Schumitsch.…
It was organized by: Khushhall Chandra Mahajan, Amey Porobo Dharwadker, Saurabh Gupta and Brad Schumitsch.…
Forwarded from Тоже Паша Техник
у меня в маге идет предмет Applied AI in Blockchain and DeFi
так что вкушайте лонгрид про
- хэш-функции, ШАА и ШААА
- причем тут эллиптические кривые и че это вообще такое
- как это все применяется в шифровании
- верхнеуровневое устройство блокчейн
- как договорится, когда у всех свое мнение
- биток
- эфир
это будет честно не скам… я надеюсь…
[1/8]
так что вкушайте лонгрид про
- хэш-функции, ШАА и ШААА
- причем тут эллиптические кривые и че это вообще такое
- как это все применяется в шифровании
- верхнеуровневое устройство блокчейн
- как договорится, когда у всех свое мнение
- биток
- эфир
это будет честно не скам… я надеюсь…
[1/8]
Forwarded from Тоже Паша Техник
Есть какой то черный ящик, который превращает любое сообщение в уникальный набор ноликов и единичек — это хэш-функция.
Хэш-функция принимает на вход данные произвольного размера, а выдаёт «отпечаток» фиксированной длины. Именно эта особенность гарантирует целостность информации: если хоть один бит поменяется, результат сильно изменится.
То есть мы хотим, чтобы для любого сообщения генерировался его уникальный “отпечаток”.
Коллизией же называется ситуация, когда алгоритм для двух разных сообщений генерирует одинаковый хэш. Ты ему “а что это у вас”, он тебе “я думала сова”, а потом ты ему “что это у вас здесь происходит”, а он — снова “я думала сова”.
Среди множества алгоритмов, использующихся в криптографии, выделяются SHA-2 и SHA-3. (раньше часто использовали md5, но он генерирует короткие 128-битные хеши и легко подвержен коллизиям)
ШАА опирается на классическую схему Merkle–Damgård (от сюда кстати название MD5), где входное сообщение разбивается на блоки фиксированного размера, а каждый блок последовательно «сжимается» с помощью специальной компресс-функции. Такой подход хоть и надёжен, но допускает определённые уязвимости, например, атаки с удлинением сообщения.
Еще он очень похож идейно на свертки из нейронок.
Если посмотрите на картинку 1, то поймете, что хэш как бы “накапливает” знания о сообщении при этом в конце выдает в качестве итога само это состояние. И тут можно догадаться, как используется удленение сообщения.
Если коротко и верхнеуровнево: ты знаешь сообщение, ты знаешь его итоговый хэш, ты можешь просто попробовать докинуть инфы в сообщение и продолжить считать хэш. (очень грубо говоря)
ШААА (на второй картинке) лишен этого недуга так как юзеру отдается не скрытое состояние, а выжимка из него.
Алгоритм использует принцип sponge construction (губка короче).
Здесь данные сначала «впитываются» в состояние алгоритма, а затем «выжимаются» в нужном количестве бит. Считается дольше, но более безопасный алгоритм.
Переходя от преобразования данных к их защите, следующий шаг — как зашифровать и защитить сам ключ, с помощью которого можно работать с информацией.
[2/8]
Хэш-функция принимает на вход данные произвольного размера, а выдаёт «отпечаток» фиксированной длины. Именно эта особенность гарантирует целостность информации: если хоть один бит поменяется, результат сильно изменится.
То есть мы хотим, чтобы для любого сообщения генерировался его уникальный “отпечаток”.
Коллизией же называется ситуация, когда алгоритм для двух разных сообщений генерирует одинаковый хэш. Ты ему “а что это у вас”, он тебе “я думала сова”, а потом ты ему “что это у вас здесь происходит”, а он — снова “я думала сова”.
Среди множества алгоритмов, использующихся в криптографии, выделяются SHA-2 и SHA-3. (раньше часто использовали md5, но он генерирует короткие 128-битные хеши и легко подвержен коллизиям)
ШАА опирается на классическую схему Merkle–Damgård (от сюда кстати название MD5), где входное сообщение разбивается на блоки фиксированного размера, а каждый блок последовательно «сжимается» с помощью специальной компресс-функции. Такой подход хоть и надёжен, но допускает определённые уязвимости, например, атаки с удлинением сообщения.
Еще он очень похож идейно на свертки из нейронок.
Если посмотрите на картинку 1, то поймете, что хэш как бы “накапливает” знания о сообщении при этом в конце выдает в качестве итога само это состояние. И тут можно догадаться, как используется удленение сообщения.
Если коротко и верхнеуровнево: ты знаешь сообщение, ты знаешь его итоговый хэш, ты можешь просто попробовать докинуть инфы в сообщение и продолжить считать хэш. (очень грубо говоря)
ШААА (на второй картинке) лишен этого недуга так как юзеру отдается не скрытое состояние, а выжимка из него.
Алгоритм использует принцип sponge construction (губка короче).
Здесь данные сначала «впитываются» в состояние алгоритма, а затем «выжимаются» в нужном количестве бит. Считается дольше, но более безопасный алгоритм.
Переходя от преобразования данных к их защите, следующий шаг — как зашифровать и защитить сам ключ, с помощью которого можно работать с информацией.
[2/8]
Forwarded from Тоже Паша Техник
Если хэш-функции — это способ зафиксировать данные, то шифрование помогает сохранить их секретность.
Симметричное шифрование использует один и тот же секретный ключ для шифрования и дешифрования. Это как иметь один замок, ключ от которого знают только отправитель и получатель.
Звучит просто и безопасно, пока не задумываешься над тем “а как все таки передать этот ключ”.
Шифр Цезаря на этом и был основан. Есть ключ — количество сдвигов в алфавите. Ключ знают оба участника общения. И если бы партизаны, узнавшие ключ, знали, что Цезарь использует шифр Цезаря (могли бы так то догадаться лол), то спокойно бы расшифровали сообщение.
Асимметричное шифрование решает эту проблему, используя пару ключей: публичный и приватный.
Публичный ключ можно свободно распространять, а приватный хранить в секрете. Именно благодаря такому разделению можно не только шифровать сообщения, но и создавать цифровые подписи.
Одним из классических примеров асимметричной криптографии является RSA. Основная идея RSA заключается в том, что вычислить произведение двух больших простых чисел легко, а разложить (факторизовать) его обратно на множители — практически невозможно при современных вычислительных мощностях.
Генерация ключей в RSA начинается с выбора двух больших простых чисел, после чего вычисляются их произведение и функция Эйлера. В итоге получается пара ключей, где публичный используется для шифрования, а приватный — для дешифрования.
А есть еще круче? Конечно есть блин)
Самая интересная тема по-моему дальше
[3/8]
Симметричное шифрование использует один и тот же секретный ключ для шифрования и дешифрования. Это как иметь один замок, ключ от которого знают только отправитель и получатель.
Звучит просто и безопасно, пока не задумываешься над тем “а как все таки передать этот ключ”.
Шифр Цезаря на этом и был основан. Есть ключ — количество сдвигов в алфавите. Ключ знают оба участника общения. И если бы партизаны, узнавшие ключ, знали, что Цезарь использует шифр Цезаря (могли бы так то догадаться лол), то спокойно бы расшифровали сообщение.
Асимметричное шифрование решает эту проблему, используя пару ключей: публичный и приватный.
Публичный ключ можно свободно распространять, а приватный хранить в секрете. Именно благодаря такому разделению можно не только шифровать сообщения, но и создавать цифровые подписи.
Одним из классических примеров асимметричной криптографии является RSA. Основная идея RSA заключается в том, что вычислить произведение двух больших простых чисел легко, а разложить (факторизовать) его обратно на множители — практически невозможно при современных вычислительных мощностях.
Генерация ключей в RSA начинается с выбора двух больших простых чисел, после чего вычисляются их произведение и функция Эйлера. В итоге получается пара ключей, где публичный используется для шифрования, а приватный — для дешифрования.
А есть еще круче? Конечно есть блин)
Самая интересная тема по-моему дальше
[3/8]
Forwarded from Тоже Паша Техник
В основе современных криптографических систем лежит не только арифметика, но и элегантная геометрия эллиптических кривых.
Эллиптическая кривая задаётся уравнением вида:
y^2 = x^3 + ax + b.
при этом важно, чтобы дискриминант не обращался в ноль — это гарантирует гладкость кривой.
сама кривая есть на первой картинке
Здесь операция сложения точек на кривой определяется весьма своеобразно: для сложения двух разных точек P и Q проводится прямая через них, а затем найденная третья точка отражается относительно оси x.
На картинке показано как получается результат P+Q=R’
При удвоении точки применяется касательная, которая пересекается с кривой, и аналогично выполняется отражение.
На картинке 2*P=S’
Для криптографических применений, таких как формирование ключей, вычисления ведутся не над вещественными числами, а в конечных полях (например, GF(p)).
Если кратко, то конечное поле, это штука, где все операции выполняются по модулю p. То есть уравнение будет вида:
y^2 mod p = (x^3 + ax + b) mod p.
Точек в кадрате p*p будет p-1 или около того (я забыл если честно).
На второй картинке показан пример такого поля. И тут тоже есть геометрическая интерпретация для сложения.
Нахера нам эти поля и кривые?
В криптографии важно, чтобы все вычисления были дискретными (то есть, с целыми числами) и имели ограниченное число вариантов. Это позволяет избежать проблем с точностью и сделать вычисления эффективными.
Конечные поля позволяют нам выполнять операции по модулю, которые позволяют нам производить вычисления достаточно легко в одну сторону и почти не обратимо в обратную.
Вот пример:
3^3 mod 17 = 27 mod 17 = 10
При этом, если мы не знаем степень, то получить x можно только перебрав кучу не верных кандидатов:
3^x mod 17 = 12 — найдите x…
Если что, ответ 29 🙂
Аналогично, в эллиптических кривых используется операция, которая записывается как
Q = d * G,
где G — базовая точка, а d — приватный ключ (по сути тот самый x, который нереально найти при наших вычислительных ресурсах).
Эта операция представляет собой повторное сложение точки G с собой d раз и является аддитивным аналогом возведения в степень.
То есть у нас есть операция, которую легко выполнить в одну сторону, но почти не реально в другую сторону (при больших d и p (прям оооочень больших))
Эти операции лежат в основе ECDSA — алгоритма цифровой подписи на эллиптических кривых. При генерации ключей выбирается базовая точка G с большим простым порядком p. Приватный ключ d — случайное число, а публичный вычисляется как Q = d * G
пример на картинке 3.
Задача восстановления d по Q сводится к поиску дискретного логарифма — математической проблеме, которую решить практически невозможно без перебора (то что описано выше).
От криптографических примитивов мы переходим к тому, как всё это используется для создания целостных систем хранения данных.
А вот здесь тыц можно поиграть с элиптическими кривыми и посмотреть как появляются точки P, Q и R.
[4/8]
Эллиптическая кривая задаётся уравнением вида:
y^2 = x^3 + ax + b.
при этом важно, чтобы дискриминант не обращался в ноль — это гарантирует гладкость кривой.
сама кривая есть на первой картинке
Здесь операция сложения точек на кривой определяется весьма своеобразно: для сложения двух разных точек P и Q проводится прямая через них, а затем найденная третья точка отражается относительно оси x.
На картинке показано как получается результат P+Q=R’
При удвоении точки применяется касательная, которая пересекается с кривой, и аналогично выполняется отражение.
На картинке 2*P=S’
Для криптографических применений, таких как формирование ключей, вычисления ведутся не над вещественными числами, а в конечных полях (например, GF(p)).
Если кратко, то конечное поле, это штука, где все операции выполняются по модулю p. То есть уравнение будет вида:
y^2 mod p = (x^3 + ax + b) mod p.
Точек в кадрате p*p будет p-1 или около того (я забыл если честно).
На второй картинке показан пример такого поля. И тут тоже есть геометрическая интерпретация для сложения.
Нахера нам эти поля и кривые?
В криптографии важно, чтобы все вычисления были дискретными (то есть, с целыми числами) и имели ограниченное число вариантов. Это позволяет избежать проблем с точностью и сделать вычисления эффективными.
Конечные поля позволяют нам выполнять операции по модулю, которые позволяют нам производить вычисления достаточно легко в одну сторону и почти не обратимо в обратную.
Вот пример:
3^3 mod 17 = 27 mod 17 = 10
При этом, если мы не знаем степень, то получить x можно только перебрав кучу не верных кандидатов:
3^x mod 17 = 12 — найдите x…
Если что, ответ 29 🙂
Аналогично, в эллиптических кривых используется операция, которая записывается как
Q = d * G,
где G — базовая точка, а d — приватный ключ (по сути тот самый x, который нереально найти при наших вычислительных ресурсах).
Эта операция представляет собой повторное сложение точки G с собой d раз и является аддитивным аналогом возведения в степень.
То есть у нас есть операция, которую легко выполнить в одну сторону, но почти не реально в другую сторону (при больших d и p (прям оооочень больших))
Эти операции лежат в основе ECDSA — алгоритма цифровой подписи на эллиптических кривых. При генерации ключей выбирается базовая точка G с большим простым порядком p. Приватный ключ d — случайное число, а публичный вычисляется как Q = d * G
пример на картинке 3.
Задача восстановления d по Q сводится к поиску дискретного логарифма — математической проблеме, которую решить практически невозможно без перебора (то что описано выше).
От криптографических примитивов мы переходим к тому, как всё это используется для создания целостных систем хранения данных.
А вот здесь тыц можно поиграть с элиптическими кривыми и посмотреть как появляются точки P, Q и R.
[4/8]