Алгоритмы *

Google представила открытую библиотеку jpegli с реализацией кодировщика и декодировщика изображений в формате JPEG.

Библиотека включает дополнительные оптимизации для повышения эффективности кодирования, позволяющие на 35% увеличить степень сжатия высококачественных изображений, по сравнению с традиционными кодеками JPEG.

В сравнении с libjpeg-turbo проект jpegli позволяет добиться аналогичного уровня качества при снижении битрейта на 32%. На уровне API и ABI библиотека полностью совместима с libjpeg62 и может применяться для её прозрачной замены. Код jpegli написан на языке С++ и распространяется под лицензией BSD.

Библиотека jpegli позволяет кодировать изображения с выделением 10 и более битов на цветовой компонент. При этом результат работы алгоритмов кодирования адаптируется для традиционной для формата JPEG модели, допускающей использование только 8 бит на цветовой компонент. Подобная особенность позволяет сохранить совместимость с уже существующими декодировщиками, рассчитанными на 8-битовое представление цветовых составляющих.

Кодируемые при помощи jpegli изображения полностью соответствуют стандарту JPEG, не требуют специфичных декодировщиков и могут просматриваться в существующих просмотрщиках JPEG и веб‑браузерах. Применение для распаковки изображений, сжатых при помощи jpegli, собственного декодировщика позволяет добиться дополнительного снижения артефактов. Скорость кодирования при помощи jpegli сопоставима с библиотеками libjpeg‑turbo и MozJPEG.

Источник: OpenNET.

Фильтры Throttling VS Debounce

Оказывается, они работают по-разному )

Еще посты об IT в ИТ БД → t.me/it_bd

Оба этих фильтра используются для того, чтобы не дублировать события.

Например, пользователь злостно и быстро кликает на кнопку «Обновить» десять раз подряд.

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

В этом случае нужно отфильтровать лишние события, то есть пропустить лишние клики, обработав лишь 1 событие.

И тут есть два подхода:

• Throttling  — пропускает первое событие и игнорирует остальные N миллисекунд

  Например, если установить Throttling = 500мс, то обработается первый клик, а все следующие 500мс клики будут игнорироваться.

• Debounce  — отсчитывает N миллисекунд после последнего события и только после этого пропускает последнее событие.

  Например, если установить Debounce = 500мс, то клики будут игнорироваться, пока пользователь не сделает перерыв в 500мс. После 500мс простоя последнее событие обработается.

_{остальные посты}

❓100 Вопросов по Машинному обучению (Machine Learning) - Вопрос_14 (Часть_2)

1. Регуляризация (Regularization): Использование методов регуляризации, таких как L1 или L2 регуляризация, может помочь снизить переобучение и улучшить стабильность модели. Регуляризация контролирует сложность модели и снижает чувствительность к малым изменениям в данных.

   t.me/DenoiseLAB (Еесли вы хотите быть в курсе всех последних новостей и знаний в области анализа данных);

❓100 Вопросов по Машинному обучению (Machine Learning) - Вопрос_12

🔠Вопрос_12: Expectation-Maximization (EM) ?

Expectation-Maximization (EM) - это итерационный алгоритм, который используется для оценки параметров вероятностных моделей, когда некоторые данные являются наблюдаемыми, а другие данные являются скрытыми или неполными. EM-алгоритм часто применяется в статистике и машинном обучении для обучения моделей с неизвестными параметрами.

EM-алгоритм состоит из двух основных шагов: шага ожидания (Expectation) и шага максимизации (Maximization).

1. Шаг ожидания (Expectation step, E-шаг): На этом шаге вычисляются ожидаемые значения скрытых переменных (или "ответственностей") в соответствии с текущими значениями параметров модели. Это делается путем вычисления условного математического ожидания скрытых переменных при условии наблюдаемых данных и текущих параметров модели.

2. Шаг максимизации (Maximization step, M-шаг): На этом шаге обновляются параметры модели, чтобы максимизировать ожидаемое правдоподобие, полученное на E-шаге. Обновление параметров происходит путем решения оптимизационной задачи, которая может включать максимизацию правдоподобия или минимизацию ошибки между наблюдаемыми данными и ожидаемыми значениями.

   t.me/DenoiseLAB (Еесли вы хотите быть в курсе всех последних новостей и знаний в области анализа данных);

   https://boosty.to/denoise_lab (Если вы хотите поддержать проект, или получить более модные фишки по коду и продвижению подписывайтесь).

❓100 Вопросов по Машинному обучению (Machine Learning) - Вопрос_6

🔠Вопрос_6: Всегда ли PCA спасает от проблеммы "проклятие размерности" и если нет, то что можно использовать вместо него ?

✔️Ответ:
РСА не всегда спасает от проклятия размерности, однако существует несколько продвинутых алгоримов для решения данной проблеммы:

• t-SNE (t-Distributed Stochastic Neighbor Embedding): Этот алгоритм позволяет визуализировать данные высокой размерности в двух или трех измерениях, сохраняя при этом их локальную и глобальную структуру. Он основан на вероятностной модели, которая пытается сохранить близость между объектами в исходном пространстве и их представлением в пространстве меньшей размерности.

• LLE (Locally Linear Embedding): LLE ищет линейные зависимости между соседними точками данных и пытается сохранить эти зависимости при снижении размерности. Алгоритм строит локальные линейные модели для каждой точки данных и затем находит низкоразмерное представление, которое наилучшим образом воспроизводит эти локальные модели.

• UMAP (Uniform Manifold Approximation and Projection): UMAP является относительно новым алгоритмом снижения размерности, который сочетает в себе методы локальной связности и глобальной структуры данных. Он строит граф связности между точками данных и затем находит низкоразмерное представление, которое сохраняет геометрическую структуру данных.

  Кроме того, в ряде задач применяются: Isomap, MDS, Random Projection, Sparse Coding, NMF.

  https://t.me/DenoiseLAB
  

Youtube-канал ones and zeros опубликовал визуализации нахождения маршрута между двумя точками в реальных городах (Чикаго и Рим) при помощи A*. Алгоритм A* — это рекурсивный алгоритм поиска пути в графах на основе эвристик, изобретённый в 1968 году как усовершенствованная версия алгоритма Дейкстры. Этот алгоритм активно применяется в разработке игр.

Статья про A* в Википедии: ссылка

Пара статей на Хабре с объяснением работы алгоритма: 1, 2

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

Цель - найти все оптимумы, не вычисляя производные. Пусть задано два начальных приближения a, b. Первый шаг алгоритма: найти решение линеаризованной задачи наименьших квадратов в этом направлении. В результате получится точка c. Второй шаг алгоритма: решить задачу линейного поиска относительно угла. Развернем вектор bc на такой угол, в котором значение целевой функции станет локально минимальным. Для решения этой задачи можно использовать метод парабол, если вычислить значения целевой функции при развороте вектора, скажем, на ±5° и приблизить зависимость от угла многочленом второй степени. Далее полученная точка становится вторым приближением, а второе приближение с предыдущего шага - первым.

Метод вырезает на плоскости треугольники, в которых не должно оказаться оптимума, хотя этот вопрос открыт. Таким образом, запустив алгоритм из всех углов объемлющего прямоугольника, можно получить информацию о том, где уже не следует искать оптимумы. Алгоритм удобен нормированностью углов и может быть обобщен на более высокие размерности.

Вакуум популярности

Сейчас рекомендательные алгоритмы социальных сетей и медиа настолько крутые и умные, что реально подсовывают тот контент, который нам интересен и релевантен в данный момент.

Из-за этого может сложиться мнение о каком-то информационном шуме, которого по факту нет. Точнее он есть, но только у определенной аудитории. И потом человек в беседе с друзьями говорит «Даааа, крутую фичу встроили в новый iPhone!» А его друзья хлопают глазами и вообще не в контексте.

А дело все в том, что главный персонаж этой истории пользуется продуктами Apple, подписан на блогеров, которые делают обзоры этой техники, читает новости об этом и подписан на паблики компании в социальных сетях. А его друзья пользуются Самсунгами, смотрят фильмы Кубрика и читают лонгриды про ЗОЖ (все совпадения партеров ЦА случайны 🙃).

Поэтому стоит держать у себя в голове, что какой-то информационный шум или повод может быть (даже скорее всего не является) не общим, а локальным, только для одной конкретной ЦА. И это инструмент маркетинга, который нужно использовать 😉 Можно называть это «прогревом», конечно, а можно «вакуум популярности продукта/бренда/персоны».

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

Про математические основы самого подхода вычисления контрольного числа писать не буду, кому интересно, можно почитать например тут: The Mathematics of Identification Numbers.

В частности в статье отмечалось, что классический алгоритм Луна не выявляет некоторые типы ошибок, например ошибку перестановки чисел 09->90. Есть же и другие и другие распространенные типы ошибок и подходы к их выявлению.

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

Возможно, что кому-то это станет полезным при проектировании систем контроля данных или проектирования интерфейсов.

Собеседование по алгоритмам: разноцветные соседи

Есть двадцать клеток, каждая из которых либо белая, либо чёрная. Известно, что самая левая клетка имеет белый цвет, а самая правая — чёрный. Цвета всех остальных клеток скрыты. Вы можете кликнуть на любую клетку, чтобы узнать её цвет. Ваша цель — найти пару соседних клеток разных цветов. Попробуйте!

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

Оказывается, можно найти такую пару всего за пять кликов! Сможете?

Опубликую решение в комментариях через пару дней.