Привет, Роман! Спасибо за классную статью. А работаете ли вы в направлении понимания видео, в частности для анализа длинных видео, причем не только в речевом домене, но и в визуальном, с помощью LLM?
Все так. Более того, в одной языковой группе есть множество региональных диалектов, которые могут отличаться между собой (например: московский и новосибирский диалекты РЖЯ).
К счастью, нет. Она была разделена на две части: 1) теоретические вопросы по комп. зрению (детекция, классификация, сегментация) и немного по базе глубокого обучения. 2) System Design кейс: «есть такая-то система с камерами, нужно сделать то-то». На понимание как строить полный пайплайн от сбора и разметки данных до выбора правильных алгоритмов, использования нейросетей в условиях разных ограничений на тип камеры, объем хранение данных, скорость работы алгоритмов, канал связи и т.д. и т.п.
Поделюсь своим опытом, летом собеседовался на позицию тимлида в ML. Обещали три секции - 1) код 2) прикладной ML 3) лидершип (скатали у Amazon лидершип принципы и всю методику).
Итак:
Код: две задачи уровня медиум литкод. Решил за 45 минут, даже осталось много времени, собеседующий сказал, что на этом всё, можем просто поболтать.
ML: секция на компьютерное зрение. Собеседующий явно не знал классические алгоритмы и предлагал построить систему исключительно на нейронках. Но договориться удалось, секция пройдена.
Лидершип: это секция булшит-вопросов в стиле «на вас орет начальник, команда вас ненавидит и устраивает гражданскую войну, ваши действия?». Был готов к ней и прошел идеально. На что получил максимально позитивный фидбек, но оценку немного снизили по причине, цитирую «скорее всего в FAANG готовился». Ха-ха.
И тут нужно было ждать финал и оффер? Как же. А давайте еще АА секцию пройдём? Алгоритмы. Причем я уточнял не раз, мне правда на позиции тимлида придется КОДИТЬ? Алгоритмы? Ну ок, не бросать же. И четвертую секцию я завалил (решил 1 задачу из 2), тк совершенно был не готов к задаче на дерево, внутри которого нужно было найти все одинаковые подмножества букв, образующиеся проходом по под-дереву). А проходной фильтр это 2/2 задач.
В итоге начались качели на два месяца из серии берем/не берем, и закончилось это фразой «ну мы можем показать другим командам, где АА секция не важна». Не интересно абсолютно.
И это не конец. Недавно пришел рекрутер в личку и предлагает пройти 5 собесов заново!! Я ему говорю — уже проходил 3 таких, вы же даже фидбеки видите. А мне в ответ — «да, вижу, хорошо прошли, но это другой Яндекс, давай заново». Смеяться или плакать?
Переход от классической сегментации к матингу не так-то прост:
Задача матирования в принципе сложнее обычной сегментации,
Разметить качественно данные под задачу матинга нетривиально, а обучить толокеров рисовать маски намного проще. Мы пробовали получать pixel-perfect, но это все равно не матинг,
Сетки для сегментации проще и быстрее, их можно вытащить в реал-тайм, а с матингом такого сходу не получится (несмотря на готовые решения типа RVM).
Сегментация позволяет сразу решать несколько задач - вырезание фона, бьютификация и т.п., через матирование придется декомпозировать обработку (что опять же усложнит и замедлит финальное решение).
Да, проводили такой анализ. Выиграла схема: оптимальное перекрытие = 3 (в худшем случае 5), без последующей валидации разметки. Это оказалось и дешевле и намного точнее по качеству. Самописные алгоритмы усреднения боксов + предсказание хорошей нейронкой (как доп. уверенность при усреднении) дают очень неплохое качество и не требуют валидации. Совсем спорные кейсы после методов агрегации просто отбрасывали, но это единицы % от всего датасета.
Сейчас такая задача не ставилась, но мы ей активно занимаемся. Основное отличие от представленной статьи в том, что язык жестов - динамический, поэтому статичные картинки не совсем подходят для ее решения.
В будущих релизах обязательно планируем опубликовать результаты по исследованию языка жестов.
Найти прикладное применение для таких длинных БПФ непросто, но оно есть: астрономия (в задачах спектрометрии частоты дискретизации начинаются от гигагерц), медицина (ЭЭГ, например). В классической радиотехнике тоже можно использовать. Я делал сверхдлинный БПФ для задачи радиоприема (к сожалению, ответить подробнее не могу).
Вы правы — для таких длин БПФ нужна очень высокая точность промежуточных вычислений, в частности для поворачивающих множителей. С одной стороны, для этого можно использовать нестандартные самописные floating-point вычислители, у которых мантисса шире, чем у double. Или все вычисления проводить в fixed-point с линейным ростом разрядности от бабочки к бабочке (а в FPGA это сделать проще, чем в floating-point). С другой стороны — я не могу придумать реальную задачу, где действительно была бы нужна такая точность, поэтому промежуточные результаты вычислений и хранимые поворачивающие множители можно округлять.
Зайду с обратной стороны: для того, чтобы вычислить K-точечное БПФ, необходимо получить сумму всех пачек по K отсчетов. А чтобы это сделать — нужно пройти всю последовательность N. И так для каждой следующей пачки длины K на выходе.
Прошу прощения, я неправильно понял назначение D на этой картинке. Тут D отвечает за степень параллелизма подачи входных данных, если D = 1, то все будет работать, просто будет поступать 1 отсчет за такт, а не D.
Но это дополнительная полифазная обработка (например, когда у вас частота дискретизации 4 ГГц, а в ПЛИС вы можете работать только на 400 МГц, тогда D = 10). То есть это просто аспект реализации на скорость обработки в FPGA.
Таким образом, на add стадию после overlap этот D не влияет: вам все равно придется ждать всю последовательность, чтобы произвести суммирование.
3) Да, схема правильная.
Смотрите: на вход поступает D = K * M отсчетов. Они разбиваются на последовательности M по K сэмплов. Затем сумируются и вычисляется БПФ (поворот фазы опустим, он необязателен). На выходе получаете пачку длины K. Чтобы получить вторую пачку данных длины K нужно снова набрать и обработать D = K * M.
2) Если не задать окно или выбрать его неправильно — то возможна ситуация потери гармоник.
3) Возможно, я некорректно выразился. WOLA может работать в реал-тайме, то есть может получать новые отсчеты на каждом такте. Но выдавать результат пользователю будет в соответствии с разбиением исходной последовательности с периодом M = N / K. В алгоритме сверхдлинного БПФ — результат приходит и уходит на каждом такте.
4) Продуктовая. Описанный в статье метод применяется в реальных задачах. К сожалению, не могу раскрывать детали из-за NDA.
По сути дальнейшее разложение приведет к «разворачиванию» схемы до элементарной бабочки (Radix-2, например). То есть изначальная конвейерная схема соединения «бабочка — узел перестановки» превратится в многомерную (параллельную?) форму, где бабочки будут только Radix-2, а узлы кросс-коммутации разложатся по памяти, но это выглядит нереализуемым по ресурсам ПЛИС.
Для примера взять БПФ N = 8. В одномерном случае это 3 стадии бабочек. На каждой стадии выполнится четыре Radix-2 операции. В сумме — 12 операций. В двумерном случае N = K1 * K2 = 4 * 2. Для K1 надо 8 операций, для K2 = 4. Итого 12 операций. Для трехмерного БПФ получаем элементарный куб K1 * K2 * K3 = 2 * 2 * 2, который тоже выполняет 12 операций. Но в многомерном случае приходится где-то хранить всю выборку N после прохода по одному измерению (и столько раз по числу измерений).
Да, WOLA FFT (или полифазные схемы БПФ) я применял в других проектах. «Супер-разрешение» достаточно опасное понятие в этом плане, поскольку отражается только в визуальном улучшении качества спектра, а не в настоящей разрешающей способности по частоте.
На результирующих спектрах после WOLA в некоторых случаях хорошо видны усредненные гармоники с сравнении с обычным БПФ, оно и понятно — увеличение времени наблюдения дает больше информации. Но разрещающая способность по частоте fs/N остается прежней! А для очень близких гармоник может произойти их наложение из-за применения оконной функции (расширяется главный лепесток спектра). Здесь подробно обсуждались нюансы WOLA в задачах Super-Resolution, а тут — теория.
Все эти свойства я описывал в своей последней лекции по ЦОС. Вот графики:
Эффекты:
1) Потеря первой гармоники из-за некратности фазы при разбиении сигнала N на M пачек длины K (FFT lenght = K).
2) С фазой все хорошо -график приличный.
3) Переход к наложению оконной функции, если сигналы далеко — все хорошо.
4) Неверный выбор оконной функции. Слипание из-за наложения окна.
5) Без оконной функции, но с фазами снова все хорошо.
6) Сдвигаем еще ближе, выполняя условие по фазам. Ура. Super-resolution.
Кроме того, WOLA — не честный реал-тайм и выдает спектр с периодом M = N / K.
Применять этот метод следует очень аккуратно и поставленную задачу он не решает.
Аттракторы — очень интересная тема. На базе простых ОДУ в зависимости от начальных условий получаются совершенно разные траектории движения, при этом сохраняются свойства поведения. В свое время писал диссер по использованию аттракторов в задачах радиолокации на базе сверхширокополосных хаотических сигналов. Автокорреляционные функции аттракторов, похожи на АКФ белого шума (большой пик в нуле), что позволяет применять их в этих задачах.
Если интересно, основные аттракторы постарался классифицировать в своем репозитории на гитхабе.
Рекомендую к прочтению адаптированную статью, УФН от 2006 года "О пропускной способности эфира и проволоки в электросвязи", в которой содержатся все семь теорем Котельникова. Это адаптированный вариант оригинальных трудов Котельникова. Добавил её в репозиторий.
Привет, Роман! Спасибо за классную статью. А работаете ли вы в направлении понимания видео, в частности для анализа длинных видео, причем не только в речевом домене, но и в визуальном, с помощью LLM?
Спасибо за комментарий! Статистика у нас есть, в следующей версии на сайт доедут слова с учётом частотности их использования.
Все так. Более того, в одной языковой группе есть множество региональных диалектов, которые могут отличаться между собой (например: московский и новосибирский диалекты РЖЯ).
К счастью, нет. Она была разделена на две части: 1) теоретические вопросы по комп. зрению (детекция, классификация, сегментация) и немного по базе глубокого обучения. 2) System Design кейс: «есть такая-то система с камерами, нужно сделать то-то». На понимание как строить полный пайплайн от сбора и разметки данных до выбора правильных алгоритмов, использования нейросетей в условиях разных ограничений на тип камеры, объем хранение данных, скорость работы алгоритмов, канал связи и т.д. и т.п.
Поделюсь своим опытом, летом собеседовался на позицию тимлида в ML. Обещали три секции - 1) код 2) прикладной ML 3) лидершип (скатали у Amazon лидершип принципы и всю методику).
Итак:
Код: две задачи уровня медиум литкод. Решил за 45 минут, даже осталось много времени, собеседующий сказал, что на этом всё, можем просто поболтать.
ML: секция на компьютерное зрение. Собеседующий явно не знал классические алгоритмы и предлагал построить систему исключительно на нейронках. Но договориться удалось, секция пройдена.
Лидершип: это секция булшит-вопросов в стиле «на вас орет начальник, команда вас ненавидит и устраивает гражданскую войну, ваши действия?». Был готов к ней и прошел идеально. На что получил максимально позитивный фидбек, но оценку немного снизили по причине, цитирую «скорее всего в FAANG готовился». Ха-ха.
И тут нужно было ждать финал и оффер? Как же. А давайте еще АА секцию пройдём? Алгоритмы. Причем я уточнял не раз, мне правда на позиции тимлида придется КОДИТЬ? Алгоритмы? Ну ок, не бросать же. И четвертую секцию я завалил (решил 1 задачу из 2), тк совершенно был не готов к задаче на дерево, внутри которого нужно было найти все одинаковые подмножества букв, образующиеся проходом по под-дереву). А проходной фильтр это 2/2 задач.
В итоге начались качели на два месяца из серии берем/не берем, и закончилось это фразой «ну мы можем показать другим командам, где АА секция не важна». Не интересно абсолютно.
И это не конец. Недавно пришел рекрутер в личку и предлагает пройти 5 собесов заново!! Я ему говорю — уже проходил 3 таких, вы же даже фидбеки видите. А мне в ответ — «да, вижу, хорошо прошли, но это другой Яндекс, давай заново». Смеяться или плакать?
Желаю успехов Яндексу в найме.
Переход от классической сегментации к матингу не так-то прост:
Задача матирования в принципе сложнее обычной сегментации,
Разметить качественно данные под задачу матинга нетривиально, а обучить толокеров рисовать маски намного проще. Мы пробовали получать pixel-perfect, но это все равно не матинг,
Сетки для сегментации проще и быстрее, их можно вытащить в реал-тайм, а с матингом такого сходу не получится (несмотря на готовые решения типа RVM).
Сегментация позволяет сразу решать несколько задач - вырезание фона, бьютификация и т.п., через матирование придется декомпозировать обработку (что опять же усложнит и замедлит финальное решение).
Спасибо за позитивный фидбек!
Да, проводили такой анализ. Выиграла схема: оптимальное перекрытие = 3 (в худшем случае 5), без последующей валидации разметки. Это оказалось и дешевле и намного точнее по качеству. Самописные алгоритмы усреднения боксов + предсказание хорошей нейронкой (как доп. уверенность при усреднении) дают очень неплохое качество и не требуют валидации. Совсем спорные кейсы после методов агрегации просто отбрасывали, но это единицы % от всего датасета.
Сейчас такая задача не ставилась, но мы ей активно занимаемся. Основное отличие от представленной статьи в том, что язык жестов - динамический, поэтому статичные картинки не совсем подходят для ее решения.
В будущих релизах обязательно планируем опубликовать результаты по исследованию языка жестов.
Можно посмотреть здесь
Но это дополнительная полифазная обработка (например, когда у вас частота дискретизации 4 ГГц, а в ПЛИС вы можете работать только на 400 МГц, тогда D = 10). То есть это просто аспект реализации на скорость обработки в FPGA.
Таким образом, на add стадию после overlap этот D не влияет: вам все равно придется ждать всю последовательность, чтобы произвести суммирование.
Смотрите: на вход поступает D = K * M отсчетов. Они разбиваются на последовательности M по K сэмплов. Затем сумируются и вычисляется БПФ (поворот фазы опустим, он необязателен). На выходе получаете пачку длины K. Чтобы получить вторую пачку данных длины K нужно снова набрать и обработать D = K * M.
3) Возможно, я некорректно выразился. WOLA может работать в реал-тайме, то есть может получать новые отсчеты на каждом такте. Но выдавать результат пользователю будет в соответствии с разбиением исходной последовательности с периодом M = N / K. В алгоритме сверхдлинного БПФ — результат приходит и уходит на каждом такте.
4) Продуктовая. Описанный в статье метод применяется в реальных задачах. К сожалению, не могу раскрывать детали из-за NDA.
Для примера взять БПФ N = 8. В одномерном случае это 3 стадии бабочек. На каждой стадии выполнится четыре Radix-2 операции. В сумме — 12 операций. В двумерном случае N = K1 * K2 = 4 * 2. Для K1 надо 8 операций, для K2 = 4. Итого 12 операций. Для трехмерного БПФ получаем элементарный куб K1 * K2 * K3 = 2 * 2 * 2, который тоже выполняет 12 операций. Но в многомерном случае приходится где-то хранить всю выборку N после прохода по одному измерению (и столько раз по числу измерений).
Например, в астрономии в задачах спектроскопии.
На результирующих спектрах после WOLA в некоторых случаях хорошо видны усредненные гармоники с сравнении с обычным БПФ, оно и понятно — увеличение времени наблюдения дает больше информации. Но разрещающая способность по частоте fs/N остается прежней! А для очень близких гармоник может произойти их наложение из-за применения оконной функции (расширяется главный лепесток спектра). Здесь подробно обсуждались нюансы WOLA в задачах Super-Resolution, а тут — теория.
Все эти свойства я описывал в своей последней лекции по ЦОС. Вот графики:
Эффекты:
1) Потеря первой гармоники из-за некратности фазы при разбиении сигнала N на M пачек длины K (FFT lenght = K).
2) С фазой все хорошо -график приличный.
3) Переход к наложению оконной функции, если сигналы далеко — все хорошо.
4) Неверный выбор оконной функции. Слипание из-за наложения окна.
5) Без оконной функции, но с фазами снова все хорошо.
6) Сдвигаем еще ближе, выполняя условие по фазам. Ура. Super-resolution.
Кроме того, WOLA — не честный реал-тайм и выдает спектр с периодом M = N / K.
Применять этот метод следует очень аккуратно и поставленную задачу он не решает.
Если интересно, основные аттракторы постарался классифицировать в своем репозитории на гитхабе.