공간

1. Linear Independence(중요개념)

어떤 임의의 벡터 집합 

에 대해서 

이 되는 유일한 조건이 

이면 벡터()들은 서로 Linearly Independent 하다.

c가 모두 0이어야 한다면,  벡터 들은 서로  Linearly dependent 하다

그러면 c가 모두 0이 아니라는 것은 무슨 뜻일까?

예를 들어  

이 0이 아니라고 해보자.

그러면

이 된다.  

은 다른 벡터 ()로 표현이 가능하다는 것이다.

그러니까 벡터들이 dependent하다는 것은, 말 그대로 다른 벡터들에게 의존하여 표현될 수 있다는 것이다.

이런 벡터는 하나정도 빠져도 다른 벡터들로 조합해서 표현하면 되니까 벡터를 표현하는데는 별로 지장이 없다!

벡터들이 independent하다는 것은 반대로, 모든 벡터들이 다른 벡터들로는 표현될 수 가 없는 것이다. 

하나라도 빠지면 절대로 안된다. 하나라도 빠지면 다른 벡터로는 어떻게 조합해도 대체할 방법이 없어서 큰일이 난 상황이 된다

(갑자기 딴 소리인데, 우리도 삶에서 사람이라는 집합에서 independent한 set에 포함되면 아무도 우리를 대체할 수 없게 될까?)

2. Spanning a Subspace

벡터 스페이스 V가 모든

의 조합(combination)을 표현할 수 있으면 이 벡터들이 벡터 스페이스 V를 Span한다고 한다.

그러니까, 벡터 스페이스에 속한 모든 벡터들을 특정 벡터들의 집합으로 표현할 수 있다면 이 특정 벡터들의 집합이 벡터 스페이스를 Span 하는 것이다. 

즉, 벡터 스페이스 V에서 나온 모든 (Every) 벡터 v 는 w로 표현될 수 있다.   

(c는 계수)

3. Basis for a vector space

벡터 스페이스 V의 basis는 아래의 조건을 만족한다

1. 벡터들은 서로 Linearly independent하다.

2. 벡터들은 V를 Span한다.

이렇게 앞에서 배운 두개의 조건을 만족하면 Basis라고 보면 된다.

어떤 벡터 스페이스를 표현하는 최소한의 벡터 집합!!!!이다~

당연히 basis는 여러개가 될 수 있다. 그러니까 문제에서 어떤 벡터스페이스를 여러가지의 basis로 표현 가능하다는 것이다.

4. Dimension(차원)

Definition. Any two bases for a vector space V contain the same number of vectors. This number, which is shared by all bases and expresses the number of "degree of freedom" of the space, is the dimension of V.

해석하면. 아까 어떤 벡터 스페이스의 Basis 는 여러개가 있을 수 있다고 했는데, 그렇다고 해도 변하지 않는 것이 있다. 그것은 basis 안에 속해있는 벡터의 개수이다. 이 벡터의 개수를 바로 Dimension(차원)이라고 한다는 것이다.

여기서 어떤 사람들은 "왜! 무슨 근거로! 벡터 스페이스의 bases들의 원소 개수가 같다는 거야!" 라고 소리칠 수 있다.

증명이 있다.

Contradiction을 이용해서 증명할 거다.

1. w의 수가 v의 수보다 많다고 해보자. (n>m) 

2. v가 basis를 형성하므로, 반드시 그 스페이스를 Span해야 한다. 

3. 그러니까 모든는 v로 표현 가능해야 한다.

4. 만약  이라면, 이것은 을 첫번째 열로 가지는 A행렬의 VA곱으로 표현 가능하다. 즉, 아래와 같은 식으로 표현이 가능하다는 말이다.

이니까..

이다.

A의 원소에 뭐가 채워질지는 모르지만 A는 m by n 행렬이다.  앞에서  (n>m)이라고 가정했으므로 A는 넓은 직사각형 형태의 matrix이다.

5.  그러면 A는 pivot수가 m개 이고, 오른쪽에 한 열은 pivot이 없게 될 것이다. 즉,핵심은 여기! Ax=0는 x가 0 벡터 아니더라도 존재하게 된다. 

6. VAx=0, Wx=0이다. W에 있는 애들을 x라는 벡터의 0이 아닌원소를 가지고 잘 조합했더니 0이 나왔다. 그러면 W는 Basis가 아니다. 

7. 비슷하게 m>n일때도 그럴거다.

그러니까 m=m일때만 말이 된다!

DCG라는 metric은 기존의 precision, recall 기반의 검색엔진 평가 방법으로는 순위에 따른 차별점을 부과하기 힘들다는 판단에 따라 나온 방법이다.
이전에도 언급했지만 50% 이상의 검색 사용자가 검색 결과의 1,2 페이지 정도만 참고한다는 것은 precision, recall 만으로는 정확한 사용자 패턴에 기반한 성능평가를 하기 힘들다는 것을 알 수 있다.

Cumulative Gain

이는 그냥 n개의 검색 결과의 등급을 모두 합한 값이다. 관련성에 따라 3~0 사이의 값을 가진다고 하면 ideal CG와 현재 CG를 기반으로 절대적인 점수를 도출할 수도 있다.

 
예를 들어 첫번째 결과에서 여섯번째 결과까지의 rel 등급이 3,3,2,0,1,2 라고 한다면 CG는 11의 값을 가지게 된다.
이 방법은 실제 검색 결과 위치에 따른 영향을 전혀 받지 않는 방법이다.
ideal CG는 어떻게 될까? 이는 18이 될 것이다.

Discounted Cumulative Gain

이는 실제 검색 결과 순서에 따른 패널티를 적용한 점수값을 도출한다.

에디터가 산정한 rel점수에는 비례하지만 낮은 랭킹의 결과에 대해서 점진적인 패널티를 주기 위해  log 함수를 사용했다.
개인적인 생각으로 log 함수는 80:20 법칙에 가장 잘 맞는 함수라고 생각한다. 예를 들면 검색 결과 1,2위 사이의 간격은 정말 큰 차이지만 999위와 1000위 사이는 log의 값 차이이건 사용자가 느끼는 차이이건 그 차이가 거의 없다.

Normalizing DCG

위 DCG 점수는 현재 검색엔진의 결과의 상태를 보여준다. 그렇다면 가장 이상적인 검색엔진의 점수로 위 점수를 나누어 주면 정규화된  DCG가 나올 것이다.

현재 검색엔진의 순위대로 rel 등급이 3,3,2,0,1,2로 나왔다고 하면 DCG는 아래와 같이 계산될 수 있다.
그리고 이상적인 결과 순위는 3,3,2,2,1 이 될 것이다.

DCG = 3 + (3/log2 + 2/log3 + 0/log4 + 1/log5 + 2/log6) = 5.46

IDCG = 3 + (3/log2 + 2/log3 + 2/log4 + 1/log5) = 5.69

NDCG = 5.46 / 5.68 = 0.95

개인적으로 랭킹관련 평가를 할때 이 log함수를 많이 쓰고 있는데, log n값의 결과가 0이 되는 시기만 조심하면 랭킹관련 문제에서 아주 요긴하게 쓰일 수 있다.