定義:
記号集合 $\Sigma$ 上の有限系列 $S$ を以下のように定義する.\[S = (s_1, s_2, \dots, s_N),\quad s_i \in \Sigma\]
ここで $N \in \mathbb{N}$ は系列の長さである.$n \in \mathbb{N},\ n \geq 1$ を固定された整数とする.このとき,系列 $S$ に含まれるすべての $n$-gram の集合は,次のように定義される.\[\text{$n$-gram} := \left\{ (s_i, s_{i+1}, \dots, s_{i+n-1})\ |\ 1 \leq i \leq N - n + 1 \right\} \subseteq \Sigma^n\]
すなわち,$n$-gram は系列 $S$ から得られる,長さ $n$ の連続する順序付き部分列[$n$-タプル]全体の集合である.
n-gramとは,離散的な系列[文字列や単語列]において,連続する $n$ 個の要素から構成される部分列である.
この定義において「要素」とは,文脈に応じて文字・音素・単語など任意の単位とされ,$n$ は正の整数である.従って,n-gram は系列の局所的な構造を捉える有限長のスライディングウィンドウに相当し,情報処理・自然言語処理・バイオインフォマティクスなど,順序性をもつデータを解析する分野において基本的かつ有用な単位である.
たとえば,単語列\[S = [\text{"I"},\ \text{"love"},\ \text{"NLP"}]\]に対して,$n=2$ の場合の 2-gram は,\[\{\, [\text{"I"},\ \text{"love"}],\ [\text{"love"},\ \text{"NLP"}]\, \}\]である.数学的には、長さ $N$ の系列\[S = [s_1,\ s_2,\ \dots,\ s_N]\]に対して,$n$-gram の全体集合 $G_n[S]$ は次のように定義される.\[G_n[S] = \left\{\, [s_i,\ s_{i+1},\ \dots,\ s_{i+n-1}]\ |\ 1 \leq i \leq N - n + 1 \,\right\}\]したがって、$n$-gram は系列の局所的連接構造[長さ $n$ の連続部分列]の集合であると言える.
このように n-gram とは,ある文字列や単語列において,連続する $n$ 個の要素から構成される部分列を意味する.ここでいう「要素」とは,文脈に応じて文字,音素,単語など任意の言語単位であり,$n$ は正の整数である.たとえば,文字単位で "hello" という単語を考えた場合,2-gram は "he", "el", "ll", "lo" といった部分列に対応する.同様に単語単位で "I love NLP" という語列を考えた場合,2-gram は "I love", "love NLP" となり,3-gram は "I love NLP" の1つのみとなる.n-gram は確率的モデルの構築,言語解析,情報検索など多くの自然言語処理タスクにおいて,文脈の一部を簡易的に捉えるための基本的な構成要素として用いられる.
n-gram の概念は,統計的自然言語処理において20世紀半ばから形式化されてきた.情報理論の発展とともに,Claude Shannon[1948年]が文字列の情報量やエントロピーの測定を行う中で,一定のコンテキストに基づく確率推定の重要性が示され,n-gram の萌芽が見られた.Shannon の研究では,英語テキストにおける n-gram の統計的性質が分析され,言語の予測可能性に関する重要な洞察が得られた.20世紀後半になると,計算機による大規模コーパス処理が可能となり,Brown Corpus[1967年]などを用いた統計的手法が広まる中で,n-gram モデルは機械翻訳,音声認識,スペル補正などの基盤技術として活用されるようになった.1990年代には,特にトライグラム[3-gram]モデルが盛んに用いられ,文脈依存型言語モデルとしての有効性が広く認知された.これは隠れマルコフモデル[HMM]やバックオフスムージング[Katz backoff,Kneser-Ney smoothing など]と組み合わされ,デコーディング効率と予測精度を両立する実用的手法として発展を遂げた.
技術的には,n-gram モデルはマルコフ性の仮定に基づいており,ある単語[あるいは文字]が出現する確率を,直前の $n-1$個の要素のみに依存させる.この仮定により,系列全体の確率を局所的な部分系列の積で表現することが可能となる.たとえば,単語列 $w_1,w_2,\cdots w_m$ の同時確率 $P(w_1,w_2,\cdots w_m)$ は,連鎖律により,\[P(w_1) P(w_2 \mid w_1) P(w_3 \mid w_1, w_2) \cdots P(w_m \mid w_1, \dots, w_{m-1})\]と分解できるが,n-gram モデルでは\[P(w_i|w_i−n+1,\cdots,w_i−1)\]のように直前の $n−1$ 個の単語のみを考慮することで計算の簡略化を図る.完全な文脈を考慮するのは計算上非現実的であるが,n-gram を用いることで,短い文脈に限定した確率推定が可能となる.これは多くの実用応用において極めて有用であり,言語モデルの構築における基礎となった.
しかしながら,n-gram には固有の課題も存在する.第一に,コンテキスト長に限界があるため,長距離依存[例えば,文の主語と述語の呼応,代名詞の照応など]の捕捉が困難である.第二に,データスパースネス[疎なデータ]問題により,訓練データに現れない組み合わせに対する確率推定が不安定になる.第三に,$n$ の値を大きくすると,計算量やメモリ使用量が指数的に増加する.これらの課題を受け,現代においては Transformer ベースのニューラル言語モデルに取って代わられつつある.
とはいえ,n-gram は構造が単純で解釈性が高く,計算資源が限られた環境やエッジデバイスにおいては依然として有効な技術である.また,ニューラルモデルの前処理段階や特徴量抽出においても補助的に用いられることが多く,その役割は単なる古典的技術にとどまらない.さらに,現代の大規模言語モデルの評価指標[BLEU,ROUGE,perplexity 計算など]や,情報検索におけるテキストマッチング,盗作検出[plagiarism detection]などにおいても,n-gram の概念は重要な役割を果たしている.n-gram は,統計的手法と現代的手法の接点に位置する言語技術として,今なお重要な意義を持つ.
Mathematics is the language with which God has written the universe.