지밍이 블로그

다들 아시다시피 지능형 웹, 인공지능 웹, 시맨틱 웹 같이 현재 웹 3.0 환경에서 생활 하고 있습니다.
실제로 구글에서, 위와 같은 내용의 메일을 받아보면 메일의 내용이 수집되어 해당 내용과 관련된 추천을 제공하는 등의 서비스를……..

사용자 모르게 개인정보관련하여 동의를 받아서 제공하고 있다고 하네요

사용자가 검색단어를 입력하고 검색결과를 얻는 중간에, 지속적인 피드백을 통해서 인공신경망에는 학습이 이루어 집니다.

이 책에서는 사용자의 클릭 정보를 수집하여 기록하고, 그 기록을 이용해 검색 결과를 향상 시키는 방법을 살펴봅니다.

첫번째로는 학습된 인공신경망이 필요하답니다.

그럼 인공신경망이란 무엇을까요?

인간의 뇌를 기반으로 한 추론모델… 뉴런….

잠깐 생각을 하게됩니다 ㅋㅋㅋㅋㅋㅋ

뉴런은 신경계에서 기본적인 정보처리를 하는 단위입니다.

학교다닐때 많이들 보셨던 그림입니다.

인간의 뇌는 간단히 말하면 매우복잡하고 비선형적이며 병렬처리를 수행합니다.

이 관점에서 다시 말하면,

100개의 뉴런과 각 뉴런을 연결하는 6조개의 스냅스들의 결합체이고,

정보는 신경망 전체에서 동시에 저장되고 처리됩니다.

또 적응성이란 것을 가져서 잘못된정보에 대해서는 뉴런들 사이의 연결이 약해지고, 올바른 정보에 대해서는 뉴런들 사이의 연결이 강해지게 됩니다.

자! 그럼 다시 인공신경망으로 돌아가겠습니다.

인공신경망은 인간의 뇌를 기반으로 모델링하였습니다.

학습을 수행하고 가중치도 조정합니다.

인공신경망의 학습은

검색단어, 검색결과, 사용자가 클릭한 것으로 수행됩니다.

인공신경망의 구조에 대해 살~짝 더 들어가보겠습니다.

일반적으로 인풋값이 들어오면 적절한 weight가 곱해지고 더해집니다.

즉 노드간의 연결들을 가중치 있는 값으로 연결된다고 말할 수 있습니다.

1985년 프랭크 로젠블랫이 간단한 인공신경망을 훈련시키기위해 Perceptron algorithm을 발표하였습니다.

즉 이렇게 일반적인 input/output layer로 이루어진 Neural Network의 구조를 Perceptron이라고 합니다.

일반적으로 각각의 노드들은 연결을 통해 여러 입력값을 받을 수는 있지만, 출력값은 오직 하나입니다.

하지만 그림에서 보시다시피 단일 perceptron구조에서는 하나의 직선으로 된 판별식만 표현할 수 있어 새로운 모델이 제안됩니다.

단점을 보안하기위해서 중간에 hidden layer 로 여러 판별식을 추가로 둘 수 있어, 보다 복잡한 문제를 해결 할 수 있습니다.

(애니메이션), Hidden layer는 input layer에만 반응하기 때문에 hidden layer라고 부릅니다.

이제, 여기서는 수많은 neural network의 weight(가중치)값을 어떻게 학습시킬 것 인지 고민해야합니다.

책에나온 그림으로 보겠습니다.

Hidden layer는 원래 여러개의 층으로 구성이 될 수 있지만, 책에서는 단일 층의 경우만 설명하고 있습니다.

또 외부와 직접상호작용하지 않고 input layer에 따라러만 반응하므로 이 경우 input은 단어들의 집합이 돕니다. 그래서 이 layer를 쿼리층이라고도 합니다.

각 layer의 노드들은 인접한 layer의 모든 노드들과 연결됩니다.

여기서 최적의 결과는 검색어 안에 있는 단어들에 대한 입력값이 1이 되어야 합니다.

이게 무슨말이냐면,
아까 인공신경망은 실제 생물학적 신경망의 지능적 처리를 단순 모방하여 지능적 형태를 재현하는 것으로,

뉴런간에 교신정보의 세기가 강할 수록 신호 전달이 잘 되는 것이라고 생각하면 될 것 같은데요,

무한대의 값을 0~1사이의 적당한 값으로 표현할 때 1이 가장 최적화 된 값이 되는 겁니다. (맞는건지 모르겠음..ㅋㅋ)

따라서 1이 입력으로 들어오면 입력노드들에서 출력이 On이 되어 은닉층을 활성화 시키고,

충분히 강한 입력을 받은 은닉층 내 노드들이 차례로 On이 되어 출력층의 노드들까지 On을 시키게 됩니다.

이런식으로 계산을 한다는데..다음기회로 넘기도록 하겠습니다.

ㅠㅠ~

다시 그림으로 돌아와서 보겠습니다.

이런 상황에서 입력층 또는 은닉층의 노드들의 연결형태로 앞장에서 보신 계산식등으로 가중치가 정해지게 되고, 이에따라 출력층내의 노드들도 여러등급으로 활성화됩니다.

즉 이 활성화 레벨은 원래의 검색어안에 있는 단어들과 출력 URL간에 얼마나 관련이 있는지 결정하는데 사용됩니다.

우선 책의 그림에서는 bold체는 활성화된 노드를 의미하고, 실선은 강한연결을 의미합니다.

“world”와 “bank”를 검색했을때 두 입력노드가 활성화되고, 은닉1 노드가 활성화 되었을때,

출력쪽에서 “World Bank”가 활성화되었다는 그림입니다.

연결 강도의 정확도에 따라 결과는 달라지며, 정확도는 검색을 하고 검색결고에서 링크를 “클릭”할 때마다 네트워크를 학습하여 얻어집니다.

데이터 베이스를 설정해야합니다.

데이터 베이스에 저장할 정보로는

단어, URL, 은닉층에 대한 테이블, 단어층에서 은닉층으로의 연결정보와 은닉층에서 출력층으로의 연결정보를 가지고 있어야합니다.

리딩을 해주신 김승일님 자료

http://whydsp.org/263

# Unsupervised Learing / Clusgtering

# 계층적 군집화

1. 유사도가 가장 가까운 한 쌍을 찾는다.

2. 찾은 한 쌍을 하나의 그룹으로 만들고, 그룹의 위치는 두 쌍의 중심(무게중심)

3. 위 과정을 1개의 그룹만 남을 때까지 반복

: 팩토리얼계산으로 2^3알고리즘

# 계통도

: tree의 깊이가 깊은 것 보다, 깊지않은 쪽의 거리가 가까움

# 세로줄 군집화

: 데이터를 단순히 rotation 시켜줌

ex. 마트에서는 어떤 물건을 함께 진열하면 좋을까? 기저귀와 맥주

# 계층적 군집화 기법의 단점

: 뚜렷한 그룹으로 쪼개지 못하고, 계산량이 많음(알고리즘 대박...)

=> K-means Clustering

# K-means Clustering

1. 임의의 k점을 initial centroid로 잡기

2. 각 centroid에서 가까운 node들을 하나의 그룹으로 만듬

3. Centroid Update. 각 그룹의 무게중심으로 중심을 잡기

4. 더 이상 그룹에 변화가 없을때까지 위 과정을 반복

# 선호도 군집

: Zebo.com, 사람들이 가지고 싶은 물건 목록을 만드는 사이트

# Tanamoto Coefficient

: 책이 잘못나온거 같음

타니모토 알고리즘이 맞음

군집화 할 때, 합집합분의 교집합으로 계산

4. 검색과 랭킹

...

06. 유입 링크 사용하기

기존 - 페이지 내용에 기반한 점수 지표

검색품질향상 - 다른 사람들이 그 페이지에 등록한 정보를 적용,
                        의심스러운 값을 가진 페이지나 스패머들이 생성했을 법한 페이지 색인에 효과적

(이런 페이지들은 실제 내용을 가진 페이지에 비해 연결될 가능성이 적기때문)

# 단순계산

유입링크를 사용하는 가장 간단한 방법

> 각 페이지의 유입링크 개수를 세고,

> 링크 전체 개수를 페이지에 대한 지표로 사용

예, 학술눈문

: 인용논문수로 논문의 중요도가 평가

####코드

- 페이지들이 단순 리턴, 해당 페이지의 유입 링크 개수만을 의존하여 랭킹

예, "Programming language"페이지가 "Python"페이지보다 많은 유입링크를 갖지만

정말 찾는 것이 "Python"이라면 결과에서 제일 먼저 나타나야 함

유입 링크 기반지표와 다른 지표들 중 하나와 결합하여 검색능력과 랭킹에 적합도를 결합할 수 있다. (검색능력향상)

# 페이지랭크 알고리즘

"Google"을 만든 세르게이 브린과 래리 페이지가 대학원생 때 쓴 논문 "The Anatomy of a Large-Scale Hypertextual Web Search Engine"에서 발표

개요

- 검색엔진의 품질 향상을 목적

- 웹기반에서의 검색엔진은 인덱스만으론 부족

: 검색된 페이지수는 엄청난 성장으로 방대하나, 사람들의 수용능력은 느리게 성장

         -> 결국 필요한 페이지만 골라서 읽어야 할 필요가 있음

- 관련이 있는 페이지만을 도출하자

- 하이퍼텍스트 정보를 사용하여 웹 페이지간의 연결 관계를 판단, "링크구조 및 링크달린 텍스트"

알고리즘 소개

- 기존 : 특정 페이지를 인용하는 다른 페이지가 얼마나 많이 있느냐를 세는 방식

- PageRank : 다른 페이지에서 오는 링크를 같은 비중으로 세지 않고, 페이지에 걸린 링크 숫자를 "정규화(normalize)"하여 사용

-> 하이퍼링크를 가지는 문서에서 상대적 중요도에 따라 가중치를 부여하는 방법을 가진 알고리즘

PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

PR : PageRack

PR(A) : A페이지의 페이지랭크 값

T1, T2,... : 그 페이지를 가리키는 다른 페이지들

PR(T1) : T1 페이지의 페이지랭크 값

C(T1) ; T1 페이지가 가지고 있는 총 링크의 갯수

> d(Dampen Factor)는 아직 생각하지 않기(d=1로 가정)

> A페이지를 가리키는 다른 페이지들의 페이지랭크 값을 평균화하여 다 더한 값

> 즉 A페이지랭크 값은 그 페이지를 인용하고 있는 다른 페이지들의 페이지랭크 값을 "정규화" 시킨 값

> "정규화"라는 말의 의미... 페이지랭크 값은 단순 합산이 아님. 

예. T1의 페이지랭크가 높아도, T1페이지를 가리키는 링크가 많다면(C(T1)) 그 페이지가 기여하는 비중은 낮아짐

A : 페이지

T1, T2, T3, T4, T5 : A를 가리키는 페이지

- 재귀적 호출 알고리즘

T1, T2, T3, T4, T5 의 페이지랭크값을 정규화하여 합한 값으로 A의 페이지랭크 값을 계산

A의 페이지랭크값도 다른 페이지의 페이지랭크값을 구하는데 사용

제한조건이 필요

- Dampen Factor

: 어떤 마구잡이로 웹서핑을 하는 사람이 그 페이지에 만족을 못하고 다른 페이지로 가는 링크를 클릭할 확률 - 논문

PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

d=1, 수식 그대로가 A의 PageRank 값

d=0, 모든 페이지가 1이 되므로 의미가 없어짐

d는 0~1 사이값

보통.. d는 85%, 0.85 

논문에 따르면, "모든 웹페이지의 페이지랭크 값을 합산하면 1이된다."고 하는데..

수식에 모순이 있음

d=1일때, 하나의 페이지에 대한 페이지랭크가 최대 1이 될 수 있으므로, 전체 페이지에 대한 페이지랭크값은 N.

위키피디아에서 수식을 정정

PR(A) = (1-d)/N + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))    // 전체 페이지수로 한번 나눔

출처 https://sungmoon.files.wordpress.com/2012/08/screen-shot-2012-08-25-at-4-46-19-am.png

책에서는,

dampen Factor를 85%로 계산(0.85)

PR(A) = 0.15 + 0.85 * ( PR(B) / link(B) + PR(C) / link(C) + PR(D) / link(D) )

PR(A) = 0.15 + 0.85 * ( 0.5 / 4 + 0.7 / 5 + 0.2 / 1 )        // 페이지랭크는 C가 젤 높은데, 링크는 A 한군데만 하기때문에 기여도가 젤 높음

PR(A) = 0.15 + 0.85 * ( 0.125 + 0.14 + 0.2 )

PR(A) = 0.15 + 0.85 * 0.465

PR(A) = 0.54425

함정,

페이지링크 값을 가지지않은 모든 페이지들의 페이지랭크 값들은??

> 모든 페이지랭크 값을 초기에 임의의 값으로 지정한 후 여러 번 반복 계산

> 반복을 할 때마다 각 페이지랭크값은 실제 페이지랭크값에 점점 가까워 지게됨

> 약 20회 정도

페이지랭크는 시간이 많이 걸림, 검색어와 상관없이 진행이 됨.

> 모든 URL에 대한 페이지 랭크를 사전에 계산

> 이 값을 테이블에 저장하는 함수 생성

calculatepagerank(x, y)

: 매번 수행될 때 모든 페이지랭크를 재계산

> 모든 페이지에 대한 페이지랭크값을 1로 초기화

> 모든 페이지URL에 대해 루프를 돌며 모든 유입링크에 대한 페이지랭크 값과 전체 링크 수를 얻는다.

>  예제 Database에서 어떤 페이지가 가장 높은 페이지랭크 값을 가지는지 확인하려면 데이터베이스에 직접 쿼리

>  "Main Page"가 젤 높은 페이지랭크를 가짐

> 정규화 함수 부분 추가

> weights 리스트를 수정하여 페이지랭크를 포함시키면 좀 더 향상된 결과를 얻을 수 있음

# 링크텍스트 활용

: 페이지의 링크들의 텍스트를 사용하여 페이지의 적합도를 판단

-> 링크를 가진 페이지 자체보다 페이지에 대한 링크에 대한 설명등을 참조(개발자들이 링크하려는 것들에 대한 간략한 설명을 링크에 넣기 떄문)

코드

> 검색 수행 시, 제공된 단어 ID들의 목록을 새로운 인자로 가짐

linktextscore(x,y,z)를 searccher안에 추가

> wordids 안에 있는 모든 단어들에 대해 루프를 돌면서 이 단어들의 링크를 찾기

> 링크의 목적지가 검색결과 안에 있다면, 링크소스의 페이지랭크 값을 목적지 페이지의 최종 점수에 더하기

검색 단어를 포함하고 있는 중요한 페이지로부터 링크를 많은 받은 페이지가 더 높은 점수를 가짐

검색 결과 내의 대부분의 페이지들의 경우 정확한 텍스트를 가진 링크가 없어 점수0을 가짐

> 링크 텍스트 랭킹을 반영하기 위해 weights 리스트에 코드를 추가

(1.0, selt.linktextscore(row, wordids))

모든 지표들의 표준 가중치는 없음. 

주요 검색 사이트들도 검색 결과 랭킹방법은 수시로 바꿈

: 사용할 지표와 제공할 가중치는 구축하려는 응용에 따라 크게 달라짐

# 유클리디안 거리점수

: 그럼  제곱 제곱 제곱이 되는뎅.....

 말이 안되는 알고리즘인뎅...? 2^ ==> 제곱으로 속도가 떨어지는거지???? 

... 유사도 계산 시 나타낼  수 있는 범위를 0~1로 잡고(정규화), 실수로 표현한다.

하.. 이게 왜. 효육적이지? 실수로 가면 속도가..........................................

제곱은 알고리즘에서..for로 처리하니깐.. ~~~

# 피어슨 상관점수

: 1, 0, -1

- 0이라는 기준을 잡는 조건은?

- 평균? 상관계수? 

- 전체적인 상관관계를 나타낼 수 있찌만 두 객체간의 유사도는 측정할 수가 없다는 단점이 있다.

- 궂이 이 이론을 사용하는 이유는 ? 두 객체간 상관관계의 판별로만 사용한다. 

# 유사도 계산을 할때는 

 1. 피어슨이 1위

 2. 유클리디안이 2위

 3. 3위는 기타 많은 것들이 있당...?

# 예를들어

 1 : 객체간의 양의 상관관계가 나오면 함께 파는게 낫다.

 0 : 객체간에 0의 상관관계가 나오면 

 -1: 객체간의 -1의 상관관계가 나오면 함께팔지않는게 낫다.

http://greennuri.info/?p=163