Алгоритмы *

❓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. Есть же и другие и другие распространенные типы ошибок и подходы к их выявлению.

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

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

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

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

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

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

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