Similarity Ranking

Similarity Ranking

A Context-Aware Similarity Search for a Handwritten Digit Image Database

• 손으로 쓴 숫자 이미지 데이터베이스에서 문맥을 인식하는 Similarity Search 알고리즘

Motivating Examples

• 사람이 볼 때는 한 줄이 비슷한 건데 기계가 보니 위 아래를 비슷하다고 보더라.

• Result

  

• 사람이 생각하는 것과 기계가 생각하는 것이 서로 다르더라

• 사람이 생각하는 것에 비슷하게 결과를 끄집어 내고 싶다.

  

• 실 세계의 모든 데이터는 N차원 공간 위의 하나의 점으로 표시가 된다.

• 유사하다는 것은 거리에 반비례한다. 데이터가 멀리 있으면 유사하지 않은 것.

• 하지만 그런 관점에서 보면, 1번과 유사한 것은 2번이다.

• 하지만 이 그림상에서는 데이터가 그룹을, 군집을 이루고 있다.

• 그러므로 3번데이터는 1번과 같은 그룹에 속해있다.

• 따라서 우리가 원하는 것은 2번보다는 3번이 1번과 더 비슷하다고 하고 싶다.

• 하지만 이건 쉽지 않은 일.

• 따라서 이걸 판단할 수 있는 알고리즘을 만들자는 것이 목표

  

• 쿼리포인트가 주어지고 이 포인트와 비슷한 것을 랭킹을 매겨보고 싶다.

• 기존의 방법은 무조건 거리계산. 거리가 멀면 비슷하지 않고 거리가 가까우면 비슷하다고 본다.

• 비슷한 것은 큰 원으로, 비슷하지 않은 것은 작은 동그라미로 표시

• 우리는 오른쪽대로 결과가 나오길 원한다. 두 개의 그룹이 있다는 것을 파악하도록. 데이터를 그루핑하고싶다.

Semantics of Image Dataset

• 이미지 데이터 집합의 개념을 데이터 셋에 있는 문맥적인 관계, 데이터와 데이터의 관계에 의해서 의미를 파악하겠다.
• 주어진 데이터 집합의 데이터 분포와 군집 구조를 가지고 그 정보에 의해서 데이터의 의미를 파악하겠다.
• 개별적인 하나의 데이터가 아니라 데이터가 속한 전체적인 데이터 분포와 데이터 군집 구조에 기반해서 데이터의 의미를 파악하겠다.
• 이 컨셉은 군집 가정과 일치한다.
  • 밀도가 높은 지역에 있는 포인터들은 그 지역 바깥에 있는 것들보다 비슷하다.
  • 동일한 글로벌 구조에 있는 포인터들은 이 구조 바깥에 있는 것들보다 더 비슷하다.

Nonlinear Similarity Model

• linear하다는 것은 1차원적으로 생각하는것. 예를 들어 위의 그림에서 1번과 2번이 거리상으로 더 가깝기에 비슷하다고 보는것
• 1차원적이 아닌, 1번과 3번이 비슷하다고 보는 것이 nonlinear하다는 것.
• 이러한 nonlinear similarity model을 위해 basic similarity model로 Gaussian function을 채용
  • $G(x_{ i }, x_{ j })= 1 /{ e^{ { { d }( x_{ i }, x_{ y })^{ 2 } }/{ { \sigma }^{ 2 } } } }$
  • 여기서 ${ d }(x_{ i }, x_{ y })$는 피타고라스 정리를 이용한 두 점 사이의 거리. 실제 거리.
    • $d^2=(x_1-y_1)^2+(x_2-y_2)^2$
  • 위 식에서 이 $d$, 즉 거리가 커지면 커질수록 $G$값이 작아진다. 반대로 거리가 작아질수록 $G$값이 커진다.
  • 여기서 $G$가 Similarity value. 유사도.
  • 이 $G$를 exponential하게 만들어 놓았다. 즉 지수에 변화하도록. 1차원이 아니게. (exponential function)
  • $d$가 커지면 커질수록 $G$는 지수적으로 작아진다. $d$가 작아지면 $G$는 지수적으로 커진다.
  • 이것이 사람이 느끼는 것하고 비슷하다.
  • 일반적으로 카메라로 사진을 찍어보면 가까이 있는건 더 가까이 느껴지고 멀리 있는 것은 더 멀리 느껴진다.
  • 실제로 인간이 느끼는 것이 그렇다. 조금 가까이 있으면 더 가까이 느끼고 조금 멀리 있으면 더 멀리 느껴진다.
  • 즉 지수적으로 비례하게 변한다.
  • 여기서도 linear하지 않고 nonlinear하다.
  • $e$의 $d$승에 비례하니까 $d$가 조금만 커지면 유사도는 굉장히 작아지고 $d$가 조금만 작아지면 유사도는 굉장히 커진다. 지수에 비례하게 되어 있으니까. 이게 의미가 있다.
  • 결론적으로 유사도 값을 1차원적이지 않고 지수에 비례하도록 만들었다.
• G : 거리 ${ d }(x_{ i }, x_{ y })^{ 2 }$에 Gaussian transformation을 실행한다.
  • 이것은 $x_i$와 $x_j$간의 유사도를 설명
• 이 exponential similarity function은 굉장히 sensitive하다. 지수승이니까. $d$가 조금만 변해도 $G$에 미치는 영향이 크다. 실제로 인간이 느끼는 것도 지역적으로 조금만 변해도 굉장히 sensitive하게 반응한다.
• Input space : 오리지널 데이터
• Feature space : 이렇게 G에 의해 변화된 새로운 공간
• ${ \sigma }^{ 2 }$ : 이걸로 나누지 않으면 너무 크게 변한다. 따라서 이 $d$의 영향력을 컨트롤 하기 위한 값. 구글에서는 이 값을 0.85로 설정.

A Simple Ranking Algorithm

• 위의 Gaussian function을 적용해서 변환시켜 보니까 왼쪽 오리지널 데이터가 오른쪽처럼 변하더라. 그룹으로 표현하기 몹시 용이해짐.

• 비슷한 것은 더 비슷하게 모이게 되고 조금만 달라도 굉장히 멀리 가는 것을 볼 수 있다. 이것이 exponential한 것의 영향력.

• A Simple Ranking Algorithm

  • m개의 데이터 집합들이 주어지고 그것을 분류하고 싶다. $X= {x_1, …, x_m} ∈ R^n$

    

    1. $K_{ij}$라는 similarity matrix로 만든다. 여기서 $K_{ij}$는 $i$와 $j$간의 유사도.

       $K_{ij}={ 1 }/{ { e }^{ { { d }(x_{ i },x_{ y })^{ 2 } }/{ { \sigma }^{ 2 } } } }$ if $i\neq j$ and $K_{ij}=0$

    2. 그 다음 $D_{ii}$라는 diagonal matrix를 만든다. 각 행의 합을 가지고 있는 것

    3. 그 다음 normalized similarity matrix $K^′= D^{−1/2}KD^{−1/2}$를 구한다.

       

    4. 그 다음 $K^′$로부터 eigenvectors(아이젠벡터) k개($v_1$, $v_2$, …, $v_k$)를 구한다. 그렇게 행렬 $V=[v_1 v_2 … v_k]$를 구한다.

       • 아이젠벡터는 데이터의 특성을 분석하는 것.
       • 데이터는 n차원 공간상의 점
       • 위 그림처럼 데이터가 여러개 있다고 가정 (점)
       • 이 데이터에서 제일 중요한 축을 찾는다. 데이터가 어떤 방향으로 분포가 되어 있는지.
       • 이 축이 첫번째 아이젠벡터(1번). 제일 중요함
       • 이 축과 직각을 이루는 축이 두 번째 아이젠벡터
       • 데이터가 분포된 축을 아이젠벡터

    5. 이 아이젠벡터를 찾아서 이걸 회전시켜 새로운 축으로 만든다. 이렇게 축과 함께 데이터를 돌려서 계산을 한다. 이렇게 $V$로부터 행렬 $Z$를 새로 구한다.

    6. 이렇게 새롭게 구한 $Z$에서 Euclidean distance(유클리드 거리)로 유사도를 분석한다. 유클리드 거리는 멀리 있으면 유사도가 떨어지고 가까이 있으면 유사도가 높다고 판단하는 것.

    7. 이렇게 해서 랭킹을 매긴다.

  • 이걸 자세하게 알 필요는 없다. 개념만 알고 있을 것.

    

  • 위 그림이 해당 과정을 통해 구한 결과.

  • 굉장히 클러스터 구조를 잘 표현하고 있다.

  • 저차원에서는 위와 같이 그룹 구조를, 클러스터 구조를 잘 파악하지만, 역시 멀티미디어 데이터, 굉장히 고차원 데이터가 되면 차원의 저주 문제로 인해 맞지 않는다.

Ranking Based on Similarity Distribution

• 위와 같은 방식은 고차원에서는 동작을 하지 않으므로 바꾼 알고리즘

• Input data $X = {x_1, x_2, …, x_m}$

• Query point $x_q, q ∉ {1, 2, …, m}$

  • 기존의 데이터는 쿼리 데이터 오브젝트가 아니라고 가정
  • 데이터 포인트와 쿼리 포인트가 다르다고 가정

• Similarity Distribution

  • 벡터 $s_i = [s_{iq}, s_{i1}, s_{i2}, …, s_{im}]^T$

    • $s_{iq}$ : 데이터 오브젝트 $x_i$와 $x_q$간의 유사도
    • 즉 쿼리 포인트를 포함해서 모든 오브젝트간의 유사도가 $s_i$
    • 이 $s_{ij}$는 ${ 1 }/{ { e }^{ { { d }(x_{ i }, x_{ y })^{ 2 } }/{ { \sigma }^{ 2 } } } }$를 이용해서 구한다.
    • 결국 $s_i$는 데이터 오브젝트 $x_i$와 쿼리 포인트를 포함한 데이터 베이스에 있는 모든 오브젝트간의 유사도

  • 벡터 $s_q = [s_{qq}, s_{q1}, s_{q2}, …, s_{qm}]^T$

    • $s_q$는 쿼리 포인트와 모든 데이터 오브젝트간의 유사도

  • $x_i$와 $x_q$간의 유사도는 두개의 similarity distribution vectors들간의 dot prodcut, 내적으로 구한다.

    • 두 개의 오브젝트간의 유사도를 내적이라고 한다.

    • 이렇게 내적을 구하는 것의 의미하는 바는, 두 개의 오브젝트들간의 유사도는 두 개의 오브젝트들간의 실제적인 유사도 뿐만 아니라 그 오브젝트와 인접한 것들과의 유사도까지 포함한다.

    • 즉, similarity($x_i$, $x_q$) = Individual-similarity($x_i$, $x_q$) + linear combination of the similarity($x_i$, $x_i$’s neighbors) weighted by similarity($x_i$’s neighbors, $x_q$)

      • $x_i$와 $x_q$간의 유사도는 $x_i$와 $x_q$ 두 개의 개별적인 유사도 + $x_i$와 $x_i$ 이웃들간의 유사도 + $x_i$와 $x_q$의 이웃들간의 유사도까지 포함해서 표시

        

      • 이것은 SNS에서, 중간에 내가 있고 내가 다른 사람의 카톡 전화번호에 올라가있다고 가정. 내가 저장한게 아니고 남이 나를 저장한 것. 위와 같이 표시

      • 즉 내가 많이 저장되어 있을 수록 나는 인기가 있는 것.

      • 이걸 친밀도라고 해보자. 나와 대중들간의 친밀도를 나를 가리키고 있는 화살표가 많으면 많을수록 나는 대중들한테 인기가 많은 것. 내 전화번호가 등록되어 있는 사람이 없으면 나는 전혀 인기가 없는 것. 이것이 직접적인 친밀도. 내 번호가 직접적으로 등록되어 있는 친밀도.

        • 이게 Individual-similarity($x_i$, $x_q$). $x_q$가 나. 나와 인접한 사람들과의 친밀도. 직접적인 친밀도

        

      • 나를 가리키고 있는 오브젝트들이 인기가 높을 수도 있다. 그럼 나는 인기가 덩달아 올라간다.

      • 나를 가리키고 있는 사람들이 인기가 높을수록 나도 인기가 자동적으로 올라간다. 그것이 이웃들(neighbors)

      • 이렇게 이웃들간의 친밀도까지 나의 인기에 반영을 하겠다는 것.

        • linear combination of the similarity($x_i$, $x_i$’s neighbors) weighted by similarity($x_i$’s neighbors, $x_q$)
        • 직접적인 친밀도 말고, $x_q$를 가리키고 있는 오브젝트들이 굉장히 많다. 그러면 나의 친밀도는, 나의 인기는 상승하는것.
        • 만약 나를 가리키고 있는 사람들이 인기가 별로 없는 사람들이면, 나의 인기는 직접적인 인기밖에 없게된다.
        • 따라서 나를 가리키고 있는 이웃들의 친밀도가 높으면 높을수록 나의 인기도 올라가도록 만든 것이 위의 식.

      • 이것이 Similarty의 분포에 기반한 Ranking 알고리즘.

      • 정리하면 나의 인기를 표현하는데 실제로 직접 나를 가라키고 있는 오브젝트들간의 친밀도에다가 나를 이웃으로 가지고 있는 다른 이웃들의 친밀도까지 포함해서 친밀도를 계산하면 더 정확하게 표현이 된다.

  • 실제 돌린 결과 - Ranking on 2 query opints x and +