kjh8331267
commented
3 months ago TL;DR
- 이 논문은 텍스트나 그래프 같은 symbolic 데이터의 계층적 구조를 표현하기 위해 Euclidean 대신 Poincaré 임베딩을 사용하는 방법을 제안함.
Open kjh8331267 opened 3 months ago
kjh8331267
commented
3 months ago
Poincaré Embedding for Learning Hierarchical Representations
Abstract
1 Introduction
Riemannian(리만) 최적화에 기반한 임베딩을 학습하기 위한 효과적인 알고리즘을 소개하고 Poincaré 임베딩이 잠재 계층구조를 가진 데이터에서 Euclidean 임베딩보다 뛰어나다는 것을 보여줌. 표현 능력과 일반화 능력 모두에서 뛰어남.
텍스트, 그래프, multi-relational data같은 symbolic 데이터의 representations를 학습하는 것이 ML과 AI에서 중요한 패러다임이 되고 있음.
예를 들어, word embedding(Word2Vec, GloVe, FastText 등)은 기계번역부터 감성분석까지 다양하게 사용됨.
유사하게 graph embedding(latent space embeddings, Node2Vec, DeepWalk)은 소셜 네트워크에서 communitiy detection 과 의 link prediction에 유용하게 사용됨.
multi-relational data(Rescal, TransE, Universal Schema)은 knowledge graph completion과 information extraction에 사용됨.
일반적으로 임베딩 방법론의 목적 : 임베딩 공간에서의 유사성이 의미론적 또는 기능적 유사성을 반영하도록 symbolic 객체들(단어, 엔티티, 개념)을 조직하는 것
이런 목적을 위해 객체의 유사성은 일반적으로 거리나 임베딩 공간에서 내적(inner product)에 의해 측정됨.
예를 들어, Mikolove는 $R^d$에 단어를 임베딩함. 텍스트 안에 있는 유사한 문맥끼리 내적이 최대화시킴.
단어의 의미가 문맥들에서 파생된다는 분포가설에 의해 동기부여가 됨.
마찬가지로, Hoffsms는 social networks를 임베딩함. 네트워크로 연결되어 있는 경우 social actors간 거리를 최소화하는 방식
많은 실제 네트워크에서 발견되는 동질적 속성(homophily property) 즉, 유사한 actors이 서로 연결되어 있다는 경향이 있음을 반영함.
임베딩 방법론들이 여러 응용 분야에 성공적으로 증명해냈지만, 본질적인 한계를 가짐. → 복잡한 패턴을 모델링하는 능력은 임베딩 공간의 차원에 의해 본질적으로 제한됨.
예를 들어 Nickel등은 그래프의 선형 임베딩이 특정 유형의 관계를 모델링하기 위해 매우 큰 차원을 필요로 할 수 있다는 것을 보여줌.
비선형 임베딩이 이 문제를 완화할 수 있지만, 복잡한 그래프 패턴은 여전히 계산적으로 불가능한 임베딩 차원이 요구될 수 있음.
결과적으로 , 소셜 네트워크나 지식그래프, 분류와 같은 대규모 그래프 데이터의 임베딩을 정보 손실 없이 계산 가능한 방법은 아직까지 없음.
정보를 표현하는 능력은 학습과 일반화를 위한 전제 조건이기 때문에, 임베딩 방법론의 표현 능력을 증가시키는 것이 중요함. 이를 통해 거대 스케일로 복잡한 패턴을 현실적으로 모델링하는데 사용될 수 있음.
이번 연구에서 symbolic data의 특정 클래스에 대한 이 문제를 완화시키는데 포커스를 맞춤. 즉, 잠재적 계층 구조에 따라 조직될 수 있는 거대 데이터셋을 말하며, 이는 복잡한 많은 데이터셋에 내재된 속성임.
예를 들어 , 데이터셋에서 power-law distributions(멱법칙 분포)의 존재는 종종 계층 구조로 거슬러 올라갈 수 있음.
멱법칙 분포의 두드러진 예로 자연어와 소셜 및 의미 네트워크와 같은 scale-free 네트워크가 있음.
유사하게 Adcock 등의 실증 분석에 따르면 많은 real-world 네트워크가 근본적으로 트리 구조를 가지고 있다는 것을 나타냄.
이 구조적 속성을 활용해서 더 효율적인 표현을 학습하기 위해, 우리는 임베딩을 Euclidean이 아닌 hyperbolic 공간, 즉 일정한 negative curvature(음의 곡률)을 가진 공간에서 계산하는 것을 제안함.
비공식적으로, hyperbolic space은 트리의 연속적인 버전으로 생각될 수 있으며, 따라서 계층 구조를 모델링하는게 자연스러움.
예를 들어, 모든 유한한 트리는 거리가 대략적으로 보존될 수 있도록 유한한 쌍곡 공간에 임베딩될 수 있음을 입증함.
쌍곡 공간의 특정 모델 즉, poincare 볼 모델에 기반을 둔 접근 방식을 사용하며, 이는 gradient-based optimization(기울기 기반 최적화)에 적합함.
이를 통해 Riemannian optimization(리만 최적화)를 기반으로 임베딩을 계산하는 효율적인 알고리즘을 개발할 수 있으며, 이는 쉽게 병렬화할 수 있고 대규모 데이터셋에도 확장할 수 있음.
실험적으로, 이 접근 방식이 누락된 데이터가 있거나 없거나 모두 대규모 분류 체계에 대해 고품질 임베딩을 제공할 수 있음을 보여줌.
또한, WORDNET에서 학습된 임베딩이 어휘 내포(task)에서 최첨단 성능을 제공하는 것을 입증
협업 네트워크에서는 Poincare 임베딩이 그래프에서 링크를 예측하는데 성공적이며, 특히, 저차원에서 유클리드 임베딩보다 뛰어나다는 것을 보여줌.
이 논문의 나머지 부분은 다음과 같이 구성됨.
2장에서는 쌍곡 기하학을 간략히 검토하고 쌍곡임베딩과 관련된 연구를 논의함.
3장에서는 Poincare 임베딩을 소개하고 그것을 계산하는 방법을 논의함.
4장에서는 분류 체계 임베딩, 네트워크에서 링크 예측, 어휘 내포 예측과 같은 작업에서 우리의 접근 방식을 평가함.
2 Embeddings and Hyperbolic Geometry
Hyperbolic geometry(쌍곡 기하학)은 일정한 음의 곡률 가진 공간을 연구하는 non-Euclidean geometry(비 유클리드 기하학)임.
예를 들어, 쌍곡 기하학은 특수 상대성이론에서 Minkowski 시공간과 관련이 있음.
네트워크 과학에서 쌍곡 공간은 계층적 데이터를 모델링하는데 적합하여 주목을 받기 시작함.
예를 들어, 트리구조를 임베딩하여 그것의 구조가 그 임베딩에 반영되도록 하는 과제를 고려해보자.
가지 요소가 b인 규칙적인 트리는 레벨에 $(b+1)b^{l−1}$ 개의 노드를 가지고 있으며, 이하의 레벨에는 $((b + 1)b^{l} − 2)/(b − 1)$ 개의 노드를 가짐.
따라서, 자식 노드의 수는 트리의 루트로부터의 거리에 따라 지수적으로 증가함.
쌍곡 기하학에서는 이런 트리 구조를 2차원으로 쉽게 모델링할 수 있음. 루트 아래 정확히 $l$ 레벨의 노드들은 반지름 $r\propto l$ 인 쌍곡 공간의 구면에 배치되고, 루트 아래 $l$ 레벨보다 적은 노드들은 구면 내부에 위치됨.
이러한 구성은 쌍곡 원판 면적과 원의 길이가 반지름에 따라 지수적으로 증가하기 때문에 가능함. (Figure 1b)
직관적으로 쌍곡 공간은 트리의 연속적 버전으로 생각될 수 있으며, 반대로 트리는 discrete(이산) 쌍곡 공간으로 생각될 수 있음.
2차원 유클리드 공간($\mathbb{R}^2$, 평면 공간)에서 비슷한구성은 불가능함. 원의 길이($2\pi r$)와 원판의 면적($2\pi r^2$)이 반지름에 따라 선형적이고 이차적으로만 증가하기 때문
대신, 점점 복잡해지는 계층 구조를 모델링하려면 임베딩의 차원을 늘려야 함.
파라미터 수가 증가함에 따라 실행 시간 및 메모리 복잡도에 따른 계산 문제와 과적합 문제가 발생할 수 있음.
이러한 특성 때문에, 쌍곡 공간은 최근 복잡한 네트워크를 모델링하는데 고려되고 있음.
예를 들어, Kleinberg 은 지리적 통신 네트워크에서 그리디 라우팅을 위해 쌍곡 기하학을 도입함.
마찬가지로, Boguñá 등 은 임베딩 공간에서 그리디 최단 경로 라우팅을 수행하기 위해 AS 인터넷 토폴로지의 쌍곡 임베딩을 제안
Krioukov 등은 쌍곡 공간을 사용하여 복잡한 네트워크를 모델링하기 위한 프레임워크를 개발하고, 이러한 네트워크에 내재된 쌍곡 기하학을 가정함으로써 이질적인 차수 분포와 강한 클러스터링과 같은 전형적인 특성이 어떻게 나타나는지에 대해 논의함.
Adcock 등은 그래프의 트리 유사성을 특징짓기 위해 Gromov의 δ-쌍곡선에 기반한 측정 방법을 제안
머신러닝과 인공지능에서는 반면에, 유클리드 임베딩이 symbolic 데이터로부터의 학습을 위한 인기있는 접근법이 되었음.
예를 들면 섹션 1에 논의된 방법론 외에도, Paccanaro와 Hinton은 관계형 데이터로부터 학습하기 위한 초기 임베딩 방법 중 하나를 제안함.
더 최근에는, Holographic과 Complex Embeddings이 지식 그래프 완성에서 최첨단 성능을 보여줌.
계층구조 표현에 관련하여, Vilnis와 McCallum은 불확실성과 비대칭성을 포착하기 위해 밀도 기반의 단어 표현, 즉 가우시안 임베딩을 학습하는 방법을 제안함.
계층적 관계에 대한 정보를 정렬된 인풋 쌍의 형태로 제공 받았을 때, Vendrov 등은 단어, 문장 및 이미지에 걸친 visual-semantic hierarchies(시각-의미 계층 구조)를 모델링하기 위해 Order Embeddings(순서 임베딩)을 제안함.
3 Poincaré Embeddings
⇒ 계층적 정보를 직접적으로 이용할 수 없을 때, 비지도 학습을 통해 이를 추론하는 방법을 설명하며, 쌍곡 공간에서 Poincaré 볼 모델을 사용하는 이유
특히, $B^d={x∈\mathbb{R}^d∣∥x∥<1}$ d차원 단위 구로 정의하며, 여기서 $∥⋅∥$은 유클리드 노름임.
포인카레 볼 모형에서 쌍곡 공간은 the Riemannian manifold(리만 다양체) $(B^d, g_x)$에 대응됨. 이는 리만 메트릭 텐서를 갖춘 연린 단위의 구를 의미함.
$g_x = (\frac{2}{1−∥x∥^2})^2g_E$ 여기서 $x∈B^d$이고 $g_E$ 는 유클리드 메트릭 텐서를 나타냄.
$u,v∈B^d$가 주어질 때, 거리 $d(u,v)=arcosh(1+2\frac{∥u−v∥^2}{(1−∥u∥^2)(1−∥v∥^2)})$ → 식 (1)
구의 경계는 ∂B 로 표시 이는 구의 $S^{d-1}$에 해당 쌍곡 공간의 일부가 아니지만 무한히 먼 점들을 나타냄.
$B^d$에서 Geodesic(측지선)*은 ∂B 에 수직인 원 (및 모든 직경)임. 그림 1a 참고
Geodesic(측지선)은 평면 위에 존재하는 두 점을 잇는 최단거리. 지름김
식 (1)에서 볼 수 있듯이, 포인카레 구 내의 거리는u와 v 의 위치에 따라 부드럽게 변화
포인카레 거리의 이러한 지역성 속성은 계층 구조의 연속적인 임베딩을 찾는 데 중요한 역할을 함.
예를 들어, 트리의 루트 노드를 $B^d$의 원점에 배치하면 유클리드 노름이 0이기 때문에 다른 모든 노드와의 거리가 상대적으로 작아짐.
반면에, 잎 노드는 노름이 1에 가까운 점들 사이의 거리가 매우 빠르게 증가하기 때문에 포인카레 구의 경계 근처에 배치할 수 있음.(왜?)
또한, 식 (1)이 대칭이며 공간의 계층적 구조는 오로지 점들이 원점으로부터의 거리에 의해 결정됨.
이러한 자기 조직화 속성 때문에, 식 (1)은 텍스트와 네트워크처럼 객체의 계층적 순서가 사전에 지정되지 않은 비지도 설정에서 적용 가능
놀랍게도, 식 (1)은 객체의 계층 (노름을 통해) 과 유사성 (거리를 통해) 을 동시에 캡처하는 임베딩을 학습할 수 있게 해줌.
단일 계층 구조는 이미 2차원으로 표현될 수 있기 때문에, 포인카레 디스크 ($B^2$) 가 일반적으로 쌍곡 기하를 표현하는 데 사용
우리 방법에서 대신 포인카레 구 ($B^d$) 를 사용하는데 두 가지 이유가 있음.
심볼 집합 $S = {xi}{i=1}^n$에 대한 포인카레 임베딩을 계산하기 위해, 임베딩 $\Theta = {{\thetai}}{i=1}^n$ 을 찾는 것에 관심이 있음. 여기서 $θ_i∈B^d$ 임.
문제에 특화된 손실 함수$L(\Theta)$가 주어졌다고 가정, 이는 의미적으로 유사한 객체들이 포인카레 거리 측면에서 임베딩 공간 내에서 가깝게 위치하도록 함.
Θ 를 추정하기 위해, 우리는 다음 최적화 문제를 해결 $Θ′←argmin_ΘL(Θ)$ s.t. $∀θi∈Θ:∥θi∥<1$ → 식 (2) 섹션 4에서 구체적으로 논의
3.1 Optimization
3.2 Training Details
4 Evalution
4.1 Embedding Taxonomies
첫 번째 실험 세트에서는 포인카레 임베딩이 명확한 잠재 계층 구조를 보여주는 데이터를 임베딩하는 능력을 평가
이 목적을 위해, 우리는 두 가지 설정에서 WORDNET 명사 계층 [18]의 전이 폐쇄에 대한 실험을 수행함.
Reconstruction: 표현 용량을 평가하기 위해, 완전히 관찰된 데이터를 임베딩하고 임베딩에서 이를 재구성함. 임베딩 차원에 대한 재구성 오류는 모델의 용량을 측정하는 척도
Link Prediction: 일반화 성능을 테스트하기 위해, 관찰된 링크를 무작위로 제외하여 데이터를 학습, 검증 및 테스트 세트로 나눔. 검증 및 테스트 세트의 링크에는 루트 또는 리프 노드가 포함되지 않는데, 이는 이 링크들이 예측하기 쉽거나 신뢰할 수 없기 때문임.
우리가 the transitive closure(전이 폐쇄)*를 사용하고 있기 때문에, 상위어 관계는 방향 비순환 그래프를 형성하여 계층적 구조가 원시 데이터에서 직접 보이지 않고 추론되어야 함.
주어진 관계를 확장하여 모든 전이적 관계를 포함하는 것으로 예를 들어, '동물'이 '포유류'의 상위어(hypernym)이고, '포유류'가 '고양이'의 상위어라면, 전이 폐쇄를 통해 '동물'이 '고양이'의 상위어라는 관계도 포함
WORDNET 명사 계층의 전이 폐쇄는 82,115개의 명사와 743,241개의 상위어 관계로 구성되어 있음.
이 데이터에서, 우리는 두 가지 설정에서 다음과 같이 임베딩을 학습함.
식 (6)은 관련된 객체들이 관계를 관찰하지 않은 객체들보다 더 가까워야 하는 소프트 랭킹 손실로 해석될 수 있음.
이 손실 함수 선택은 서로 다른 서브트리에 속하는 심볼들을 임의로 멀리 밀어내고 싶지 않기 때문인데, 그 서브트리들이 여전히 가까울 수 있기 때문임.
대신, 우리는 관찰된 관계를 가진 심볼들보다 더 멀리 떨어지길 원함.
우리는 그래프 임베딩에서 일반적으로 하는 대로 임베딩의 품질을 평가함. 각 관찰된 관계 $(u,v)$ 에 대해, $u$ 의 실제 음성 예시들 사이에서 그 거리 $d(u,v)$를 순위 매김. i.e. 집합 ${d(u,v') \mid (u,v')\notin D}$
the Reconstruction setting에서, 데이터셋의 모든 명사에 대해 순위를 평가
그런 다음 v 의 평균 순위와 순위의 평균 정밀도(MAP)를 기록 (표 1)
대규모 분류체계의 임베딩에서 표현 능력과 일반화 성능 모두에서 매우 성공적
작업의 구조에 대해 더 많은 정보를 가진 Translational embeddings(변환 임베딩)과 비교해도, 포인카레 임베딩은 크기가 한 자릿수 작으면서도 성능이 크게 개선됨.
게다가, Link Prediction(링크 예측) 작업에서 포인카레 임베딩의 결과는 임베딩 차원에 대해 매우 강력함.
이 결과가 포인카레 임베딩의 구조적 편향에 기인한다고 생각하며, 이는 명확한 잠재 계층 구조를 가진 이러한 유형의 데이터에서 과적합을 줄이는 데 기여할 수 있음.
그림 2에서는 2차원 포인카레 임베딩의 시각화를 보여줌.
명확성을 위해, 이 임베딩은 WORDNET의 포유류 서브트리에서만 훈련됨.
4.2 Network Embeddings
4.3 Lexical Entailment
포인카레 임베딩의 흥미로운 점은 계층 구조가 연속적인 공간에서 표현되기 때문에 계층적 관계에 대해 단계적인 주장(확률적 판단)을 할 수 있음.
이 특성을 HYPERLEX [32]에서 테스트합니다. HYPERLEX는 의미 모델이 X가 Y의 유형인 정도를 [0, 10]의 척도로 평가하여 단계적인 어휘 내포를 얼마나 잘 포착하는지 평가하는 골드 표준 리소스임.
2163개의 평가된 명사 쌍으로 구성된 HYPERLEX의 명사 부분을 사용하여 포인카레 임베딩이 이러한 단계적인 주장을 얼마나 잘 반영하는지 평가함.
이를 위해, 섹션 4.1에서 WORDNET을 차원 $d=5$로 임베딩하여 얻은 포인카레 임베딩을 사용함. 이 임베딩들은 이 작업을 위해 특별히 훈련된 것이 아님.
$is−a(u,v)$가 참인 범위를 결정하기 위해 우리는 다음의 점수 함수를 사용함.
$score(is−a(u,v))=−(1+α(∥v∥−∥u∥))d(u,v)$
여기서 $\alpha (|v| - |u|)$ 항은 v가 임베딩 계층에서 낮을 때, 즉 v가 u보다 높은 노름을 가질 때 페널티로 작용
하이퍼파라미터 $\alpha$는 페널티의 심각도를 결정함. ($α=10^3$로 설정)
식을 사용하여 HYPERLEX의 모든 명사 쌍을 점수화하고, 실제 순위와의 스피어만 순위 상관 관계를 기록 (표3)
포인카레 임베딩을 기반으로 한 순위가 [32]에서 평가된 모든 최신 방법을 명확하게 능가함.
WN으로 시작하는 방법들도 WORDNET을 기반으로 사용하므로 가장 비교할 만함.
동일한 임베딩은 단계가 없는 어휘 내포를 평가하는 WBLESS [33, 14]에서 0.86의 최신 정확도를 달성함.
5 Discussion and Future Work
상징적 데이터의 표현을 학습하기 위한 포인카레 임베딩을 소개했으며, 객체의 유사성과 계층을 동시에 학습할 수 있음을 보였음.
또한, 임베딩을 계산하기 위한 효율적인 알고리즘을 제안했으며, 실험적으로 포인카레 임베딩이 계층적 데이터에서 유클리드 임베딩보다 중요한 이점을 제공함을 보임.
이 작업의 주요 초점은 상징적 데이터의 임베딩을 위한 쌍곡기하의 일반적인 특성을 평가하는 것
향후 작업에서는 포인카레 임베딩의 응용을 확장하고(예: 다중 관계 데이터), 단어 임베딩과 같은 특정 응용에 맞춘 모델을 도출할 계획
또한, 자연 경사도 기반 최적화가 이미 매우 좋은 임베딩을 생성하고 대규모 데이터셋에 확장될 수 있음을 보여주었는데, 전체 리만 최적화 접근법이 임베딩의 품질을 더욱 높이고 더 빠른 수렴을 이끌어낼 수 있을 것으로 기대함.