고요한 하늘

첨언 : 글을 쓰다 보니 LSH를 어디에 사용하는지 쓰지 않은것 같다.

LSH는 문서를 몇개의 signature( 고유값 )으로 표현하는 방법이다. 일반적으로 문서 하나가 100여개의 단어로 구성되어 있다면 이를 벡터로 표현했을때 100차원이라고 볼수 있다. 이것은 제한된 크기 n차원으로 줄이는 기술이다.

n이 크면 클수록 원본 데이터에 유사해지지만 속도가 느려지고 작아지면 속도가 빨리진다.
물론 차원을 줄여 속도가 빨라진다고 퀄리티까지 형편 없어지면 알고리즘이고 불리지도 않았을 것이다.

차원이 줄어들면 문서의 중복 제거나 클러스터링이 가능할것 같다.

구글에서는 이기술을 map & reduce와 접목시켜 개인화된 뉴스 클러스터링을 한다고 한다.

Locality sensitive hashing : 고차원 데이터의 차원 확률에 기반한 차원 축소 방법론

Basic idea : 해시 함수에서 같은 데이터는 같은 buket에 들어간다.

간단한게 LSH를 설명하면 다음과 같다

두개의 문서가 있을때

문서에 나타나는 모든 키워드에 ID를 부여한다.( ID는 unique 해야 하고, 두번째 출연한 키워드에 대해서는 이미 부여된 ID가 주어진다 )
id가 부여되면

문서1 = 1,2,3,4,5

문서2  = 1,2,3,4,6,7,8

이런 모습이 될것이다.

여기에 1차원 함수를 n 개 만든다.

예를 들면

각각의 문서에서 일정한 간격  k개 마다  term id  n개를 추출한다.

간격(k)은 임의대로 설정해서 4로 설정하고 첫번째는 5, 두번째는 7, 세번째는 15, 네번째는 20

추출된 n개의 ID에서 가장 작은 값을 선택한다.( get the signature )

그러면 결과적으로

첫번째 문서에서 추출한 id가 4개

두번재 문서에서 추출한 id가 4개가 된다.

이렇게 추출한 ID가 같으면 두개의 문서는 유사할 가능성이 높은 문서로 판단한다.

간격 k를 더 많이 설정하여 추출하면 더 많은 id가 추출될 것이고 신뢰성도 높아질 것이다.( 물론 계산량은 많이지고 속도는 떨어질 것이다 )

실제 알고리즘은 여기에 prime number와  universal hash, random permutation 과 같은 개념들이 추가된다.

 BOOL prime_number (int x)
  {
  for ( int i = 2; i<=sqrt(double(x)); i++)

     if( x % i == 0 )
        return FALSE;

   return TRUE;
}

약 240,000개 문서에 대해서

문서당 signature를 추출하는 과정까지 테스트 했을때 1분 30초 정도가 소요되었다.

속도가 중요한 경우에는 사용해 볼만한 알고리즘이다.

LINK :

http://people.csail.mit.edu/indyk/mmds.pdf

KNN : http://sj21.wo.to/tt/320?category=4

MIN HASH : http://www.stanford.edu/class/cs276b/handouts/minhash.pdf

 위 내용이 이해가 어렵다면

문서 A, B가 있고

우선 문서 A에서 다음 규칙에 의해서 키워드를 선택한다.

3, 6, 9 12.. 번째 키워드를 가져와 정렬한 후에 최상위에 오는 키워드를 선택한다.( 선택된 키워드는 k1 )

5, 10, 15 ...번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k2)

7, 14, 21... 번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k3)

그럼 A문서는 { k1, k2, k3 }가 되고  A`으로 표현

다음 문서 B에서 다음 규칙에 의해서 키워드를 선택한다.

3, 6, 9 12.. 번째 키워드를 가져와 정렬한 후에 최상위에 오는 키워드를 선택한다.( 선택된 키워드는 k1 )

5, 10, 15 ...번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k2)

7, 14, 21... 번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k3)

그럼 B문서는 { k1, k2, k3 }가 되고 B`으로 표현

만약 A` = B`이라면 문서 A와 문서 B가 같을 확률이 높다고 할수 있다.

조금더 정확히 하려면 키워드를 좀더 많이 선택해서 비교하면 된다

이 글은 스프링노트에서 작성되었습니다.

carryover12.pdf

                              NUMBER OF              LENGTH OF                     NUMBER OF

 SELECTOR             CODES                     EACH CODE (BITS)         UNUSED BITS

 a                             30                            1                                    0

 b                             15                            2                                    0

 c                             10                            3                                    0

 d                             7                              4                                   2

 e                             6                              5                                   0

 f                              5                              6                                   0

 g                             4                              7                                   2

 h                             3                              10                                 0

 i                              2                              15                                 0

 j                              1                              30                                 0

TABLE-1

                                                                    possible next selector values

Current selector          a             b             c             d             e              f            g            h              i               j

a                               0             1             2                                                                                                      3

b                               0             1             2                                                                                                      3

c                                             0             1              2                                                                                       3

d                                                            0             1             2                                                                         3

e                                                                          0             1               2                                                         3

f                                                                                          0              1             2                                           3

g                                                                                                        0             1              2                            3

h                                                                                                                       0             1               2            3

i                                                                                                                        0             1               2            3

j                                                                                                                        0             1               2            3

TABLE-2

 relative-10은 TABLE-1에서처럼 총 10개의 selector가 존재한다.

그래서 이름이 relative-10이다.

그럼 relative가 의미하는 것은  selector를 선택할때 이전에 선택했던 selector를 기준으로 상대적인 거리를 계산하여 기록하기 때문에 붙여진 이름이다.

예를 들면 이전 selector가 c이었다면 현재 selector로 될수 있는 후보는 b ,c, d, j 이다.

다시 말하면 최대 경우는 수는 4가 되고 이 4를 저장하기 위해 2bit를 사용한다.

전체 진행 과정을 예를 들어 설명 하면 다음과 같다.

입력되는 포스팅값이 다음과 같이 주어졌다고 가정하자

 1, 3, 9 , 11 ,12, 14

초기 selector를 선택하고 시작할수도 있으나, 여기서는 a를 초기 selector로 하겠다.

-- 데이터를 압축하여 저장할때 기본적으로 데이터 사이의 차이를 저장한다. 차이를 저장하므로써 저장할 수가 작아지기 때문에 효율적으로 데이터 압축이 진행될수 있다. (이것을 보통은 data gap 줄여서 D-gap이라 부른다)

a selector가 기본적으로 바뀔수 있는 selector은 a, b, c, j 이다( TABLE-2 참조) 

초기 값이 1, 3, 9, 11, 12, 14 라면 차이값으로 다시 변환하면 아래와 같다.

1, 2, 6, 2, 1, 2

첫번째 숫자 1는 a selector로 저장할수 있기 때문에 selector는 여전히 a이다.

두번째 숫자 2는 a selector로 저장할수 없기 때문에 a보다 큰 selector b를 선택한다.

selector b는 2를 담을수 있기  때문에 현재 selector는 b이다.

세번째 숫자 6은 b selector로 저장할수 없기 때문에 b보다 큰 selector c를 선택한다.

selector c도 6을 담을수 없기 때문에 selector는 마지막 가능한 selector인 j로 이동한다.

selector  j는 하나의 데이터만을 저장할수 있기 때문에 첫번째 숫자 1을 저장한

여기부터는 다시 위의 과정을 반복한다. 단 j selector에서는 selector가 아래로 이동한다.

2는 selector j로 담기에는 너무 크기 때문에 아래 selector로 이동한다

 selector i 는 2를 담기에는 너무 크기 때문에 아래 selector로 이동한다.

 selector h 는 2를 담기에는 너무 크기 때문에 아래 selector로 이동한다.

 selector g 는 2를 담기에는 너무 크지만 selector에서 이동할수 있는 최대 범위 이기 때문에

더이상의 selector를 아래로 이동하진 못한다.

세번째 숫자 6은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

세번째 숫자 2은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

세번째 숫자 1은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

세번째 숫자 2은  selector g로 저장할수 있기 때문에 현재 selector는 g이다.

 위와 같은 방식으로 selector는 이전 selector를 기준으로 TABLE-2를 참조하여 이동할수 있다,

selector j일 경우에만 아래(table-2 기준으로 왼쪽)로 이동하고 모든 경우는 위로(table-2기준으로 오른쪽)만 이동한다.

이런 방법으로 위에 든 예처럼 "1, 3, 9 , 11 ,12, 14"은 interger 변수 2개로 모두 표현할수 있다. 

이 글은 스프링노트에서 작성되었습니다.

http://en.wikipedia.org/wiki/Bayes'_theorem

첫번째 바구니 : 초콜렛 쿠키(10), 일반쿠키(30)

두번째 바구니 : 초콜렛 쿠키(20), 일반쿠키(20)

쿠키를 하나 뽑았는데 일반 쿠키가 나왔다. 첫번째 바구니에서 뽑았을 확률

조건부 확률로 표현하면

일반쿠키를 선택했는데 첫번째 바구니일 확률

P(첫번째바구니 | 일반쿠키) = ?

첫번째 바구니 = A

일반 쿠키       = B

일반 쿠키를 뽑을 확률          P(일반쿠키)       = 50/80 ( 일반쿠키 / 전체쿠키 ) , P(B) = 0.625

첫번째 바구니를 선택할 확률 P(첫번째바구니) = 1/2 ( 첫번째바구니수 / 전체바구니수 ) ,P(A) = 0.5

첫번째 바구니를 선택하고서 일반쿠키를 선택할 확률 P(일반쿠키 / 첫번째 바구니)

(첫번째 바구니의 일반 쿠키수 / 첫번째 바구니의 전체 쿠키수) =  30/40 =  P ( B | A ) = 0.75

P(A | B)  = ( P ( B | A) * P(A)) / P(B) = (( 0.75 ) * 0.5) / 0.625 = 0.6

쿠키를 하나 뽑았는데 초코렛 쿠키가 나왔다. 첫번째 바구니에서 뽑았을 확률

P(첫번째바구니 | 초콜렛쿠리) = ?

첫번째 바구니  = A

초코렛 쿠키     = B

초코렛 쿠키를 뽑을 확률 P(B) = 30 / 80 = 0.375

첫번째 바구니를 선택할 확률 P(첫번째바구니) = 1/2 ( 첫번째바구니수 / 전체바구니수 ) ,P(A) = 0.5

첫번째 바구니를 선택하고서 초콜렛쿠키를 선택할 확률 P(초콜렛쿠키 / 첫번째 바구니)

(첫번째 바구니의 초콜렛 쿠키수 / 첫번째 바구니의 전체 쿠키수) , P ( B | A ) = 10 / 40 = 0.25

P(A | B)  = ( P ( B | A) * P(A)) / P(B) = (( 0.25 ) * 0.5) / 0.625 = 0.2 (
P(A | B) = ( P ( B | A) * P(A)) / P(B) = (( 0.25 ) * 0.5) / 0.375 = 0.3333

네이버에서 끝음절 차트라는걸 만들어서 네이버 탑에 걸었다.

예를 들면

~하는방법
~협회
~소
~서

와 같이 일정한 음절로 끝나는 쿼리들의 순위들을 보여주는 서비스이다.끝음절로 사용하는것이 조금 길게 되면 비교적 통일성있는 리스트들이 보여주는 반면 1음절로 끝음절이 짧으면 기대했던 것과는 다른리스트들이 많이 올라오는것 같다.
예전에 나도 이런 서비스 생각을 했었는데 여기서 한발 더나아가 가장 사용자가 많이 찾는 답까지 보여주고자 하다 막혔던 기억이 있다.

지금도 충분히 가이드 쿼리는 많은데 정작 사용자들이 찾고자 하는건 제대로 못찾아주는 것 같아 시도했었는데 뜻대로 잘 되지 않았다.

블로깅을 하다 보면 종종 다음 검색은 구글이 대행을 해주고 있는듯이 잘못 오해하고 있는 글들을 종종 보게 된다.

이 말을 맞는 말일수도 있고 틀린말일수도 있다.
맞는 말이라고 한다면 오해의 소지가 있다고 봐야 할것이고 틀린 말이라고 한다면 전부 틀렸다고 말하기는 어려울 것이다.

무슨 이야기인가 하면
다음에서는 현재 몇십개의 컬렉션에 대해서 검색서비스를 제공 하고 있다(여기서 컬렉션을 하나하나의 컨텐츠를 의미한다) 그런데 이중에 웹검색만은 구글이 대행하고 있는 것이다.

다음검색에서 검색을 하면 페이지 마지막 부분에 웹페이지 검색이 보여지는데 타이틀 오른쪽 구석에 POWERED BY GOOGLE이라는 글귀가 보인다.

우리나라에서 웹검색은 다른 검색에 비해 상대적으로 비중이 상당히 약해져 있다. 그러나 검색 서비스의 구색을 맞추기 위해서는 반드시 필요한 서비스(커버리지 부분)이지만 이것을 하기 위해서는 그어떤 것보다 기술적인 도적이 필요하다.

다시 말하면 개발 비용이나 시간은 많이 드는데 비해 쓰임은 작다고 할수 있다. ROI(return of Investment)가 안나온다는 이야기이다. 그렇기 때문에 다음에서는 이부분을 구글에 맞기고 있는게 아닌가 싶다.


결론적으로 다음의 대부분의 서비스는 다음 자체적으로 하고 있고 웹검색만 구글이 대행해 주는것이라고 봐야 할것이다.