(57)【要約】【課題】自然言語処理などで時系列データの特徴量として良く利用されるn-gramにおいてnを職人芸で調節しないといけない問題を解決し、自動的に適切な特徴が選択されるotsu-gramを提案する。この特徴量にcorrespondence analysisを適用すると単語分散表現が計算できる。この単語分散表現は従来法のword2vecやfasteTextよりも大幅に精度向上したものになる。しかし、この特徴量と単語分散表現の計算には非常に大きなメモリが必要となり計算が困難である。【解決手段】n-gramのnを職人芸で調節しないといけない問題を大津の2値化でnを調節することで解決した。この特徴の計算でメモリが大量に必要になる部分を遅延評価にして少ないメモリでの計算を可能とした。データの一部をディスクに保存することで少ないメモリで高速に計算する方法も提案する。このメモリ効率向上手法は他の疎行列演算にも応用できる応用範囲の広いテクニックである。【選択図】図3【特許請求の範囲】
【請求項１】
発明を実施するための形態で説明した過メモリ行列、すなわち密行列としてメモリ上に展開するとメモリーオーバーフローを生じる可能性のある疎行列、圧縮データ、ファイルデータなどを、密行列を前提とした行列計算プログラムで処理する時に、メモリーオーバーフローが生じる場所に目印として標準的な行列データと違うデータ型を指定し、その標準と違うデータ型へのoperator overloadで過メモリ行列がメモリ上に展開されないような演算を遅延評価として定義するスタイルのアルゴリズム、およびその実装、および計算方式、およびそのための遅延評価処理をメモリーオーバーフローが生じる場所の目印にしたデータ型のclassの初期化処理とoperator overloadに遅延評価によって効率化される処理の詳細を記述することでオリジナルの密行列を前提とした行列計算プログラムにほぼ変更をすることなく、効率的なメモリ処理を可能とするデータ型、および図4の delayedspmatrix のデータ型、および図6の delayed_file_matrixのデータ型、および発明を実施するための形態で説明した遅延メモリ行列。
【請求項２】
疎行列を前提とした行列計算プログラムと密行列を前提とした行列計算プログラムを複数組み合せた時に、計算途中で疎行列が展開された巨大な密行列が生じてしまい、疎行列処理を前提としていた部分が密行列を前提とした計算に切り替わってしまう場合に、請求項1の方法を適用してメモリ使用量を減らすスタイルのアルゴリズム、およびその実装、および計算方式、及びそのためのデータ型。
【請求項３】
contingency tableとして疎行列データを入力するcorrespondence analysisとrandomized SVDとを組み合わせて計算する場合に計算途中で疎行列が展開された巨大な密行列が生じてしまうポイントである疎行列データのcontingency tableを平均的な確率から推定したcontingency tableとの差を計算する場所に目印として標準的な行列データと違うデータ型を指定し、請求項2および請求項1の方法を適用してメモリ使用量を減らすアルゴリズム、およびその実装、および図10のアルゴリズム、およびその実装、およびそのためのデータ型、およびそのデータ型そのためのデータ型の実装、および図4の delayedspmatrix のデータ型を図10のアルゴリズムのように設定するアルゴリズム、およびその実装、およびpython scikit-learn libraryのrandomized_svd関数においてsafe_sparse_dot関数に図12に示す拡張を行い図4に示すdelayedspmatrix のデータ型を利用するアルゴリズム、およびその実装。
【請求項４】
自然言語処理において単語の共起関係を行列として記述するために、図1に例を示すような離れた位置に2種類の単語が同時に出現する確率について、その離れている距離をx軸、出現する確率をy軸としたヒストグラムデータに大津の2値化を適用して距離が近い側に分類された確率を足しあわせて、2つの異なる単語の共起関係を記述した行列を計算するアルゴリズム、すなわちotsu-graアルゴリズム、およびその実装、および図2のアルゴリズム、およびその実装、およびこの時に計算される単語の共起関係の行列にcorrespondence analysisを適用して単語分散表現を計算するアルゴリズム、およびその実装。
【請求項５】
請求項4のotsu-gramアルゴリズムにおいて、事前に考慮したい単語集合Wを決めておき、その集合中の任意の2つの単語がk語離れて出現する回数を現す行列Nkへの積、和、アダマール積、単位ステップ関数、行列要素ごとの除算によって大津の2値化を計算し請求項4のotsu-gramアルゴリズムと同じ行列を行列演算によって出力するアルゴリズム、およびその実装、および図3のアルゴリズム、およびその実装、およびこのアルゴリズムにおいて行列を過メモリ行列として請求項2の方法でメモリ使用量を減らしたアルゴリズム、およびその実装、および過メモリ行列として図6の delayed_file_matrixのデータ型を利用するアルゴリズム、およびその実装、および図3のアルゴリズムに図6の delayed_file_matrixのデータ型を利用するアルゴリズム、およびその実装。
【請求項６】
行列データをメモリ上に行ごとに圧縮したデータとして格納し、行列計算を行ごとに解凍して行ごとに実行することで、行列データ全体をまとめて圧縮、解凍する時に大きなメモリが必要になってしまう問題を回避するアルゴリズム、およびその実装、および図8に示すアルゴリズム、およびその実装、およびその行ごとの圧縮の前に行列全体を効率的に圧縮できるHuffman Codingを計算してから行ごとに圧縮することで、さらに圧縮効率を向上させたアルゴリズム、およびその実装、および図9に示すアルゴリズム、およびその実装、およびこれらの圧縮解凍処理を遅延評価として既存の行列計算のメモリ使用量を減らす最適化を行なう請求項1、2、3、5のアルゴリズム、およびその実装。
【請求項７】
請求項4および請求項5と同様に単語の共起関係を行列として記述するために、離れた位置に2種類の単語 w1 と w2が が同時に現れる確率について、それぞれの単語が単独で現われる確率をかけ算した値 P(w1) P(w2）よりも小さい確率をゼロとみなす修正をかけたものを離れた位置に2種類の単語 w1 と w2が が同時に現れる確率とみなして、次の方法で単語の共起関係を行列として記述するアルゴリズム、およびその実装、およびこの時に計算される単語の共起関係の行列にcorrespondence analysisを適用して単語分散表現を計算するアルゴリズム、およびその実装。
1つめの単語の共起関係を計算する方法は、単純にk語離れた位置に2種類の単語 w1 と w2が同時に現れる確率を事前に設定した長さkmaxまで全て足し合わせた値を単語の共起関係とみなす方法、2つめの単語の共起関係を計算する方法は,請求項4および請求項5と同様に大津の2値化によって分割された長さが短い側についてのk語離れた位置に2種類の単語 w1 と w2が同時に現れる確率を全て足し合わせた値を単語の共起関係とみなす方法。
【請求項８】
請求項4および請求項5と同様に単語の共起関係を行列として記述するために、k語離れた位置に2種類の単語 w1 と w2が同時に現れる確率について、それぞれの単語がk語の区間に単独で現われない確率 (1-P(w1)-P(w2）) k をかけ算して減衰させた値を,k語離れた位置に2種類の単語 w1 と w2が同時に現れる確率とみなして、次の方法で単語の共起関係を行列として記述するアルゴリズム、およびその実装およびこの時に計算される単語の共起関係の行列にcorrespondence analysisを適用して単語分散表現を計算するアルゴリズム、およびその実装、およびk語離れた位置に2種類の単語 w1 と w2が同時に現れる確率に請求項7のそれぞれの単語が単独で現われる確率をかけ算した値 P(w1) P(w2）よりも小さい確率をゼロとみなす修正をかけたものを離れた位置に2種類の単語 w1 と w2が が同時に現れる確率とみなす処理をさらにかけることで、さらに遠方にある単語の関係が減衰するようにして、次の方法で単語の共起関係を行列として記述するアルゴリズム、およびその実装、およびこの時に計算される単語の共起関係の行列にcorrespondence analysisを適用して単語分散表現を計算するアルゴリズム、およびその実装。
1つめの単語の共起関係を計算する方法は、単純にk語離れた位置に2種類の単語 w1 と w2が同時に現れる確率を事前に設定した長さkmaxまで全て足し合わせた値を単語の共起関係とみなす方法、2つめの単語の共起関係を計算する方法は,請求項4および請求項5と同様に大津の2値化によって分割された長さが短い側についてのk語離れた位置に2種類の単語 w1 と w2が同時に現れる確率を全て足し合わせた値を単語の共起関係とみなす方法。
【請求項９】
自然言語以外の時系列データについて請求項4および請求項5および請求項7および請求項8と同様の処理を行なう特徴抽出アルゴリズム、およびその実装
【発明の詳細な説明】
【技術分野】
【０００１】
自然言語処理を始めとした様々な時系列データの特徴量として良く利用されるn-gramにおいて、nを職人芸で調節しなくとも適切な特徴が自動抽出されるようにする。この時に生じるメモリ不足の問題をプログラムコードをほとんど書き変えせずにデータの型情報の修正とそのデータの型へoperator overloadで解決する。
【背景技術】
【０００２】
本発明では自然言語処理を始めとした様々な時系列データの特徴量として良く利用されるn-gramの拡張とその応用を行う。本発明は自然言語処理以外の時系列データにも適用可能であるが、簡単のため自然言語処理特に英語への適用例を中心に以下では述べる。本発明が特に有効に働く応用は自然言語処理における単語分散表現の計算である。単語分散表現とは単語を数値のベクトルとして表現する方法である。単語分散表現の良さは単語間の類似度を使って評価されることが多い。具体的には単語間の類似度をベクトルの内積としたとき、内積が妥当な値になるかで単語分散表現の精度を評価できる。例えば( "train"と"car"の類似度 )  >  ( "plane"と"car"の類似度 )  という大小関係が様々な単語間で妥当な順番になっているか順番の正解率を計算することで単語分散表現の良さを計測する。このような単語の類似度の大小関係を列挙したベンチマークとして利用できるデータセットとしては非特許文献4で提案されている  ws353_similarity (Sim) データセット、非特許文献5で提案されている  ws353_relatedness (Rel) データセット、非特許文献6で提案されている  MEN データセット、非特許文献7で提案されている  M.Turk データセットなどがある。表1はこれらのデータセットを使って単語分散表現の既存手法と本発明を利用した場合の精度比較である。OG、PY、TCが本発明で新たに提案する手法である。またその組合せについても評価している。単語分散表現の計算手法としてはword2vecとfastTextとGloVeが有名であり、これらの手法よりも精度が大幅に良くなる手法は従来は存在しなかった。しかし本発明は大幅に精度が向上する。例えば表1のSimとRelのベンチマークでfastTextとword2vecの正解率が0．6程度の時に、本発明を利用した場合の正解率は0．7以上となる。なおこの比較実験で単語分散表現の計算には自然言語処理の研究で良く利用される英文データであるtext8 corpusを学習データとして利用した。
【０００３】
n-gramは自然言語処理を始めとした様々な時系列データの特徴量として利用されている。n-gramのnの値は応用によって適切に調節するのが一般的である。例えば英文の品詞推定問題では2-gramと3-gramが重要な特徴であり4-gram以上の特徴を利用すると精度が落るという分析がある。このnの選択は従来は開発者の直感で行なわれてきた。本発明では、このnの選択を自動的に行うことに相当する処理を行う。具体的には、画像処理の分野でパラメータ自動調節手法として利用されている大津の2値化をn-gramに適用してnの選択を自動的に行うことに相当する処理を行う。ただしnは単語ごとに適切な値に調節されるようにする。例えば "this is a pen" という英文を分析したい場合に、"this" の後に "is" が来る確率を考えたい場合には2-gramを利用し、"this" の後に "a" が来る場合についてはは3-gramを利用し、"this" の後に "pen" が来る場合については4-gramを利用する、ということに相当する処理を自動的に行う。しかし、このような計算を英文、例えば英文Wikipediaの英文に適用すると100ギガバイト以上のメモリーが必要となることがある。英文Wikipediaの英文は少なくとも10万種類以上の単語から構成されており、これらの単語の組み合わせ全てについて大津の2値化の計算をすると10万行10万列以上の大きさの行列が100個近く必要となるためである。そのため、一般的なパソコンでは計算するのが困難であり、従来このような分析は行なわれてこなかった。
【０００４】
メモリーに収まりきらないデータはスワップなどの処理によってディスクに保存するのが一般的である。近年 M.2 SSD などの高速なディスクの登場によりディスクからデータを読み書きする処理によって著しく処理速度が遅くなることは少なくなった。そこで前述の大津の2値化でメモリが不足する問題を、データをディスクに保存することで解決するのが本発明の要点の1つである。
【０００５】
メモリーに収まりきらないデータを扱う方法としてスワップ以外に良く利用される方法に in-memory zipと呼ばれるテクニックがある。これはファイル圧縮に利用されるzipをメモリ上のデータに適用するとデータが圧縮されてメモリ使用量が減るというものである。しかし圧縮されたデータを解凍すると元の圧縮されていない巨大なデータがメモリ上に再度展開されてしまうため、一時しのぎにすぎず、結果的にはメモリ使用量を減らせていない問題があった。この問題を解決するにはデータを解凍せずに圧縮したまま計算に利用できる仕組みや、圧縮と解凍を適切なタイミングで遅延評価する仕組みが必要となる。
【０００６】
データをzipなどの可逆圧縮ではなく、不必要なデータを削除して非可逆圧縮する方法も本発明では提案する。
【０００７】
本発明のn-gramの拡張について説明を簡単にするため単語w1と単語w2の間に任意の単語がk個挟まった単語列が生じる回数を
【０００８】
(数1)
#(  w1 *k  w2 )
で表す。例えば  "this is this is this is this is this"という英文の場合は以下となる。
【０００９】
(数2)
#(this is) = #(this *0 is) = 4
#(this * * is)  = #(this *2 is) = 2
#(this * is)  = #(this *1 is) = 0
【００１０】
図1は自然言語処理の研究で良く利用される英文データである  text8 corpusにおける  #( this  *k  a )のヒストグラムのkによる変化をプロットしたものである。"this" の直後は "this is a" や "this was a" などの様に動詞がくることが多く "this a" などという英文はほとんど存在しない。そのため #( this  *0  a ) は小さく、 #( this  *1  a ) が大きくなっている。k > 1では"a"がランダムに"this"以外の他の単語に関連して生じているのが見てとれる。つまり"this" と "a"の関係は k < 2 の場合のみを考慮すると良いことがわかる。すなわち ( this と aの関係の強さ) = #( this  *0  a ) ＋ #( this  *1  a ) とみなして良い。この k < 2 の範囲を自動的に選択するには図1の #( this  *k  a ) のヒストグラムを大津の2値化で分割すれば良い。
【００１１】
"this" と "a"以外の任意の単語同士 ( w1 , w2 ) の関係の強さを #(  w1 *k  w2 ) のヒストグラムが与えられている場合に大津の2値化を使って計算する手順を示したのが図2である。これはn-gramのnを大津の2値化で自動的に調節することに相当する。このアルゴリズムをotsu-gramと呼ぶこととする。otsu-gramの出力する行列をotsu-gram行列と呼ぶこととする。単語の種類が10万種類の場合はotsu-gram行列である図2のresultは10万行10万列となる。例えば "this" の情報が3行目、 "a" の情報が5列目に格納されている場合、result[3,5]は"this"の後に"a"が意味のある形で出現する度合い、つまり関係の強さを表わす値となっている。kmaxは50以上にすると安定した値が出力されることがわかっている。しかし10万種類の単語を扱う場合、全ての単語について #(  w1 *k  w2 ) を保存する必要があり、そのためには10万 * 10万 * 50の数値配列が必要となる。これがotsu-gramが大量にメモリを必要とする原因である。
【００１２】
otsu-gram行列にcorrespondence analysisを適用すると単語分散表現として利用できるベクトルが計算できる。この表現の精度は表1にotsu-gram(OG)で示したように従来手法を大きく上回る。otsu-gram行列は大部分の要素がゼロの疎行列である。しかし疎行列としてゼロ成分を無視できるCompressed Sparse Row (CSR) matrix形式を利用したとしても数ギガバイト以上のメモリを必要とする場合がある。しかしこの数ギガバイト以上のメモリの疎行列に対して単純にcorrespondence analysisを適用すると途中の計算過程で疎行列が密行列となってしまう。大部分の要素がゼロの疎行列であるためCSR matrix形式を利用することでメモリが数ギガバイト程度に収まっていたが、ゼロ要素のない密行列になってしまうと100ギガバイト以上のメモリが必要となることがある。この問題は特許文献1の遅延評価を利用した方法を利用すると回避でき、疎行列が展開されて密行列になってしまう状態を回避して少ないメモリで計算することが可能になる。
【００１３】
特許文献1で提案されている遅延評価による効率化を自動で実行できるなら、コンパイラ最適化の一部としてこの機能が既に実装されているはずである。しかし非特許文献1では遅延評価による効率化を自動実行すると何らかのオーバーフローエラーで計算が停止してしまう場合があることが示されている。エラーで計算が停止しないためには、遅延評価のタイミングを人間が指定する必要がある。例えば非特許文献2では疎行列のLU分解を遅延評価を利用して効率的に計算するために、どの時点で遅延評価をするか、どのように評価計算するかの手順まで詳細に記述したアルゴリズムが提案されている。本発明では特許文献1の技術背景0006に記述されているタイミングで遅延評価を行うcorrespondence analysisのアルゴリズムを利用する。またotsu-gramの計算についても遅延評価のタイミングが自明な計算方法を提案する。特許文献1の技術背景0006において文章のみで説明されているアルゴリズムを具体的に記述したものが図10である。図10で利用しているdelayed sparse matrixのpython言語による実装 class delayedspmatrixを記述したものが図4である。図5にはこのclassの使用例を示した。図4では delayed sparse matrixの積演算と転置演算と行列要素を取り出す演算を定義している。他の和や差などの演算も同様に容易に定義可能である。しかし説明を簡単にするため図4では省略した。図10で利用しているdelayed sparse matrixのSingular Value Decomposition(SVD)を計算するrandomizedSVD関数を記述したものが図11である。図10においてAが疎行列であってもベクトルrとcにゼロが存在することはめったにないためΞ=A/n-rct/n2は密行列となってしまう。この密行列が莫大なメモリを必要とするため、従来はcorrespondence analysisを大規模なデータに適用するのは困難であった。しかしΞと何か(x)の積演算 Ξ* x =A/n * x -rct/n2 * x の計算の順番を、Aとxの積を計算してからrct/n2とxの積を引き算するという順番にすると、途中で莫大なメモリを必要とする密行列が発生しないため、少ないメモリで計算ができる、というのが特許文献1の要点であった。また randomizedSVDによって全ての特異値を計算しないようにするというのも特許文献1の2つめの要点であった。randomizedSVDは分解したい対象の行列には積演算 * 以外を実行しないため、演算子 * をclass delayedspmatrixに対して定義するだけで計算できるのが特許文献1の3つめの要点であった。
【００１４】
図4のdelayed sparse matrixの実装はpython言語以外のC++言語などのオブジェクト指向言語でも利用可能な実装方法である。遅延評価で効率化できる部分をデータ型delayedspmatrixによって人間が指定することで、自動最適化で生じるオーバーフローエラーなどを回避している。データ型の切り替えを人間が指定すると、他の必要な演算も自動で切り替わる半自動処理が可能なのが図4の方法の利点である。図11のrandomizedSVDは非特許文献3で提案されているrandomizedSVDのアルゴリズムとその実装であるpython scikit-learn-0.17.1 libraryのrandomized_svd関数と同じものである。ただしpython scikit-learn-0.17.1 libraryのrandomized_svd関数では積演算 * は safe_sparse_dotという関数で実装されており、この関数が class delayedspmatrix型の行列を受け取った時に遅延評価の実行が行なわれるように拡張を行う。図12にsafe_sparse_dotの実装例を示す。簡単のためオリジナルのsafe_sparse_dotにある密行列など疎行列以外の積演算について演算方法を切り変える部分は省略している。この様に図4の方法を利用すると元のプログラムをほぼ変更せずに、データ型の変更のみを人間が指定すると他の演算も自動的に効率化される。この方法を使えば非特許文献2のような疎行列のLU分解も簡潔に記述することが可能となる。
【００１５】
otsu-gramに図10のcorrespondence analysisのアルゴリズムを適用して出力される行列XまたはYが単語分散表現となる。行列X,Yを特異値で正規化した行列がcorrespondence analysisと呼ばれる場合もある。応用対象の性質によっては、この特異値で正規化した単語分散表現を利用した方が良い場合もある。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特願2017-007741 「Delayed Sparse Matrix」
【非特許文献】
【００１７】
【非特許文献１】Prabhat Totoo and Hans-Wolfgang Loidl "Lazy Data-oriented Evaluation Strategies" Proceedings of the 3rd ACM SIGPLAN Workshop on Functional High-performance Computing (2014)
【００１８】
【非特許文献２】Shen and Tao Yang,"Efficient Sparse LU Factorization with Lazy Space Allocation"  http://www.cs.rochester.edu/~kshen/papers/siam99.pdf (1999)
【００１９】
【非特許文献３】Nathan Halko, Per-Gunnar Martinsson and  Joel A. Tropp,"Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions",https://arxiv.org/abs/0909.4061,(2010)
【００２０】
【非特許文献４】T. Zesch, C. Mu ller, and I. Gurevych, "Using wiktionary for computing semantic relatedness" Proceedings of the 23rd National Conference on Artificial Intelligence AAAI08 (2008)
【００２１】
【非特許文献５】E. Agirre, E. Alfonseca, K. Hall, J. Kravalova, M. Pas ca, and A. Soroa, "A study on similarity and relatedness using distributional and wordnet-based approaches" Proceedings of The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics NAACL ’09. (2009)
【００２２】
【非特許文献６】E. Bruni, G. Boleda, M. Baroni, and N. K. Tran, "Distributional ompositionality. semantics in technicolor" Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (2012)
【００２３】
【非特許文献７】K. Radinsky, E. Agichtein, E. Gabrilovich, and S. Markovitch, “A word at a time: Computing word relatedness using temporal semantic analysis” Proceedings of the 20th International Conference on World Wide Web WWW ’11 (2011)
【００２４】
【非特許文献８】O.Levy,   Y. Goldberg,  and I. Dagan,  "Improving distributional similarity with lessons learned from word embeddings" TACL(2015)
【発明の概要】
【発明が解決しようとする課題】
【００２５】
密行列演算を前提としたプログラムのコードをほぼ変更することなく効率的に疎行列演算を実行できるように最小限度の手間で改造する手順。その手順を利用してn-gramのnの自動選択に相当する処理を少ないメモリで効率的に処理する。
【課題を解決するための手段】
【００２６】
メモリに収まりきらない行列データをディスクに保存するが、ディスク読み込み処理で計算が遅くならないようにディスク読み込み処理を(例えば数値一個ごとにディスク読み込みするような)細切れにせず、まとめて大きな塊を一括読み込みするようにする。ただし大きな塊を一括読み込みするにしても、一般的なパソコンのメモリーサイズ内に収まる範囲で読み込みするようにする。ディスク読み込みのタイミングは遅延評価としていつでも実行できるようにしておく。またディスク読み込み以外のメモリを少なくする手順も遅延評価として適切にスケジュールしたタイミングで実行するようにする。
【発明の効果】
【００２７】
n-gramのnを人間の直感に頼らないで自動で決定することに相当する処理ができる。特に自然言語処理の場合は単純に実装すると巨大なメモリを必要とするが、この問題を回避して効率的な処理ができる。単語分散表現として類似度の正確さが従来手法より大幅に向上し、自動翻訳などの従来の単語分散表現が利用されていた多くの自然言語処理への応用が期待できる。
【図面の簡単な説明】
【００２８】
【図１】英文中の単語"this"と"a"の共起関係を表わす #( this  *k  a ) のヒストグラム
【図２】otsu-gramを計算するアルゴリズム
【図３】otsu-gramを少ないメモリで計算するアルゴリズム
【図４】遅延メモリ行列のpython言語による実装
【図５】遅延メモリ行列のpython言語による実装の利用例
【図６】遅延ファイル行列のpython言語による実装
【図７】遅延ファイル行列のpython言語による実装の利用例
【図８】圧縮された行列データを解凍しないで積演算するるアルゴリズム
【図９】ハフマンコーディングで圧縮された行列データを解凍しないで積演算するるアルゴリズム
【図１０】疎行列データへのcorrespondence analysisを少ないメモリで計算するアルゴリズム
【図１１】randomized SVDアルゴリズム
【図１２】safe_sparse_dot関数
【発明を実施するための形態】
【００２９】
図3は図2のアルゴリズムの繰り返し処理を行列計算として書き直したものである。図3で出力される行列 Cresult は 図2のresultと同じotsu-gram行列である。図3では #(  w1 *k  w2 ) の値は行列Nkに格納されている。この行列Nkを図6のclass delayed_file_matrixのように実装すると必要なデータだけメモリに読み込んで、いらなくなったらデータをメモリから削除するという処理が効率的にできるようになる。
【００３０】
図6は行列データをディスクから読み込むという動作を遅延評価できるように拡張した行列データ型 class delayed_file_matrixである。その実行例を図7に示す。図6、図7はpython言語で実装されている。このようにディスクからの読み込み処理などのメモリ上にデータを配置する処理を遅延評価として必要になった時に後から実行できるようにする方法を遅延ファイル行列と呼ぶことする。遅延ファイル行列は特許文献１のDelayed Sparse Matrixの応用の1つである。また delayed_file_matrix はDelayed Sparse Matrixの実装であるdelayedspmatrixの継承classとして実装されている。図6では積演算を表す __mul__ 関数が実装されているが、他の行列演算も同様に実装することができる。図6では積演算を実行した時にディスク読み込み処理の遅延評価が実行されるようになっている。そのため図3では行列Nkと1の積という数値計算としては意味のない処理が記述されている。なお図3では行列Nkとの積演算以外でディスク読み込み処理は発生しないため,図6のアルゴリズムは積演算を実装している。この方法は行列要素の数値一個ごとにディスク読み読み込みするような細切れの処理よりも高速である。積演算と同様に += 演算も実装できる。+= 演算を利用すると図3のC,A,Ctotal,Atotalもdelayed_file_matrixにできるためメモリ使用量をさらに減らすことができる。
【００３１】
python言語に限らず一般的に行列などのデータを格納するclassはメンバー関数としてデータをsave,loadする関数を持っていることが多い。しかしpython言語の標準的な疎行列を格納するclassはメンバー関数としてデータをsave,loadする関数を持っていない。そのため図6ではデータをloadするメンバー関数を追加したclass mymatrixを定義している。class delayed_file_matrixは一般的なメンバー関数としてデータをloadする関数を持つ任意のclassに適用できるようになっている。この実装方法はpython言語だけでなくC++言語などのオブジェクト指向言語でも利用可能な形となっている。図7ではdelayed_file_matrixの利用例として、ディスクに保存された"tmp.npz"というファイルを行列の積演算の時に遅延評価で読み込む例が示されている。図3に現れる積演算は図7の実行例と同様に実装できる。
【００３２】
図6のmymatrixのload関数にファイルからのデータ読み込みではなく、in-memory zipで圧縮されたデータの解凍処理を記述すると、ディスク保存ではなくデータ圧縮によるメモリ利用量の減少が可能となる。この方法によるメモリ利用量の減少はディスクを利用した場合よりも少ないが速度は非常に高速である。
【００３３】
in-memory zipによるメモリ使用量の圧縮には、圧縮データの解凍時に大きなメモリを必要とする問題があった。この問題を解決したのが図8,図9のアルゴリズムである。図8,9ではデータの圧縮を行列の行ごとに個別に行なう。そして行列の積演算の実行時には行ごとに圧縮データの解凍をする。こうすることで積演算が実行中の行以外はデータ圧縮されたままになり,少ないメモリでの演算が可能となる。図8のCompressedDotと図9のHuffConpresDot関数が積演算を実行する関数である。図9は行列全体についてのHuffman Codingを求めてから、その最適なCodingを利用して行ごとの圧縮と解凍処理を行なう点が図8と異なっている。一般的に疎行列で表現されるデータは大部分の行列要素は0であり、次に多い要素は1で、その次は2、というように小さい要素ほど疎行列に現れる回数が多い傾向がある。そのため行列全体についてのHuffman Codingを一度求めてから圧縮すると、より効率的な演算となる傾向がある。
【００３４】
これまで述べてきたメモリを効率的に利用する方法は全て class delayedspmatrix またはその継承型のデータを利用していたことを思いだそう。これらのメモリを効率的に利用する方法は一般化して以下のようにまとめられる。2-gramは行列として表現すると大部分の要素がゼロなため密行列ではなく疎行列として扱われることが多い。otsu-gram行列も同様である。自然言語処理に限らず一般的に疎行列として扱われるデータを密行列としてメモリ上に展開すると数十倍のメモリが必要となることが多い。同様にzip圧縮されたデータは解凍すると数倍の大きさになることが多い。ファイルに書き出されたデータはメモリサイズより大きなデータなことがあり、このデータを密行列としてメモリ上に展開するとメモリオーバーフローとなる。このように密行列としてメモリ上に展開するとメモリオーバーフローとなる可能性のある疎行列、圧縮データ、ファイルデータなどをまとめて過メモリ行列と呼ぶこととする。過メモリ行列の特異値分解は図11に示したrandomizedSVDで行なうことができる。このプログラムはオリジナルのrandomizedSVDと同じであるが、演算子*が過メモリ行列にも定義されており、その定義は遅延評価になっている点だけが異なる。このように密行列を前提として記述された特異値分解,固有値分解、ＬＵ分解などの行列計算プログラムを、疎行列などの過メモリ行列にも適用するには、過メモリ行列のデータ型も演算できよるうに積や和演算のoperator overloadをすれば良いだけである。ただし単純にデータ型の変更だけをするとメモリオーバーフローとなる。そこでアルゴリズム中のメモリオーバーフローとなる場所を人間が見つけて、その部分だけを遅延評価をするようにclass delayedspmatrix、またはその継承型データとしてプログラム中に目印をつける。すると目印に従って適切なデータ型の計算が実行されてメモリオーバーフローが生じないようになる。例えばrandomizedSVDを利用した図１０のcorrespondence analysisの例がそうである。この枠組みとclass delayedspmatrixを遅延メモリ行列と呼ぶ。この最適化処理を自動的にコンパイラ最適化で実行するのが困難であることは非特許文献1で述べられており、人間が最適化のポイントを見つける必要がある。
【００３５】
図1のヒストグラムに大津の2値化を適用するのがotsu-gramであった。しかし大津の2値化よりも単純な方法で図1の右端の領域を切り捨てることができる。重複も含めた文章中の全ての単語の数をLとして,文章中に"this"が現われる確率 P("this")と、文章中に"a"が現われる確率 P("a")を使うと次の近似が言える。ここでこの近似式は kに依存しない点に注意しよう。
【００３６】
(数3)
#( this  *k  a ) ≒  P("this") P("a") L
【００３７】
この近似値よりも低い出現回数はノイズとみなすことができる。ノイズの項をゼロとみなすデルタ関数を使って以下の近似をする。
【００３８】
(数4)
#(  w1 *k  w2 ) ≒ #cut(  w1 *k  w2 ) = #(  w1 *k  w2 ) δ( #(  w1 *k  w2 )  ＞ P(w1) P(w2) L)
【００３９】
ここで #cut はノイズを無視して共起回数を数えることを意味する記号である。この近似を使ってotsu-gram行列を以下で近似できる。
【００４０】
(数5)
CTC[w1,w2] =  Σ k < k max    #cut (  w1 *k  w2 ) 
【００４１】
この近似 CTCをtailcut-gram(TC)と呼ぶ。表1のTCはCTCにcorrespondence analysisを適用して単語分散表現を計算した場合の精度を示したものである。また #(  w1 *k  w2 ) ではなく #cut (  w1 *k  w2 ) に対してotsu-gramを計算することもできる。この結果を表1のOG+TCで示す。 
【００４２】
n-gramの情報を要約する方法としてPitman-Yor Processが知られている。#(  w1 *k  w2 ) を考える時、単語 w1、 w2 とそれ以外である *  の3つの単語の関係についてPitman-Yor Processの考え方を適用すると、次の割引いた値に#(  w1 *k  w2 ) を置き換えるのが妥当である。
【００４３】
(数6)
#decay  (  w1 *k  w2 ) = #(  w1 *k  w2 ) (1-P(w1) - P(w2) ) k 
【００４４】
ここで #decay  は遠い単語ほど(1-P(w1) - P(w2) ) k だけ減衰させて数えることを表す記号である。これを使ってotsu-gramの近似を以下のように計算できる
【００４５】
(数7)
CPY[w1,w2] =  Σ k < k max   #decay (  w1 *k  w2 ) 
【００４６】
この近似 CPYをself pitman-yor-gram(PY)と呼ぶ。表1のPYはCPYにcorrespondence analysisを適用して単語分散表現を計算した場合の精度を示したものである。また #(  w1 *k  w2 )
ではなく #decay (  w1 *k  w2 ) に対してotsu-gramを計算することもできる。この結果を表1のOG+PYで示す。 
【００４７】
self pitman-yor-gramとtailcut-gramの両方の考え方を次式のように適用することもできる
【００４８】
(数8)
#decay-cut (  w1 *k  w2 ) =  #decay(  w1 *k  w2 )  δ( #decay(  w1 *k  w2 )  ＞ P(w1) P(w2) L)
【００４９】
この方法でotsu-gramを近似すると次式となる。
【００５０】
(数9)
CPY+TC[w1,w2] =  Σ k < k max   #decay-cut (  w1 *k  w2 ) 
【００５１】
表1のPY+TCはCPY+TCにcorrespondence analysisを適用して単語分散表現を計算した場合の精度を示したものである。また #(  w1 *k  w2 )
ではなく #decay-cut (  w1 *k  w2 ) に対してotsu-gramを計算することもできる。この結果を表1のOG+PY+TCで示す。 
【００５２】
self pitman-yor-gramとtailcut-gramはotsu-gramから省略可能な要素を削除した非可逆圧縮とみなすことができる。OG,PY,TCのどの組合せについても単語分散表現を計算すると既存の方法であるword2vec、fastText、GloVeよりも大幅に精度が上回っているのが表1からわかる。なお背景技術では表1の値は説明を簡単にするために正解率と述べたが、正確には順位相関係数の値である。表1の正確な計算方法は、表1と同様の比較を行なっている非特許文献8を参照されたい。
【実施例１】
【００５３】
図10のcorrespondence analysisのアルゴリズムにotsu-gramを適用して単語分散表現を計算した例を表1に示す。既存法よりも大幅に精度が向上しているのがわかる。
【表１】
2020009045.tif 000002
【産業上の利用可能性】
【００５４】
自然言語処理の特徴量として様々な処理に利用可能である。また自然言語処理以外の時系列データの特徴としても利用可能である。
【図１】
2020009045.tif 000003
【図２】
2020009045.tif 000004
【図３】
2020009045.tif 000005
【図４】
2020009045.tif 000006
【図５】
2020009045.tif 000007
【図６】
2020009045.tif 000008
【図７】
2020009045.tif 000009
【図８】
2020009045.tif 000010
【図９】
2020009045.tif 000011
【図１０】
2020009045.tif 000012
【図１１】
2020009045.tif 000013
【図１２】
2020009045.tif 000014