1 of 48

Lecture 4.

t-SNE, UMAP

2 of 48

Общая идея.

t-SNE

Не все данные мы можем разделить с помощью линейных методов уменьшения размерности…

3 of 48

Изначальные данные

t-SNE

Видим на картинке 3 хорошо различимых кластера.

​

Для простоты будет отображать 2-мерное пространство в 1-мерное

4 of 48

Шаг 1.

t-SNE

Мы выбрали одну из точек датасета. И для другой выбранной нами точки посчитаем евклидово расстояние до неё.

5 of 48

Шаг 1.

t-SNE

Вычисление совместного распределения вероятностей, которое представляет сходства между точками данных

Но что значит сходство?

В оригинальной статье написано:

similarity of datapoint xⱼ to datapoint xᵢ is the conditional probability p_{j|i}, that xᵢ would pick xⱼ as its neighbor.

6 of 48

Шаг 1. С математикой…

t-SNE

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

​

Вероятность того, что xᵢ соседствует с xⱼ.

7 of 48

Шаг 1. С математикой…

t-SNE

Зачем в формуле деление?

8 of 48

Шаг 1. С математикой…

t-SNE

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

9 of 48

Шаг 1. С математикой…

t-SNE

Откуда в формуле дисперсия?

Это гиперпараметр - perplexity.

По сути это целевое значение количества соседей центральной точки.

Так мы сможем учесть и плотные и разреженные кластеры!

Примеры влияния на результаты

будут дальше :)

10 of 48

Шаг 1. С математикой…

t-SNE

11 of 48

Шаг 1. С математикой…

t-SNE

NO!

В итоге возьмем:

12 of 48

Шаг 2.

t-SNE

Создадим набор точек в целевом пространстве измерений и вычислим для них совместного распределения вероятностей.

Изначально нужно как-то случайно расположить точки в этом пространстве.

13 of 48

Шаг 2.

t-SNE

У нормального распределения “короткие хвосты”...

Поэтому решили использовать распределение Стьюдента с 1 степенью свободы.

14 of 48

Шаг 2.

t-SNE

Расстояния в низкоразмерном пространстве:

15 of 48

Шаг 3.

t-SNE

В оригинальной статье говорится, что расстояния должны быть proportional to probability density under a Gaussian centered at xᵢ. (Картинка для ранее выделенной точки)

16 of 48

Шаг 3.

t-SNE

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

17 of 48

Шаг 3.

t-SNE

Подсчитаем так для первой точки и сделаем для всех остальных точек то же самое.

18 of 48

Небольшое отступление.

t-SNE

Будем пытаться оптимизировать дивергенцию Кульбака-Лейблера:

19 of 48

Небольшое отступление.

t-SNE

Градиент рассчитывается для каждой точки и описывает, насколько сильно её стоит “оттолкнуть” и в каком направлении.

20 of 48

Конец? Примеры 1

t-SNE

21 of 48

Конец? Примеры 2

t-SNE

22 of 48

Конец? Примеры 3

t-SNE

23 of 48

Конец? Примеры 4

t-SNE

24 of 48

PCA vs t-SNE

t-SNE

25 of 48

PCA vs t-SNE

t-SNE

26 of 48

PCA vs t-SNE

t-SNE

27 of 48

Шаги похожи на t-SNE…

UMAP

Шаг 1. Построение графа расстояний, для k-1 ближайшего соседа.

Взвешиваем рёбра на основе расстояний.

28 of 48

Шаги похожи на t-SNE…

UMAP

Шаг 1. Получаем similarity score, основываясь на функции, где нам надо подобрать параметр сигма

​

Далее можем посчитать расстояние между точками:

29 of 48

Шаги похожи на t-SNE…

UMAP

Шаг 1. Для каждого элемента получаем свои similarity scores, которые могут быть асимметричны

Для симметричности используем

​

30 of 48

Шаги похожи на t-SNE…

UMAP

Шаг 2. Переносим точки в низкоразмерное пространство и высчитываем расстояния в нём.

​

​

31 of 48

Шаги похожи на t-SNE…

UMAP

Шаг 3. Аналогичен шагу 3 t-SNE - используем градиентный спуск для перераспределения точек. Но тут также накладывается условие на минимальное расстояние между любыми двумя точками.

32 of 48

Гиперпараметры.

UMAP

n_neigh - количество соседей, которое рассматриваем для графа.

min_dist - минимальное расстояние между любыми двумя точками в низкоразмерном пространстве.

​

​

P.S.

Количество эпох и количество компонент - тоже гиперпараметры.

33 of 48

UMAP

  • за одну эпоху одна подвижка пары элементов
  • можем варьировать расстояние минимальное между точками в низкоразмерном пространстве
  • используем нормальное распределение для исходной размерности
  • инициализация через spectral embedding

UMAP vs TSNE

TSNE

  • сразу двигаем все элементы, проходимся циклом
  • фиксированная формула для вычисления расстояния в низкоразмерном пр-ве
  • используем подбор параметра сигма в логарифме
  • случайная инициализация

34 of 48

Примеры.

UMAP

35 of 48

Примеры.

UMAP

UMAP

t-SNE

LargeVis

Laplacian Eigenmaps

PCA

36 of 48

Примеры.

UMAP

37 of 48

Наш мамонтяра.

UMAP

38 of 48

Наш мамонтяра.

UMAP

39 of 48

Bias-Variance tradeoff concept.

Best Practices

40 of 48

Борьба с переобучением.

Best Practices

Переобучение - ситуация большой дисперсии ошибок.

​

Для борьбы с ним будем делить данные на 3 куска:

train - test - validate

41 of 48

Борьба с переобучением.

Best Practices

Как можно себя обезопасить?

a - Обучаем модель, удаляя часть данных

b - Обучаем модель для практического использования�

42 of 48

Оптимизация гиперпараметров.

Best Practices

Если параметров мало - используем GridSearch.

​

Если параметров много - техники оптимизации гиперпараметров.

43 of 48

Кросс-валидация.

Best Practices

Разделяем выборку на test/validate, используя метод k-fold.

​

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

44 of 48

Несбалансированные классы.

Best Practices

Используем методы Upsampling-а и Downsampling-а при необходимости.

45 of 48

Матрица ошибок.

Metrics.

46 of 48

Формулы для метрик

Metrics.

47 of 48

Ко(т)нец презентации

Далее:

More best practices and KNN

48 of 48

  • t-SNE
  • UMAP
  • k-fold CV
  • Bias-Variance tradeoff
  • Переобучение
  • Upsampling, undersampling
  • Metrics

Теоретический минимум