개요

이전제가 t-SNE의 설명 글을 썼어요.에 t-SNE-CUDA의 포장이 나왔다.
말 그대로 CUDA로 t-SNE를 고속화한 것으로 HPML2018(High Performance Machine Learning 2018 Workshop) 에서 발표되었다.

논문

슬라이드

GPU 설치 노력뿐만 아니라 알고리즘에도 공을 들였고,
SGD의 업데이트 공식은 물리 지식을 사용하여 Attractive Forces와 Repulsive Forces 두 가지로 나뉩니다.
다음 단계의 계산은 CUDA에서 고속화됩니다.

$P_{ij}$계산

$P_{ij}$및 $Q_{ij}$의 곱셈

Attractive forces

계산

Repulsive forces에서 Barnes-Hut tree 구축

Replusive forces의 tree 스캔

저차원 공간에 Attractive/Repulsive forces

적용
t-SNE는 샘플 수가 증가함에 따라 계산 시간도 크게 증가하기 때문에 속도를 높일 수 있다는 것이 기쁘다.
역시나'얼마나 빠를까?'
그래서 한번 해보고 보고할게요.

설치

자세한 내용은 참조 공식 저장소 설치,
Conda의 설치는 매우 수월하다. 어쨌든 Ubuntu 16.04+Anaconda3는 성공했다.
원본에서 구축하려는 시도는 하지 않았지만 의존 라이브러리가 많아 귀찮아 보입니다.

해봤어요.

먼저 NIST로 데이터 수를 변경해 보았습니다.
다만 t-SNE와 비교하면 논문과 같기 때문에 UMAP와도 비교해 봤다.

import scipy as sp
from sklearn.datasets import fetch_mldata
import json
from tqdm import tqdm
from tsnecuda import TSNE
import adelheid.plot as pp

import time


if __name__ == "__main__":
    COLORS = ["#000000", "#ffff33", "#66ff66", "#00ccff", "#6633ff", "#cc3399", "#ff3300", "#0066cc", "#9933cc", "#006633"]
    mnist = fetch_mldata("MNIST original", data_home="./")
    n_obs_all = len(mnist["data"])
    n_obs_list = [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 10000, 20000, 30000, 40000, 50000, 60000, n_obs_all]

    result = {}
    for n_obs in tqdm(n_obs_list):
        mnist_data = mnist["data"][:n_obs]
        mnist_labels = mnist["target"][:n_obs].astype(int)

        st = time.clock()

        model = TSNE(n_components=2, perplexity=30.0, theta=0.5, n_iter=1000)
        predicted = model.fit_transform(mnist_data)

        ed = time.clock()
        result[n_obs] = ed-st

        xmin = predicted[:,0].min()
        xmax = predicted[:,0].max()
        ymin = predicted[:,1].min()
        ymax = predicted[:,1].max()

        output_fn = f"mnist_tsnecuda_obs{n_obs}.png"
        fig,ax = pp.subplots(figsize=(16,12))
        unique_labels = sp.unique(mnist_labels)
        for _label in unique_labels:
            inds = sp.where(mnist_labels == _label)[0]
            ax.scatter(predicted[inds,0], predicted[inds,1], c=COLORS[_label], label=_label)

        ax.set_xlim(xmin, xmax)
        ax.set_ylim(ymin, ymax)
        ax.set_xlabel("component 0")
        ax.set_ylabel("component 1")
        ax.set_title("MNIST t-SNE-CUDA visualization")
        ax.legend()
        pp.savefig(output_fn)

    json.dump(result, open("tsnecuda_results.json", "w"), ensure_ascii=False, indent=2, sort_keys=True)

t-SNE와 UMAP를 포함하는 테스트용 코드는 여기 에 있습니다.
(위 코드를 실행하려면 여기 포장.

데이터 수가 10000을 넘으면 t-SNE-CUDA가 현저히 빨라진다. MNIST 전 사이즈의 70000점174.46이면 속도가 배 정도 높아진다.
논문에서 보고한 수치와 기본적으로 같다.
UMAP에 비해서도 4.47 배 정도 빠르지만 UMAP는 t-SNE에 비해 각 집단의 중심이 분리되고 집단이 쉽게 모일 수 있다는 장점이 있다.
이런 속도라면 결과적으로 UMAP를 사용하는 것이 좋다.
다음은 t-SNE/t-SNE-CUDA/UMAP에서 얻은 2차원 지도를 살펴보겠습니다.

t-SNE

9의 군집은 2개로 대체적으로 타당한 군집이다.

t-SNE-CUDA

t-SNE와 기본적으로 같은 경향을 보였지만 여러 그룹으로 나뉘는 클래스가 많아졌다.

UMAP

집단이 더욱 응집되어 각 집단은 쉽게 볼 수 있게 되었다.
역시 쉽게 볼 수 있는 관점에서 t-SNE보다 높다.

총결산

t-SNE-CUDA를 이동하여 MNIST에서 Barnes Hut t-SNE/t-SNE-CUDA/UMAP을 비교했습니다.

데이터 수가 10000을 넘으면 현저히 빨라진다

비트 압축의 특성으로 t-SNE와 대체적으로 같다

단순한 속도만 비교하면 UMAP보다 빠르지만 저차원 공간의 특성과 집단의 보기 쉬운 특성을 고려하면 UMAP를 사용하는 것이 더 좋을 수 있다.
수만 점 이상의 규모의 데이터에 t-SNE를 적용해야 하는 경우에 유용하다.
끝내다

참고 문헌

t-SNE-CUDA: GPU-Accelerated t-SNE and its Applications to Modern Data