브라운 군집화

Brown clustering

브라운 군집화는 윌리엄 A, 피터 브라운이 제안한 분배 정보에 기초한 하드 계층적 집적 군집화 문제다.브라운, 빈센트 델라 피에트라, 피터 V. 데 수자, 제니퍼 라이, 로버트 머서.[1]그것은 일반적으로 텍스트에 적용되며, 유사한 맥락에 내재된 단어들로 인해 의미론적으로 관련이 있다고 가정되는 군집들로 그룹화된다.

소개

자연어 처리에서 브라운 군집화[2](Brown clustering) 또는 IBM 군집화(IBM clustering[3])는 단어들이 발생하는 맥락에 근거한 계층적 군집화의 한 형태로서, 윌리엄 A가 제안하였다.브라운, 빈센트 델라 피에트라, 피터 데 수자, 제니퍼 라이, IBM의 로버트 머서.[1]이 방법의 이면에 있는 직관은 클래스 기반 언어 모델(cluster n-gram model이라고도[3] 함), 즉 단어 확률을 이전 단어의 클래스(클러스터)에 기초하여 언어 모델링에 내재된 데이터 첨사성 문제를 다루기 위해 사용된다는 것이다.

주라프스키와 마틴은 훈련장에서 이를 보지 못한 채 '상하이행'이라는 빅람의 가능성을 추정할 필요가 있는 항공 예약 시스템의 예를 들어준다.[3]이 시스템은 "상하이"를 다른 도시 이름으로 클러스터링한 다음 "런던으로", "베이징으로", "덴버로"와 같은 구문의 가능성을 기준으로 추정할 수 있다면 좋은 견적을 얻을 수 있다.

기술 정의

브라운은 클래스 기반 언어 모델, 즉 군집화를 고려하는 확률 모델에서 텍스트의 로그 확률을 기반으로 하는 이진 병합 기준을 사용하여 항목(즉, 유형)을 클래스로 분류한다.따라서 평균상호정보(AMI)는 최적화함수로서, 글로벌상호정보에서 가장 적은 손실을 발생시키는 방법으로 병합이 선택된다.

결과적으로, 그 출력은 이진수일 뿐만 아니라 아마도 모든 단어의 하나의 큰 클래스로 끝나는 병합 시퀀스로서 더 유용하게 생각할 수 있다.이 모델은 숨겨진 마르코프 모델과 같은 일반적인 형태를 가지고 있는데, 브라운의 문제 해결책에서 빅램 확률로 감소한다.MI는 다음과 같이 정의된다.

데이터의 가능성을 극대화하는 클러스터링을 찾는 것은 계산적으로 비용이 많이 든다.브라운 외 연구진이 제안한 접근법은 탐욕스러운 휴리스틱스다.

이 연구는 또한 브라운 군집화를 단순한 빅그램 클래스 기반 언어 모델로 사용할 것을 제안한다.텍스트의 토큰 w에i 대해 주어진 클러스터 구성원 자격 지표 c를i 지정하면, w 앞의i-1 단어 w에 주어진i 단어 인스턴스 [3]w의 확률은 다음과 같다.

이것은 제한된 효용성을 가지고 있다는 비판을[citation needed] 받아왔다. 왜냐하면 그것은 어떤 종류든 가장 일반적인 단어만을 예측하기 때문에, c 단어 유형으로 제한되기 때문이다; 이것은 이 모델과 브라운을 사용할 때 발견되는 당혹감의 낮은 상대적 감소에 반영된다.

변형

다른 작품들은 브라운 군집화 문제에 대한 그들의 접근방식에서 삼각형을 조사했다.[4]

브라운 클러스터링은 제안된 대로 고정된 수의 출력 클래스를 생성한다.과제에 의존하는 정확한 수업 개수를 선택하는 것이 중요하다.[5]브라운 군집화에서 비롯되는 단어의 클러스터 멤버십은 다양한 기계 학습 자연어 처리 작업에서 특징으로 사용될 수 있다.[2]

알고리즘의 일반화는 1992년 버전과 일반 형태에 대한 간결한 공식 정의를 포함하여 2016년 AAAI 회의에서 발표되었다.[6]이것의 핵심은 합병을 고려하는 클래스가 반드시 최종 클래스 출력 수를 나타내는 것은 아니며, 합병을 고려하는 클래스 수를 변경하면 최종 결과의 속도와 품질에 직접적인 영향을 미친다는 개념이다.

브라운 외 연구진(2018년 2월 기준)이 제안한 탐욕스러운 휴리스틱스에 대해서는 알려진 이론적 보장이 없다.그러나 클러스터링 문제는 기초적인 클래스 기반 언어 모델의 매개변수를 추정하는 것으로 틀에 박힐 수 있다. 즉, 가벼운 가정 하에서 이 모델에 대한 일관된 추정기를 개발할 수 있다.[7]

참고 항목

참조

  1. ^ a b Brown, Peter F.; de Souza, Peter V.; Mercer, Robert L.; Della Pietra, Vincent J.; Lai, Jenifer C. (1992). "Class-based n-gram models of natural language" (PDF). Computational Linguistics. 18 (4): 467–479. CiteSeerX 10.1.1.94.9004.
  2. ^ a b Turian, Joseph; Ratinov, Lev; Bengio, Yoshua (2010). Word representations: a simple and general method for semi-supervised learning (PDF). Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. pp. 1533–9. CiteSeerX 10.1.1.714.8528.
  3. ^ a b c d Jurafsky, Daniel; Martin, James H. (2009). Speech and Language Processing. Pearson Education International. pp. 145–6. ISBN 9780131873216.
  4. ^ Martin, Sven; Liermann, Jorg; Ney, Hermann (1999). "Algorithms for bigram and trigram word clustering". Speech Communication. 24 (1): 19–37. CiteSeerX 10.1.1.53.2354. doi:10.1016/S0167-6393(97)00062-9.
  5. ^ Derczynski, Leon; Chester, Sean; Bogh, Kenneth S. (2015). Tune your Brown clustering, please (PDF). Proceedings of the conference on Recent Advances in Natural Language Processing. CiteSeerX 10.1.1.713.5576.
  6. ^ Derczynski, Leon; Chester, Sean (2016). Generalised Brown Clustering and Roll-Up Feature Generation. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. pp. 1533–9. CiteSeerX 10.1.1.714.8528.
  7. ^ Stratos, Karl; Kim, Do-kyum; Collins, Michael; Hsu, Daniel (2014). A Spectral Algorithm for Learning Class-Based n-gram Models of Natural Language (PDF). Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence. pp. 762–771. CiteSeerX 10.1.1.643.6343.

외부 링크