n그램

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 이 기사의 개선에 도움을 주십시오. (2011년 2월) (이 템플릿메시지의 삭제 방법 및 삭제 타이밍에 대해 알아보기)

컴퓨터 언어학 및 확률학 분야에서 n그램(Q그램이라고도 함)은 주어진 텍스트 또는 음성 샘플에서 n개 항목의 연속된 시퀀스입니다.응용 프로그램에 따라 음소, 음절, 문자, 단어 또는 기본 쌍이 될 수 있습니다.n-그램은 일반적으로 텍스트 또는 음성 말뭉치로부터 수집된다.항목이 단어인 경우 n-g은 ^[1]대상포진이라고도 합니다.

라틴어 숫자 접두사를 사용하여 크기 1의 n그램은 "유니그램"이라고 하며, 크기 2는 "빅그램"(또는 "디그램")이며, 크기 3은 "트리그램"입니다.영어의 기수에는 "4그램", "5그램" 등이 사용되기도 합니다.컴퓨터 생물학에서, 알려진 크기의 폴리머 또는 올리고머는 n그램 대신 k-mer라고 불리며, 특정한 이름은 "monomer", "dimer", "trimer", "tetramer", "pentamer" 등과 같은 그리스 숫자 접두사 또는 영어의 "one-mer", "two-mer", "three-mer" 등과 같은 영어의 기수들을 사용한다.

적용들

확률론적 언어 모델의(n− 1)–order 마르코프 모델의 형태로 그러한 배열에서 다음 항목 예측하는 것을 한 N그램 모델은 한 종류이다.[2]N그램 모델 현재 광범위한 확률, 커뮤니케이션 이론, 인스턴스를(를 컴퓨터 언어학(예를 들어, 이는 통계적인 자연 언어 처리), 계산 생물학, biologi에 사용된다.cal sequence analysis) 및 데이터 압축.n-그램 모델(및 이를 사용하는 알고리즘)의 두 가지 이점은 단순성과 확장성입니다. n이 클수록 모델은 잘 이해된 시공간 트레이드오프로 더 많은 컨텍스트를 저장할 수 있으므로 소규모 실험을 효율적으로 확장할 수 있습니다.

예

그림 1 다양한 분야의 n그램 예시

들판	구성 단위	샘플 시퀀스	1그램 시퀀스	2그램 시퀀스	3그램 시퀀스
고유명			유니그램	빅램	트리거
결과 마르코프 모델의 순서			0	1	2
단백질 염기서열	아미노산	Cys-Gly-Leu-Ser-Trp...	..., Cys, Gly, Leu, Ser, Trp, ...	..., 시스글리, 글리류, 류서, 세르-트롭...	..., Cys-Gly-Leu, Gly-Leu-Ser, Leu-Ser-Trp, ...
DNA순서결정	염기쌍	...AGCTTCGA...	..., A, G, C, T, T, C, G, A, ...	..., AG, GC, CT, TT, TC, CG, GA, ...	..., AGC, GCT, CTT, TTC, TCG, CGA, ...
컴퓨터 언어학	성격	...되느냐 안 되느냐...	..., t, o, _, b, _, e, _, o, r, _, n, o, t, o, _, _, b, e, ...	..., to, o_, _b, be, e_, _o, 또는 r_, _n, no, ot, t_, _t, to, o_, _b, be, ...	..., to_, o_b, _be, be_, e_o, _or, 또는 _, r_n, _no, not, ot_, t_t, _to, to_, o_b, _be, ...
컴퓨터 언어학	단어	죽느냐 사느냐...	죽느냐 죽느냐 사느냐...	죽느냐 사느냐 사느냐 사느냐 사느냐 사느냐...	죽느냐 사느냐 사느냐 사느냐 사느냐 사느냐 사느냐...

그림 1은 몇 가지 샘플 시퀀스와 대응하는 1그램, 2그램 및 3그램 시퀀스를 보여줍니다.

다음은 Google n-gorpus의 ^[3]워드 수준 3그램과 4그램(및 출현 횟수 카운트)의 예입니다.

3그램

• 도자기 수집품(55)
• 도자기 수집품 벌금(130)
• (52)에 의해 수집된 도자기
• 도자기 수집용 도자기(50)
• 도자기 수집품 요리(45)

4그램

• 착신(92)으로서 기능하다
• 인큐베이터로서 기능하다(99).
• 무소속으로 일하다(794년)
• 지표로서 기능하다(223).
• 지시로서 기능하다(72)
• 지표로서 기능하다(120)

n그램 모델

n그램 모델은 n그램의 통계 특성을 사용하여 시퀀스, 특히 자연 언어를 모델링합니다.

이 아이디어는 클로드 섀넌의 정보 이론 연구에 의한 실험으로 거슬러 올라갈 수 있다.섀넌은 다음과 같은 질문을 던졌다: 일련의 편지(예를 들어, "for ex" 시퀀스)가 주어졌을 때, 다음 글자의 가능성은 무엇인가?$교육 데이터$로부터 $크기{\displaystyle }$n$(\backslash$displaystyle n): a = 0.4, b = 0.00001, c = 0, ....의 이력이 주어진 다음 문자에 대한 확률 분포를 도출할 수 있으며, 여기서 가능한 모든 "다음 문자$"$의 확률은 1.0이 된다.

보다 간결하게 말하면, n그램 모델은 x ${\displaystyle i_{}}$-${\displaystyle {}_{}}$(${\displaystyle n_{}}$ -${\displaystyle 1_{}),{}_i}$ -$$ ( \ $display style$ x$_$ {$$i - ( n - 1 ) , \$dots$ , $x$_ { i -$$${\displaystyle 1_{}}$} , $display$ 1 을 $기반$으로 ${\displaystyle x_{}}$${\displaystyle i_{}}$를 $예측$합니다.확률적으로 이것은 $P{\displaystyle }$( ${\displaystyle x_{}}$ i${\displaystyle {}_{}{}_{}}$ ${\displaystyle x_{}}$-${\displaystyle {}_{}}$( n - ${\displaystyle {1)}_{}}$ 입니다$.$모델링, 독립성 가정은 각 단어가 마지막 n - 1 단어에만 의존하도록 이루어집니다.이 마르코프 모델은 진정한 기초 언어의 근사치로 사용됩니다.이 가정은 데이터로부터 언어 모델을 추정하는 문제를 크게 단순화하기 때문에 중요합니다.또한, 언어의 개방성 때문에 언어 모델에 알려지지 않은 단어들을 함께 묶는 것이 일반적입니다.

단순한 n그램 언어 모델에서는 이전 단어(빅램 모델의 단어 1개, 삼각 모형의 단어 2개 등)의 수를 조건으로 하는 단어의 확률은 범주형 분포(종종 부정확하게 "다항 분포"라고 불린다)를 따르는 것으로 설명될 수 있습니다.

실제로 확률 분포는 보이지 않는 단어 또는 n-그램에 0이 아닌 확률을 할당하여 평활됩니다. 평활 기법을 참조하십시오.

응용 프로그램 및 고려 사항

n-그램 모델은 통계적 자연어 처리에 널리 사용됩니다.음성인식에서는 음소 및 음소의 시퀀스를 n그램 분포를 사용하여 모델링한다.해석에서는 각 n그램이 n개의 단어로 구성되도록 단어를 모델링한다.언어 식별을 위해 문자/문자 순서(예: 알파벳 문자)를 다른 ^[4]언어로 모델링합니다.문자의 시퀀스에 대해서는, 「굿모닝」으로부터 생성할 수 있는 3그램(때로는 「트리거」라고도 불린다)은 「구」, 「우드」, 「od」, 「dm」, 「모」, 「모」 등이며, 스페이스 문자를 그램(때로는 텍스트의 시작과 끝)으로서 명시적으로 모델화해 「_g」, 「g」, 「g」, 「go」, 「g」, 「g」를 추가한다.단어 순서는 # the dog skunk 냄새에서 나올 수 있는 trig(single)로 # the dog skunk skee, the dog skee, dog skee, dog skee, dog skee, dog skee를 들 수 있다.

여러^[who?] 단어 용어에 더 관심이 있는 실무자는 공백을 제거하기 위해 문자열을 전처리할 수 있습니다.많은 사람들은 단락 마크를 보존하면서 단순히 공백 공간을 한 칸으로 축소합니다. 왜냐하면 공백 공간은 종종 글쓰기 스타일의 요소이거나 예측 및 추론 방법론에 필요하지 않은 레이아웃 또는 프레젠테이션을 도입하기 때문입니다^[who?].구두점은 일반적으로 전처리를 통해 감소 또는 제거되며 기능을 트리거하는 데 자주 사용됩니다.

또한 n-그램은 단어의 시퀀스 또는 거의 모든 유형의 데이터에 사용할 수 있습니다.예를 들어, 그것들은 큰 위성 지구 이미지 세트를 클러스터링하기 위한 특징을 추출하고 특정 이미지가 지구의 어느 부분에서 ^[5]왔는지 결정하는 데 사용되어 왔다.그들은 또한 유전자 염기서열 탐색과 DNA의 짧은 염기서열이 ^[6]유래한 종의 식별에서 첫 번째 통과로서 매우 성공적이었다.

n-그램 모델은 장거리 의존성의 명시적 표현이 부족하기 때문에 종종 비판을 받습니다.이것은 유일한 명시적 의존성 범위가 n-그램 모델에 대한 (n - 1) 토큰이기 때문이고, 자연 언어는 (wh-movement와 같은) 무제한 의존성의 많은 경우를 포함하기 때문에, 이것은 원칙적으로 n-그램 모델이 (장거리 상관관계가 원위치에 따라 기하급수적으로 감소하기 때문에) 소음과 무한 의존성을 구별할 수 없다는 것을 의미한다.모든 마르코프 모델에 대해 ce).이러한 이유로, n-그램 모델은 그러한 의존성을 모델링하는 것이 명시적 목표의 일부인 언어 이론에 큰 영향을 미치지 않았다.

또 다른 비판은 n그램 모델을 포함한 언어의 마르코프 모델이 성능/능력 차이를 명시적으로 포착하지 못한다는 것이다.이는 n그램 모델이 언어 지식을 모델화하도록 설계되지 않았고 언어 지식의 완전한 모델이라고 주장하지 않기 때문입니다.대신 실용화에서 사용됩니다.

실제로, n-그램 모델은 현대 통계 언어 애플리케이션의 핵심 요소인 언어 데이터를 모델링하는 데 매우 효과적인 것으로 나타났다.

기계 번역 애플리케이션과 같이 n-그램 기반 모델에 의존하는 대부분의 현대 애플리케이션은 이러한 모델에만 의존하지 않습니다. 대신, 일반적으로 베이지안 추론도 포함합니다.현대 통계 모델은 일반적으로 가능한 결과의 고유한 가능성을 설명하는 사전 분포와 관찰된 데이터에 대한 가능한 결과의 호환성을 평가하는 데 사용되는 우도 함수의 두 부분으로 구성된다.언어 모델을 사용할 경우 이전 분포의 일부로 사용됩니다(예: 가능한 번역의 고유한 "선량성"을 측정하기 위해 사용됨). 이 분포의 유일한 구성요소가 아닌 경우가 많습니다.

다양한 종류의 수작업 특징도 사용된다. 예를 들어, 문장에서 단어의 위치를 나타내는 변수나 담론의 일반적인 주제 등이 있다.또한 통사적 고려사항과 같이 잠재적 결과의 구조에 기초한 특징이 자주 사용됩니다.이러한 특성은 관측된 데이터를 사용하는 우도 함수의 일부로도 사용됩니다.전통적인 언어 이론은 이러한 특징에 통합될 수 있다. (실제로, 컴퓨터 언어학자들이 개별^{[citation needed]} 문법 이론에 대해 "불가지론"적인 경향이 있기 때문에 생성적 또는 다른 특정한 문법 이론에 특정한 특징이 통합되는 것은 드문 일이다.)

어휘 부족 단어

n그램 언어 모델을 사용할 때 문제가 되는 것은 어휘 부족(OOV) 단어입니다.컴퓨터 언어학 및 자연어 처리에서는 시스템 사전 또는 데이터베이스에 없는 단어가 입력될 때 발생합니다.기본적으로 언어 모델이 추정될 때 관찰된 전체 어휘가 사용됩니다.경우에 따라서는 특정 고정 어휘를 사용하여 언어 모델을 추정해야 할 수도 있습니다.이러한 시나리오에서는 어휘가 부족한 단어를 포함하는 말뭉치 내의 n-그램은 무시된다.n-그램 확률은 ^[7]관찰되지 않았더라도 어휘의 모든 단어에 대해 평활화됩니다.

그럼에도 불구하고, 어떤 경우에는 어휘에 특별한 토큰(예: <unk>)을 도입하여 어휘 부족 단어의 확률을 명시적으로 모델링하는 것이 필수적이다.말뭉치의 어휘 부족 단어는 n그램 수가 누적되기 전에 이 특별한 <unk> 토큰으로 효과적으로 대체된다.이 옵션을 사용하면 어휘가 부족한 ^[8]단어를 포함하는 n그램의 전이 확률을 추정할 수 있다.

대략적인 일치에 대한 n그램

n-그램은 효율적인 근사 매칭에도 사용할 수 있습니다.항목의 시퀀스를 n그램 세트로 변환함으로써 벡터 공간에 삽입할 수 있으므로 다른 시퀀스와 효율적으로 비교할 수 있다.예를 들어 영어 알파벳 문자만 있는 문자열을 단일 문자 3그램으로 변환하면 $({$ 26$^{3}})$의 차원 공간이 생성됩니다(첫 번째 치수는 세 개의 문자의 가능한 모든 조합에 대해 "aaa", 두 번째 치수는 "aab" 등의 발생 횟수를 측정합니다).이 표현을 사용하면 문자열에 대한 정보가 손실됩니다.예를 들어 문자열 "abc"와 "bca"는 모두 정확히 동일한 2그램 "bc"를 발생시킵니다({"ab"이지만 "bc"}는 {"bc", "ca"}과(와) 분명히 같지 않습니다).그러나 실제 텍스트의 두 문자열이 유사한 벡터 표현(코사인 거리로 측정됨)을 갖는다면, 두 문자열은 유사할 가능성이 높다는 것을 경험적으로 알고 있다.다른 측정 기준도 다양한, 때로는 더 나은 결과를 가진 n-그램의 벡터에 적용되었다.예를 들어, z 점수는 ("배경" 벡터를 형성하는) 문서의 대량 모음 또는 텍스트 말뭉치에서 각 n그램이 평균 발생과 얼마나 다른지 조사하여 문서를 비교하는 데 사용되었다.카운트가 작은 경우 g-점수(g-검정이라고도 함)를 사용하면 대체 모형을 비교할 때 더 나은 결과를 얻을 수 있습니다.

또한 두 문자열이 베이지안 추론의 문제에 대해 동일한 소스로부터 직접 왔을 가능성으로 유사성을 모델링하면서 n-그램의 통계에 대해 보다 원칙적인 접근법을 취하는 것이 가능하다.

표절 검출에는 n그램 기반의 검색을 사용할 수도 있습니다.

기타 응용 프로그램

n-그램은 컴퓨터 과학, 컴퓨터 언어학 및 응용 수학의 여러 분야에서 사용됩니다.

이들은 다음과 같은 용도로 사용됩니다.

• 벡터 머신과 같은 기계 학습 알고리즘이 문자열^{[citation needed]} 데이터에서 학습할 수 있도록 하는 커널을 설계
• 철자가^[9] 틀린 단어의 정확한 철자 후보자를 찾다
• 데이터의 작은 영역이 더 긴 n그램이 필요한 압축 알고리즘에서 압축을 개선한다.
• 패턴 인식 시스템, 음성 인식, OCR(광학 문자 인식), 인텔리전트 문자 인식(ICR), 기계 번역 및 이와 유사한 애플리케이션에서 관심 언어의 텍스트에 나타나는 특정 단어 시퀀스의 확률을 평가한다.
• 단일 질의 문서와 참조 문서 데이터베이스가 주어지면 유사한 "유사"(데이터 세트에 따라 종래의 의미가 확장되는 용어)를 찾을 수 있을 것으로 기대될 때 정보 검색 시스템의 검색을 개선한다.
• BLAST 계열의 프로그램과 같이 유전자 배열 분석에서 검색 성능을 향상시킨다.
• 텍스트가 속해 있는 언어 또는 DNA의 작은 시퀀스가 추출된 종을 식별한다.
• 문자 또는 단어를 무작위로 예측하여 텍스트를 생성합니다. 예를 들어, 분리된 프레스 알고리즘에서처럼.
• 암호 분석^{[필요한 건]}

n그램에 필요한 공간

단위는 n그램이고, 단위는 t문자($n{\displaystyle ,}$ ${\displaystyle tn\mathbb{}}$ N$${$displaystyle$ n$,t\in$ \$mathbb {N$라고 합니다.${\displaystyle \mathrm{여기}}$서 t${\displaystyle }$-${\displaystyle }$n +$$ {$displaystyle$ $t-n$$+$$1}$의 총 $문자열$은$n개$의 공백이 $필요$합니다.따라서 이 n그램에 필요한 총 공간은 (${\displaystyle t}$ ${\displaystyle -n}$ +${\displaystyle 1}$)${\displaystyle n}$n { $displaystyle (t-n+1)\cdot$ n$\}$ 입니다.이것은 다음과 같습니다.

${\displaystyle -n^{2}+(t+1)n}$

바이어스 대 분산의 트레이드오프

n-그램 모델에서 n에 대한 값을 선택하려면 추정의 안정성과 적절성 사이의 올바른 균형을 찾아야 합니다.이는 삼각형이 큰 훈련 말뭉치(수백만 개의 단어)에서 흔히 선택되는 반면, 빅램은 작은 훈련 말뭉치(수백만 개의 단어)에서 자주 사용된다는 것을 의미한다.

스무딩 기법

간헐적 그램(예를 들어 훈련 데이터에 적절한 이름이 나타난 경우)과 빈번한 그램 사이의 균형 체중 문제가 있다.또한 교육 데이터에서 볼 수 없는 항목에는 평활을 수행하지 않으면 0.0의 확률이 부여됩니다.표본에서 볼 수 없지만 그럴듯한 데이터의 경우 유사 마운트를 적용할 수 있습니다.유사 카운트는 일반적으로 베이지안 기반에서 동기 부여됩니다.

실제로는 0이 아닌 확률을 보이지 않는 단어 또는 n-그램에 할당하여 확률 분포를 부드럽게 할 필요가 있다.그 이유는 n-g 주파수 카운트에서 직접 파생된 모델은 이전에 명시적으로 볼 수 없었던 n-g 즉 제로 주파수 문제에 직면했을 때 심각한 문제가 발생하기 때문입니다.간단한 "add-one"(라플레이스) 스무딩(1개의 카운트를 보이지 않는 n개까지 할당, 연속 규칙 참조)에서 Good-와 같은 보다 정교한 모델에 이르기까지 다양한 스무딩 방법이 사용됩니다.튜링 할인 또는 백오프 모델.이러한 방법 중 일부는 n-그램의 확률에 사전 분포를 할당하고 결과적인 후방 n-그램 확률을 계산하기 위해 베이지안 추론을 사용하는 것과 같다.그러나 보다 정교한 스무딩 모델은 일반적으로 이러한 방식으로 도출된 것이 아니라 독립적인 고려사항을 통해 도출되었다.

• 선형 보간(예: 유니그램, 빅그램 및 삼각형의 가중 평균을 취함)
• 양호 - 매력적인 할인
• Witten-Bell
• 리드스톤의 평활
• Katz의 백오프 모델(트리그램)
• Kneser-Ney 스무딩

스킵그램

컴퓨터 언어학, 특히 언어 모델링 분야에서 스킵그램은^[10] 고려 대상 텍스트에서 구성요소(일반적으로 단어)가 연속되지 않아도 되는 n그램의 일반화입니다. 그러나 스킵되는 공백이 ^[11]남을 수 있습니다.기존 n그램 분석에서 볼 수 있는 데이터 희소성 문제를 극복할 수 있는 한 가지 방법을 제공합니다.컴퓨터 보안 분야에서는 스킵그램이 ^[12]n그램보다 공격에 더 강한 것으로 판명되었습니다.

공식적으로는 n그램은 토큰의₁ 길이n의 연속적인 연속이다.w_n. k-skip-n그램은 성분이 서로 최대 k의 거리에서 발생하는 길이n의 연속이다.

예를 들어, 입력 텍스트에서 다음과 같이 입력합니다.

스페인의 비는 주로 평원에 내린다

1-1992그램의 세트는 모든 빅그램(2그램)을 포함하며, 그 후속도 포함한다.

가을에는 스페인, 가을에는 스페인, 가을에는 주로 평지에 비가 내린다.

구문 n그램

구문 n-그램은 ^[13][14][15]텍스트의 선형 구조가 아닌 구문 종속성 또는 구성 트리의 경로에 의해 정의된 n-그램입니다.예를 들어, "경제 뉴스는 금융시장에 거의 영향을 미치지 않는다"는 문장은 의존관계의 나무 구조인 뉴스-경제, 효과-작은-시장-금융에 ^[13]이은 구문 n-그램으로 변환할 수 있다.

구문 n-그램은 선형 n-그램보다 구문 구조를 더 충실하게 반영하기 위한 것이며, 특히 벡터 공간 모델의 특징과 같은 응용 프로그램을 많이 가지고 있습니다.특정 태스크에 대한 구문적 n-grams는 예를 들어 저자 속성에서 표준 ^[16]n-grams를 사용하는 것보다 더 나은 결과를 제공합니다.

구문 n그램의 또 다른 유형은 part-of-speech n-grams로, 텍스트의 part-of-speech 시퀀스에서 추출되는 고정 길이 연속 중첩 서브시퀀스로 정의됩니다.part-of-speech n-grams에는 몇 가지 응용 프로그램이 있으며, 가장 일반적으로 정보 ^[17]검색에서 사용됩니다.

「 」를 참조해 주세요.

• 코로케이션
• 숨은 마르코프 모형
• n 태플
• 문자열 커널
• 미니해시
• 기능 추출
• 최장 공통 서브스트링 문제

레퍼런스

추가 정보

• 크리스토퍼 D.Manning, Hinrich Schüze, 통계 자연어 처리 재단, MIT 출판부: 1999.ISBN 0-262-13360-1.
• White, Owen; Dunning, Ted; Sutton, Granger; Adams, Mark; Venter, J.Craig; Fields, Chris (1993). "A quality control algorithm for dna sequencing projects". Nucleic Acids Research. 21 (16): 3829–3838. doi:10.1093/nar/21.16.3829. PMC 309901. PMID 8367301.
• 프레데릭 다메라우, 마르코프 모델과 언어학 이론무통.헤이그, 1971년
• Figueroa, Alejandro; Atkinson, John (2012). "Contextual Language Models For Ranking Answers To Natural Language Definition Questions". Computational Intelligence. 28 (4): 528–548. doi:10.1111/j.1467-8640.2012.00426.x. S2CID 27378409.
• Brocardo, Marcelo Luiz; Issa Traore; Sherif Saad; Isaac Woungang (2013). Authorship Verification for Short Messages Using Stylometry (PDF). IEEE Intl. Conference on Computer, Information and Telecommunication Systems (CITS).

외부 링크

• Google의 Google Books n-g 뷰어 및 Web n-g 데이터베이스 (2006년 9월)
• 마이크로소프트의 웹 n그램 서비스
• STATOPERATOR N-그램 프로젝트 Alexa Top 1M의 각 도메인에 대한 가중치 n-그램 뷰어
• 4억2천500만 단어 코퍼스 오브 컨템포러리 아메리칸 잉글리시 중 가장 빈번한 100만 개
• Peachnote의 음악 ngram 뷰어
• 확률적 언어 모델(n-그램) 사양(W3C)
• Michael Collins의 n-Gram 언어 모델에 대한 메모
• OpenRefine:상세 클러스터링