'Study/Information Retrieval'에 해당되는 글 21건

• 지금까지는 단순 검색(Ad hoc retrieval)에 대해 주로 다뤘으며, 단순 검색은 사용자가 정보 요구를 검색 엔진에 보내고, 검색 엔진으로부터 그 결과를 받아 확인하는 과정임
• 그러나 많은 사용자들은 똑같은 정보 요구를 주기적으로 반복함
• 상시 질의(Standing query)
• 시간이 지나면서 새로 출현한 문헌을 수집하기 위해 주기적으로 같은 질의를 반복함
• 그 외에는 일반 질의와 동일함
• 하지만 해당 질의와 밀접한 관련 문헌들을 찾을 수 없기 때문에 상시 질의가 점진적으로 수정되어야 함
• 분류(Classification) 문제
• 상시 질의를 일반화한 것으로 범주(Class, Category, Label)와 객체가 주어지면 그 객체가 속할 하나 이상의 범주를 결정하는 것
• 문서 분류의 목적은 실험 자료 혹은 새로운 자료에 대해 높은 정밀도를 얻는 것
• 하지만 학습 집합에서 높은 정밀도를 얻었다고 새로운 자료에 대해 반드시 높은 정밀도를 얻을 수 있는 것은 아님

13.1 문서 분류 문제

• 지도 학습(Supervised learning)
• 감독자(범주를 정의하고 학습 문헌에 범주를 부착하는 사람)가 학습을 도와주는 교사로서 역할을 수행하는 방법
• 지도학습을 F라고 하면 F(D) = ४로 표기할 수 있으며, 학습 방법 F는 학습 집합(Training set) D를 입력으로 받아서 분류 함수 ४를 구하는 것임
• 일단 분류 함수 ४가 학습되면 그 분류 함수 ४를 이용해서 실험 집합(Test set) 혹은 실험 자료(Test data)를 분류할 수 있음
• 이로써 새로운 문헌에 범주를부여할 수 있음

13.2 Naive Bayes 문서 분류

• 다항 Naive Bayes(Multinomial Naive Bayes) 혹은 다항 NB 모델
• 문헌 d가 범주 c에 속할 확률을 이용한 문서 분류 방법으로 각 범주 c 중 c 내의 문헌에서 용어 t의 상대 빈도에 따른 최대값으로 가장 적합한 범주를 선정하는 방법임
• 위치 독립 가정(Positional independence assumption)을 사용
• 희소성(Sparseness) 때문에 만약 용어들 중 하나가 추정치가 0이 되는 경우 모든 용어의 조건부 확률이 곱해지는 과정 때문에 해당 범주의 추정치는 0이 됨
• 따라서 모든 빈도에 1을 더하는 1-가산 평활화(Add-one smoothing) 혹은 Laplace 평활화(Laplace smoothing)를 사용함

13.3 Bernoulli 모델

• NB 모델을 설정하는 방법 중 하나
• 다항 모델의 다른 방법으로 다변량 Bernoulli 모델(Multivariate Bernoulli model) 혹은 Bernoulli 모델이 있음
• 이진 독립 모델과 같으며 문헌에 용어가 존재하면 1을 생성하고 존재하지 않으면 0을 생성하는 모델임
• 하지만 Bernoulli 모델에서 P(t|c)는 용어 t를 포함하는 범주 c에 속하는 문헌 비율(Fraction of document)로서 추정함
• 반면 다항 모델에서 P(t|c)는 용어 t를 포함하는 범주 c에 속하는 문헌에서 위치 비율(Fraction of position) 혹은 토큰 비율(fraction of tokens)로서 추정함
• 실험 문헌을 분류할 때 Bernoulli 모델은 이진 출현 정보를 사용하고 출현 빈도를 사용하지 않음
• 반면 다항 모델은 다양한 출현 정보를 이용함
• 결과적으로 bernoulli 모델은 긴 문헌을 분류할 때 많은 오류를 유발함
• 분류 결정(Classification decision)
• 다항 모델에서는 분류 결정에는 영향을 주지 않음
• Bernoulli 모델에서는 P(c|d)를 계산할 때 출현하지 않은 용어의 확률이 인수분해되어, 출현하지 않은 용어를 분명하게 모델링할 수 있음

13.4 Naive Bayes의 성질

• 문서 분류를 위해 다항 모델 및 Bernoulli 모델에서 2^M*|C|개의 인수를 추정해야하기 때문에 일반적으로 이 수가 너무 커서 정확한 인수를 추정할 수 없음
• 인수를 줄이기 위해 Naive Bayes 조건 독립 가정(Conditional independence assumption)이 필요함
• 하지만 조건 독립을 가정하더라도 문헌에서 각 위치 k마다 서로 다른 확률 분포를 가지고 있기 때문에 다항 모델에서는 너무 많은 인수가 존재함
• 추가로 용어 t의 조건부 확률은 문헌 내에서 위치(k1, k2)에 관계없이 모두 같음을 가정하는 위치 독립(Position independence)을 사용함
• 하지만 용어들은 서로 매우 의존적인 경우가 존재하기 때문에 독립적이지 않음
• 다항 모델에서는 위치 독립 가정을 사용하고 Bernoulli 모델에서는 위치 정보가 사용되지 않지만 NB는 좋은 문서 분류기임
• NB의 확률 추정(Probability estimates)은 그다지 좋지 않지만 분류 결정은 아주 좋음
• 개념 이동
• 시간이 흐름에 따라 개념이 변화하는 것
• 예를 들면 대통령이 바뀌는 것
• Bernoulli 모델은 개념 이동에 대해 특히 잘 적응됨
• 수십 개 이하의 용어만 가지고도 상당한 성능을 모임
• 따라서 아주 중요한 핵심 자질에만 의존하는 모델은 개념 이동에도 높은 정밀도를 유지할 수 있음
• NB는 다음과 같은 환경에서 자주 사용됨
• 정밀도가 좀 떨어져도 큰 문제가 되지 않을 때
• 대량의 학습 자료가 있고 작은 학습 자료에서 좋은 성능을 보이는 분류기보다 많은 학습 자료를 통해서 학습하는 것이 더 많은 이득이 있을 때
• 개념 이동에 잘 적응하는 분류기를 개발하려고 할 때

13.5 자질 선택

• 자질 선택(Feature selection)
• 학습 집합에서 출현하는 용어의 부분집합을 선택하는 것
• 목적
• 사전의 크기를 줄여서 학습과 실험에서 더 효율적인 분류기를 만드는 것
• 잡음 자질을 제거해서 분류 정밀도를 높이는 것
• 잡음 자질(Noise feature)
• 어떤 자질이 문헌 표현에 포함됨으로써 오히려 분류 오류가 증가하는 자질
• 과적합(Overfitting)
• 학습 자료에 우연히 발생된 것을 일반화하여 정확한 분류를 방해하는 현상
• 기본적인 자질 선택 알고리즘
• 범주 c가 주어지면 사전에 있는 모든 용어에 대해서 이용률 A(t, c)를 계산하고, 가장 높은 A(t, c) 값을 가지는 k개의 용어를 선택함
• 선택되지 않은 모든 용어는 문서 분류에 관여하지 않음
• 이용률
• 상호 정보
• Χ^2 검증
• 빈도
• 평균 상호 정보(MI, Mutual Information)에 따른 자질 선택
• 한 용어가 c를 정확하게 분류하는데 얼마나 많은 정보를 제공하는지를 측정함
• 실험 결과
• 자질 수가 많은 경우 다항 모델이 Bernoulli 모델보다는 좋은 성능을 보이고, 자질 선택으로 선택된 자질을 사용하는 것이 모든 자질을 사용하는 것보다 좋은 성능을 보임
• Χ^2 자질 선택(Χ^2 feature selection)
• 통계학에서 Χ^2 검증은 두 사건이 독립인지를 검증하기 위해 사용됨
• Χ^2은 평균 빈도 E와 관찰 빈도 N이 얼마나 큰 차이를 보이는지를 측정함
• Χ^2이 높으면(평균 빈도와 관찰 빈도가 비슷하지 않으면) 독립 가설이 거짓임
• Χ^2 임계값에 따라 통계적 유의성(Statistical significance)로 독립 사건인지를 결정하고 자질을 선택함
• 통계적으로는 독립성을 결정하기 어려울 수 있지만 자질의 유용성에 따라 순위화하는 데에는 충분히 사용 가능함
• 빈도 기반 자질 선택(Frequency-based feature selection)
• 어떤 범주에 가장 자주 나온 용어를 자질로 선택함
• 빈도는 문헌 빈도(범주 c에서 용어 t를 포함하는 문헌 수) 혹은 컬렉션 빈도(범주 c에서 속한 문헌에 출현한 용어 t의 빈도수)를 사용함
• Bernoulli 모델에서는 문헌 빈도가 적절하고 다항 모델에서는 컬렉션 빈도가 더 적절함
• 세 가지 방법 중에는 성능이 가장 낮음
• 탐욕적 방법(Greedy method) (욕심이 많아 새로운 것들을 끊임없이 원함)
• 세 가지 방법은 모두 탐욕적 방법으로 이들 모두 자질의 크기를 늘려도 이전에 선택된 자질이 가지고 있던 정보에 새로운 정보가 더해지는 형식으로 자질을 추출하지 않음
• 반면에 비탐욕적 방법(Non-greedy method)은 계산양이 너무 많아서 문서 분류에서 거의 사용되지 않음

13.6 문서 분류의 평가

• 문서 분류기에 대해 각각 재현율, 정확률, 정밀도를 구할 수 있음
• 최근 대부분 ModApte 분학(ModApte split)을 사용함
• 학습 문헌과 실험 문헌이 각각 9,603개와 3,299개로 구성되었고 모든 문헌은 전문가가 검토한 것임
• 범주 내에 문헌을 아주 고르게 분포함
• 상대 빈도가 1% 밖에 되지 않은 범주에 대해 항상 no라고 해도 99%는 정확하기 때문에 항상 no라고 해도 정밀도가 항상 높아서 작은 범주에 대해서는 재현율, 정확률, F1이 훨씬 더 적절한 척도임
• 유효성(Effectiveness)
• 정확률, 재현율, F1, 정밀도를 포함해서 분류 결정을 평가하는 척도를 통칭함
• 하나의 총합적인 척도를 위한 방법
• 거시 평균(Macroaveraging)
• 각 범주에 척도를 평균하는 방법
• 미시 평균(Microaveraging)
• 각 문헌마다 범주의 척도를 문헌마다 적절한 곳에 모으고 이렇게 모은 이분표에서 유효성을 구함
• 거시 평균은 각 범주가 동등한 비율로 참여하였고 미시 평균은 각 문헌이 동등한 비율로 참여함
• 따라서 미시 평균은 실험 컬렉션에서 큰 범주에 대한 유효성 척도로 사용되고 거시 평균은 작은 범주의 유효성 척도로 사용됨
• 범주, 문헌 컬렉션, 실험 환경에 따라 크게 달라질 수 있음