그래서 행렬을 쓰면 뭐가 좋은거죠?

이제는 좀 더 실용적인 측면을 고려해보려고 합니다. 어디에다 쓰는 물건인가? -_-;;;

먼저 행렬의 곱셈은 어떻게 하는지 한번 보도록 하겠습니다.
행렬의 곱셈은 아래와 같은 방법을 통해서 수행합니다. 행 X 열 !! 위키피디어에 좋은 그림이 있어서 발췌했습니다.

Matrix Multiplication
In mathematics, matrix multiplication is the operation of multiplying a matrix with either a scalar or another matrix. This article gives an overview of the various ways to perform matrix multiplication.

이제는 좀 더 실질적인 예를 들자면, 행렬의 벡터를 이용한 방법 중에서 다차원 데이터의 표현에 사용될 수 있을 것 같습니다. 예를들어 하나의 문서를 표현하는 데에는 다음과 같이 여러가지 방법이 있을 것 입니다.

1. 모든 문자열을 원문 그대로 다 포함하는 방법
2. 사전에 있는 표제어만을 나열하는 방법 (특수문자 및 기타 기호는 제거)
3. 표제어 중에서도 복수를 단수로, 동사의 변형을 원형으로만 표현하여 정규화 된 키워드만 나열하는 방법
4. 이러한 키워드를 정렬하고 발생하는 횟수를 저장하는 방법
5. 이러한 발생횟수를 다시 중요도에 따라서 정규화 하는 방법
   (많은 문서에서 자주 발생하는 단어는 중요도가 떨어진다고 본다. tf * idf)

마지막 단계까지 어느정도 이해를 하셨다면, 수 많은 문서를 표현하는데에 있어서 행렬의 열을 모든 키워드로 보고 행을 하나의 문서로 본다면 아래와 같은 3개의 문서가 있을 때에 간단한 행렬을 만들 수가 있습니다.

문서1 = { 나는 학교에 갑니다. } = length 3
문서2 = { 오늘도 학교에서 친구와 싸웠습니다.} = length 5
문서3 = { 오늘은 날씨가 너무 좋습니다 } = length 3

* 키워드에 대한 문서에서 발견된 횟수 행렬입니다.

           문서1  문서2   문서3
가다       1         1        0
나          1         0        0
날씨       0         0        1
오늘       0         1        1
사람       0         0        0
싸우다    0         1        0
좋다       0         0        1
친구       0         1        0
학교       1         1        0

여기서 우리가 바라는 최종 목표는 '학교에 갑니다'라는 검색어로 가장 적합한 문서를 찾는 것입니다. 첫번째 행렬을 통해서도 즉, 컨텍스트 정보만을 이용해서도 충분히 관련문서를 찾을 수는 있습니다. 

이것은 다음의 질의문 행렬의 곱으로 구할 수 있습니다.

          가다, 나, 날씨, 오늘, 싸우다, 좋다, 친구, 학교
질의문    1    0     0        0       0        0       0      1

결과는

           문서1  문서2   문서3
결과        2         2        0

결과는 문서1 또는 문서2가 가장 관련있어 보입니다.
그래서 문서의 길이로 정규화를 해주면, 즉, 문서의 길이를 키워드의 갯수로 판단합니다.

* 문서별 클릭수 입니다. 더 많은 메타정보를 사용할 수도 있을 것 같습니다.

           문서1  문서2   문서3
정규화    2/3     2/5      0/3
결과       0.6    0.4      0.0

이제는 문서1이 가장 적절한 문서로 바뀌었습니다.. 너무 억지스러운 가요?
하지만 위의 경우도 마찬가지로 대부분의 행렬은 희소행렬(Sparse Matrix)입니다. 그래서 필요없는 0원소에 대한 연산은 필요없을 겁니다. 좀 더 효율적인 연산이 가능하다는 얘깁니다.

왜 굳이 행렬을 쓰나요?
우선 벡터로 표현된 것들 간의 연산이 가능하며, 이러한 표현을 직관적으로 할 수 있다는 장점이 있습니다. 또한 다양한 함수적인 요소들을 연속적으로 적용할 수가 있습니다. 또한 해당 연산의 성능과 무관하게 알고리즘을 개선할 수가 있습니다. 이러한 행렬연산은 현재 가장 나이브한 연산이 O(n³) 일 텐데요, 그나마 가장 최근에 알려진 방법을 통한다면, O(n^2.376) 까지 가능하다고 합니다. 거의 O(n²) 에 가까운 연산복잡도를 가지는 것이니, 일반적으로 순환문을 사용하여 또는 해싱을 사용하여 하는 프로그래밍 방식보다 성능에 있어서도 상당히 뛰어나다고 볼 수 있습니다.

 최근에 많이 얘기되고있는 Hadoop이라는 분산저장/처리 시스템을 활용하여 행렬연산을 할 수 있는 아파치 오픈소스 프로젝트도 진행되고 있습니다. 그것이 Hama라는 프로젝트인데요, 아직은 Hadoop프로젝트의 Sub-Project로써 인큐베이터에 있으며, 현재  NHN에 계신분이 Founder로써 활동하고 계십니다. 최근 뉴스레터가 많이 늘어나고 있는 걸로 봐서는 왕성히 활동하고 계신 것 같습니다. 이외에도 많은 한국분들이 커미터로 활동하고 계신 것으로 알고있습니다.

N의 세제곱이라면 솔직히 상당히 복잡한 알고리즘인데요 이를 좀 더 개선한 것이 Strassen 이라는 사람이 고안한 Strassen Algorithm입니다. 이 알고리즘을 쓰게되면 8번의 연산이 아닌 7번의 연산과 행렬의 합차를 통한 조금 개선된 행렬연산이 가능합니다.
행렬연산으로 가장 개선된 알려진 알고리즘은 Coppersmith-Winograd Algorithm이 있습니다.

세 차례에 걸쳐서 작성을 했는데, 생각보다 시간이 많이 걸리네요, 그래도 나름대로 행렬과 관련된 연산에 대한 감이 오는 것 같아 기쁩니다. 하지만 표현이 제대로 되지 않았던 것 같아 아쉽고, 그림이 많이 없어서 안타깝다는 생각도 좀 듭니다.

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