(57)【要約】【課題】再計算についての最適化を行う。【解決手段】最適化装置は、時間消費算出部と、戦略取得部と、を備える。時間消費算出部は、ニューラルネットワークの演算を示すグラフを構成する演算ノードについて、計算結果が記憶された他の前記演算ノードから、着目演算ノードにおける再計算に必要となる時間消費を算出する。戦略取得部は、前記時間消費に基づいて、演算結果を記憶させる前記演算ノードに関するデータを取得する。【選択図】図３
2020135748.tif 000002
【特許請求の範囲】
【請求項１】
ニューラルネットワークの演算を示すグラフを構成する演算ノードについて、
計算結果が記憶された他の前記演算ノードから、着目演算ノードにおける再計算に必要となる時間消費を算出する、時間消費算出部と、
前記時間消費に基づいて、演算結果を記憶させる前記演算ノードに関するデータを取得する、戦略取得部と、
を備える最適化装置。
【請求項２】
前記着目演算ノードにおける演算結果を再計算する場合に必要となるメモリ消費を算出する、メモリ消費算出部と、を備え、
前記戦略取得部は、前記メモリ消費及び前記時間消費に基づいて、演算結果を記憶させる前記演算ノードに関するデータを取得する、請求項１に記載の最適化装置。
【請求項３】
前記メモリ消費算出部は、前記グラフにおいて、順伝播処理における演算順序に基づいた下方集合であって、当該下方集合に含まれる前記演算ノードにより前記着目演算ノードの再計算が可能である下方集合を用いて前記メモリ消費を算出する、請求項２に記載の最適化装置。
【請求項４】
前記メモリ消費算出部は、順伝播処理において前記着目演算ノードに到達するまでに記憶されている領域における前記メモリ消費に基づいて、当該着目演算ノードの前記メモリ消費を算出する、請求項３に記載の最適化装置。
【請求項５】
前記メモリ消費算出部は、前記着目演算ノードにおける演算結果を記憶するためのメモリ消費に基づいて、当該着目演算ノードの前記メモリ消費を算出する、請求項３又は請求項４に記載の最適化装置。
【請求項６】
前記メモリ消費算出部は、前記着目演算ノードを境界として有する前記下方集合の演算結果を記憶するための前記メモリ消費に基づいて、当該着目演算ノードの前記メモリ消費を算出する、請求項３から請求項５のいずれかに記載の最適化装置。
【請求項７】
前記メモリ消費算出部は、前記着目演算ノードにおける勾配を演算するタイミングで他の前記演算ノードにおける勾配の演算結果が使用される場合に、当該他の演算ノードにおける勾配の演算結果を記憶するための前記メモリ消費に基づいて、当該着目演算ノードの前記メモリ消費を算出する、請求項３から請求項６のいずれかに記載の最適化装置。
【請求項８】
前記時間消費算出部は、前記着目演算ノードを境界として有する前記下方集合において演算結果が記憶されている前記演算ノードからの再計算時間を算出して前記時間消費を算出する、請求項３から請求項７のいずれかに記載の最適化装置。
【請求項９】
前記メモリ消費算出部は、再計算に不要な前記演算ノードの少なくとも一部を除外して、前記メモリ消費を算出する、請求項３から請求項８のいずれかに記載の最適化装置。
【請求項１０】
前記戦略取得部は、前記メモリ消費が算出された場合、算出された前記メモリ消費に対応する前記時間消費が最小となるものを取得する、請求項２から請求項９のいずれかに記載の最適化装置。
【請求項１１】
ニューラルネットワークの演算を示すグラフを構成する演算ノードについて、
計算結果が記憶された他の前記演算ノードから、着目演算ノードにおける再計算に必要となる時間消費を算出し
前記時間消費に基づいて、演算結果を記憶させる前記演算ノードに関するデータを取得する、
を備える最適化装置。
最適化方法。
【請求項１２】
コンピュータに、
ニューラルネットワークの演算を示すグラフを構成する演算ノードについて、
計算結果が記憶された他の前記演算ノードから、着目演算ノードにおける再計算に必要となる時間消費を算出する手段、
前記時間消費に基づいて、演算結果を記憶させる前記演算ノードに関するデータを取得する手段、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化装置、最適化方法及びプログラムに関する。
【背景技術】
【０００２】
機械学習においては、順伝播処理を行い、その結果に基づいて逆伝播処理を行うことにより訓練が行われることが多い。逆伝播処理を実行する際には、順伝播処理において各層で計算された数値等が必要となり、これら計算結果等を記憶する必要がある。深層学習モデルの学習にはGPU（Graphics Processing Unit）が利用されることが多いが、利用できるメモリは有限であるため高解像度の画像や大きなバッチサイズ等を利用するときの障害となることがある。メモリに乗り切らない数値等がある場合には、途中経過が必要となる箇所まで再度順伝播処理を行うことにより、逆伝播を実行する。このような再計算を行う場合、全ての数値の再計算を行うと、訓練時間が増大することが多い。このような時間の増大を回避するため、途中経過をある程度メモリに保存する手法がある。しかしながら、どの途中経過をメモリに格納しておくかは任意であり、どの数値等を格納しておくかにより計算時間が大きく異なることもあり、メモリに格納する数値等を選定するのは困難であった。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】T. Chen, et. al., "Training Deep Nets with Sublinear Memory Cost," arXiv:1604.06174, [インターネット], 2018.12.18閲覧, https://arxiv.org/abs/1604.06174
【発明の概要】
【発明が解決しようとする課題】
【０００４】
再計算についての最適化を行う、最適化装置、最適化方法及びプログラムを提供する。
【課題を解決するための手段】
【０００５】
一実施形態によれば、最適化装置は、時間消費算出部と、戦略取得部と、を備える。時間消費算出部は、ニューラルネットワークの演算を示すグラフを構成する演算ノードについて、計算結果が記憶された他の前記演算ノードから、着目演算ノードにおける再計算に必要となる時間消費を算出する。戦略取得部は、前記時間消費に基づいて、演算結果を記憶させる前記演算ノードに関するデータを取得する。
【図面の簡単な説明】
【０００６】
【図１】グラフデータの一例を示す図。
【図２】グラフデータにおける近傍の一例を示す図。
【図３】下方集合の一例を示す図。
【図４】下方集合の一例を示す図。
【図５】一実施形態に係る最適化装置の機能を示すブロック図。
【図６】一実施形態に係る最適化の処理の流れを示すフローチャート。
【図７】一実施形態に係るハードウェア実装例を示す図。
【発明を実施するための形態】
【０００７】
以下、図面を参照して実施形態について詳しく説明する。なお、図面は、一例として模式的に示すものであり、これら図面に限定されるものではない。
【０００８】
まず、本実施形態の概略について説明する。本実施形態において、順伝播及び逆伝播の処理を示す計算グラフにおけるノードは、変数の入力又は計算結果を示し、エッジは、変数を計算するための依存関係を示す。このグラフは、DAG（有向非巡回グラフ：Directed acyclic graph）で表される。
【０００９】
具体的には、変数vを計算するために他の変数w1、w2、・・・、wkが必要な場合には、変数v、w1、w2、・・・、wkに対応するノードと、これらに対する、エッジ(w1,v)、(w2,v)、・・・、(wk,v)がグラフ内に存在する。
【００１０】
図１は、訓練における順伝播及び逆伝播の状態を示すグラフである。計算グラフは、入次数が０のノードを入力ノードと呼び、出次数が０のノードを出力ノードと呼ぶ。そして、それ以外のノードを中間ノードと呼ぶ。計算グラフは、変数の値を計算する順伝播部と、これらの勾配計算を表す逆伝播部と、を備える。
【００１１】
図中の太い矢印は、順伝播、逆伝播のそれぞれの処理におけるエッジを示す。一方で、細い矢印は、逆伝播において、順伝播の結果、あるいは、入力ノードからの依存を表すエッジを示す。説明のため、順伝播部のうち、中間ノードと出力ノードに対応する部分を、グラフG=(V,E)と記載する。
【００１２】
xは、入力データであり、yは、出力データである。W1、W2、W3は、それぞれ、中間変数のh1、h2、h3を所定の演算により求めるために必要となる変数であり、訓練により更新されてもよい入力変数である。例えば、中間変数h1は、ニューラルネットワークを構成するある１層において入力データxと、入力変数W1について演算を行うことにより取得される。同様に、次の層において中間変数h1について演算を行うことによりa1が取得される。最終層における演算により、出力データyが取得される。ノードは、上記のように変数の入力又は演算結果を示すものであり、入力ノード以外のノードにおいては、演算の結果（当該ノードが対応する層の出力変数）がノードの中に記載されている。すなわち、グラフG=(V,E)は、図に示すように、順伝播部から入力データ及び入力変数を表すノードであるx、W1、W2、W3に対応する入力ノードを除いた、h1、a1、h2、a2、yが示される演算ノード及びエッジを含むグラフである。
【００１３】
逆伝播部でも、同様に各層における演算を繰り返すことにより、誤差を逆伝播する。例えば、出力データyに基づいて勾配gyを算出する。入力変数W3と勾配gyに基づいてga2を取得する。中間変数a2と勾配gyに基づいて勾配gW3を取得する。このように、順伝播部のノードである入力変数と中間変数を用いて、逆伝播処理がグラフに基づいて実行される。
【００１４】
この場合、例えば、順伝播処理において、中間変数a2がメモリに格納されていると、gW3は、gyと、メモリに格納されているa2とを用いて逆伝播処理を行うことにより取得される。逆にa2がメモリに格納されていない場合には、h2がメモリに格納されていると、このh2を用いて順伝播処理に基づいてa2を再計算することにより取得し、取得したa2を用いてgW3を取得する。h2もメモリに格納されていない場合には、同様にメモリに格納されているh2を取得するのに必要となる変数まで遡って順伝播処理を行い、h2を再計算することにより取得し、その後に、a2を再計算により取得する。
【００１５】
このように、メモリに格納されている変数に基づいて、順伝播処理の再計算を行うことにより、メモリに格納されていない変数を取得して逆伝播処理を実行する。この処理は、入力データと、各入力変数まで必要な箇所における逆伝播処理が終了するまで繰り返される。
【００１６】
ニューラルネットの計算においては、入力ノード及び出力ノードが消費するメモリはわずかである。一方で、中間ノードの消費するメモリが大きいことが多い。すなわち、メモリを逼迫する要因となるのは、主に、グラフGの部分における変数となる。限られたメモリ内においてどのように訓練時間を削減するために、グラフG内におけるいずれの変数をメモリに格納し、いずれの変数を再計算で取得するかを最適化する。
【００１７】
この最適化に必要となる定義について説明する。図２は、一例として、グラフの一部を抜き出したものである。ノードの集合Sに着目する。Sは、グラフGの全てのノードの集合であるVの部分集合（S⊆V）である。グラフGのノードvに対応する変数を計算するのに掛かる時間をTv、変数を格納するのに必要なメモリ量をMvとする。これらの値は、非負整数であるとする。
【００１８】
Tvは、例えば、単位時間の整数倍、又は、ノードごとに計算に掛かると考えられる整数で表した時間の指標により示される。Mvは、例えば、ビット、又は、バイト等のメモリの量を表す指標により示される。ノード集合Sに対して、T(S)=Σv∈STv、M(S)=Σv∈SMvと定義する。
【００１９】
図２に示すように、ノード集合S⊆Vに対して、δ−(S)をv∈Sに入ってくるノードの集合、δ+(S)をv∈Sから出て行くノードの集合とする。
【００２０】
本実施形態において、ノード集合L⊆Vに対してV−LからLに向かうエッジが存在しない場合、Lを下方集合（lower set）と記載する。「−」は、差集合（全体集合に対しては補集合）を表す。Lに対して、Lの境界を∂(L)＝δ−(V−L)∩Lと定義する。グラフGの下方集合全体により構成される集合族をLGと記載する。この記載によれば、Vと空集合φは、LGに含まれる。
【００２１】
図３は、下方集合とその境界について示す図である。例えば、グラフGの全てのノードとエッジが示されている。この場合、L2＝Vであり、L1は、L2の部分集合である。集合L2−L1においてL1のノードへと向かうエッジが存在しないので、L1は、L2の下方集合である。上記の定義にしたがうと、斜線で表したノードがL1の境界∂(L1)となる。
【００２２】
L2＝Vの例を示したが、これには限られない。図４は、多数の下方集合を備えるグラフの例を示す図である。このように、グラフGは、多数の下方集合を備えるノードの集合Vを備えて構成されていてもよい。この場合、V＝Lkであり、LGは、L1、L2、・・・、Lkの各集合を含む。なお、図３、図４においては、ごく単純な計算グラフを示しているに過ぎないが、これは例として示したものであり、より複雑なグラフを有するネットワーク構造であっても同様に定義できる。
【００２３】
上記の定義により、グラフGに含まれるノードについて下方集合について、L1⊂L2⊂・・・⊂Lk=Vなる下方集合の増加列(L1, L2, ・・・, Lk)を決定することが可能である。この増加列に基づいて、順伝播の計算と、逆伝播の計算を実行することができる。以下、このような増加列のことを、戦略とも記載する。
【００２４】
ここで、V1＝L1、Vi＝Li−Li−1（i≧2）とする。本実施形態における下方集合の定義の下では、Li＝V1∪V2∪・・・∪Viであり、任意のj＜iについて、Viのノードは、Ljのノードから到達可能である。
【００２５】
順伝播においては、V1、V2、・・・、Vkの順に演算を実行する。Viの各ノードを計算する順番は、複数通りあり得るが、どのような順番で計算してもよい。Viの計算が完了した後、Viの計算結果は、∂(Li)のノードを除き、メモリから解放する。
【００２６】
逆伝播においては、順伝播とは逆に、Vk、Vk−1、・・・、V1の順で、各Viのノードの勾配を計算する。Viの勾配を計算する際には、Viの順伝播における計算結果が必要となる。メモリにViの計算結果がメモリに格納されている場合、格納されている値を用いて勾配を計算する。一方で、Viの計算結果がメモリに格納されていない場合、メモリに格納されている∂(Li−1)から再計算を行い、順伝播と同様に計算することによりViの値を取得して勾配を計算する。逆伝播においても順伝播と同様に、Viの各ノードの勾配を取得し、当該勾配を用いてパラメータ更新等の演算が終わった後に、δ+(Li−1)∩Vi のノードを除いて勾配情報を消去してもよい。
【００２７】
順伝播のタイミングにおいて、iステップ目の終了後にメモリに保存されている頂点集合をUiとする。Ui＝∪ij=1∂(Lj)として表すことができる。順伝播の全ての処理が終了した後のメモリ使用量は、Ukと表すことができる。これらのノードについては、上記のように再計算を行う必要は無いので、これらのノードについて再計算を行う時間Σv∈UkTvが全て再計算を行う場合と比べて短縮することができる時間となる。
【００２８】
消費メモリの量は、その計算過程で異なる。この消費メモリがピークとなるのは、逆伝播処理の途中のタイミングである。頂点集合Viの勾配を計算する場合、順伝播においてiステップ目の終了直後の頂点集合は、Uiである。再計算の前のタイミングでM(Ui−1)のメモリが消費されている。さらに、Vi内にある中間ノードに対して再計算を実行し、勾配を計算する必要がある。これには、2M(Vi)のメモリを消費する。
【００２９】
さらに、勾配計算のために、Viの近隣のノードの計算結果が必要となる可能性がある。例えば、Viよりも前のステップでの勾配情報が必要となることがある。この場合、M(δ+(Li)−Li)のメモリが演算の実行に利用される。また、例えば、順伝播においてh＝f(v1, v2, v3)という演算があると、v2の勾配の演算にはv1とv3の情報が使用される。このような場合、M(δ−(δ+(Li))−Li)のメモリが演算の実行に利用される。
【００３０】
これら４つのメモリ消費の和をMiとおく。すなわち、Mi＝M(Ui−1)＋2M(Vi)＋M(δ+(Li)−Li)＋M(δ−(δ+(Li))−Li)となる。本実施形態においては、消費メモリのピーク値maxi∈{1,2,…,k}Miを最適化に用いる。GPU等に依存して訓練に割り当てられるメモリ割当量(memory budget)Bが分かっている状態において、訓練時間を最小化する問題を考える。
【００３１】
そこで、以下のような最適化問題を解くことに帰着する。
【００３２】
計算グラフG＝(V,E)とメモリ割当量B∈Nが与えられる。このGに対する下方集合の増加列で消費メモリがBに収まる、すなわち、maxi Mi≦Bであるようなものの中で、追加で発生する計算時間を最小化するものを求める。Bが小さすぎる場合には、制約を満たすものが存在しない場合があるが、その場合は、「存在しない」と出力する。
【００３３】
なお、本問題の定式化においては、消費メモリの総数しか考慮されていないが、現実的には、変数の情報をGPU等のメモリ上のどこに配置するかを決定する。もし、メモリ領域に余裕が全く無い場合、メモリを確保する度に既存の確保された領域を再配置しなければならなくなる可能性がある。しかしながら、このような状況は、メモリ割当量Bを実際に使用可能なメモリ量の上限よりも少し低めに見積もることで回避しやすいと期待される。また、実際にメモリの再配置に掛かるオーバーヘッドは、大きくない。
【００３４】
ノードの計算時間Tvは、任意の値としていたが、比較的粗い粒度で離散化を行うことでTvは、小さい定数となるように調整できる。以降では、ノードの計算時間の合計T(V)は、ノード数|V|に比例する程度に小さいと仮定する。T(V)を十分小さいと仮定すると、現実的に利用されるニューラルネットワークにおける計算グラフGにおいては、下方集合の族LGの個数がノード数|V|の多項式程度に小さくなる。そこで、以下においては、LGの個数が|V|の多項式程度に小さいと仮定する。Tvは、例えば、実測値Tv'の最大値Tmaxを取得し、任意の自然数をn、実数を整数に丸める関数をround(・)として、Tv＝round(n・Tv'／Tmax)とすることができる。上記は一例として示したものであり、Tvの定義は、これに限られるものではなく、後述するように演算により固定値とする等、適切に定義することもできる。
【００３５】
この問題を、動的計画法に基づいて処理する。下方集合の増加列(L1, L2, ・・・, Lk)を求める場合に満たすことは、Li⊂Li+1、及び、Mi≦Bである。ある下方集合Lと、0≦t≦T(V)に対して、最適メモリ消費opt[L, t]を、(L1, L2, ・・・, Li)で上記の制約を満たし、かつ、列の最後LiがLに一致して時間消費がtに等しいものの中において、順伝播処理実行時に忘却しない変数Uiのメモリ使用量M(Ui)の最小値とする。このような(L1, L2, ・・・, Li)が存在しない場合には、opt[L, t]＝∞とする。
【００３６】
最終的に求めたい戦略は、L＝Vの場合である。opt[L, t]＜∞となるtが存在する場合、計算時間tの戦略が存在する。そのような条件を満たす最小のtに基づいて、動的計画法の解を復元すれば、元の戦略が得られる。そのようなtが存在しない場合は、解が存在しないものとする。
【００３７】
本実施形態に係る最適化装置の構成について説明する。図５は、本実施形態に係る最適化装置の機能を示すブロック図である。最適化装置１は、入力部１０と、記憶部１２と、初期化部１４と、メモリ消費算出部１６と、時間消費算出部１８と、更新部２０と、抽出部２２と、戦略取得部２４と、出力部２６と、を備える。
【００３８】
入力部１０は、最適化に必要となる各種データの入力を受け付ける。最適化に必要となるデータとは、例えば、最適化の対象となるグラフデータ、メモリと時間の消費データ、及び、メモリ割当量等のデータである。
【００３９】
記憶部１２は、最適化装置１に必要となる各種データを記憶する。例えば、入力部１０から入力されたデータを記憶部１２に記憶させ、必要となるタイミングにおいて各部が記憶部１２に格納されているデータを参照して演算を実行する。この他、演算途中のデータや最適化された結果のデータ等を記憶させてもよい。
【００４０】
初期化部１４は、最適化に用いる各データの初期化を行う。例えば、戦略の初期化を実行する。プログラムによりハードウェアで実行される場合には、配列等のメモリの確保等を、この初期化部１４が行ってもよい。
【００４１】
メモリ消費算出部１６は、LGに含まれる下方集合におけるメモリ消費を算出する。例えば、着目している下位集合における上述した４つのメモリ消費の種類に基づいて、メモリ消費量を算出する。なお、着目している下位集合とは、ループ演算における現ループにおいて評価の対象となる下位集合のことを示す。
【００４２】
時間消費算出部１８は、LGに含まれる下方集合における時間消費を算出する。例えば、上記のT(V)に基づいて、着目している時間に基づいて算出する。なお、着目している時間とは、ループ演算における現ループにおいて評価の対象となる時間のことを示す。
【００４３】
更新部２０は、着目している時間及び下位集合に基づいて、メモリ消費算出部１６が算出したメモリ消費と、時間消費算出部１８が算出した時間消費と、に基づいて、下位集合と時間との組み合わせにおけるメモリ消費量を更新する。
【００４４】
抽出部２２は、更新部２０により更新された下位集合と時間との組み合わせにおけるメモリ消費量に基づいて、全てのノードの集合Vにおける最適なopt[V, t]を抽出する。
【００４５】
戦略取得部２４は、抽出部２２が抽出した最適なopt[V, t]に基づいて、最適な戦略(L1, L2, ・・・, Lk)を取得する。
【００４６】
出力部２６は、戦略取得部２４が取得した戦略を出力する。なお、出力とは、最適化装置１の外部への出力はもちろんこと、記憶部１２に記憶することも含む概念であってもよい。
【００４７】
これらの各部の動作により、着目している演算ノードについて、当該着目演算ノードより入力ノード側にある演算ノードから、当該着目演算ノードまで再計算を行う場合に、どの程度のメモリ消費及び時間消費があるかを算出する。また、メモリ消費がメモリ割当量以下である場合には、当該メモリ消費を最小メモリ消費として記憶する。より詳しくは、後述する動作を繰り返すことにより、各演算ノードについて、それよりも入力側にある演算ノードのいずれの結果を用いた場合に、当該演算ノードの結果を得るためにどの程度の再計算時間が必要であり、その再計算を行うために必要となるメモリ消費がどの程度になるかを算出する。
【００４８】
この際、各着目演算ノードにおいて最小メモリ消費が存在する場合には、当該最小メモリ消費と、その場合における当該着目演算ノードまでに掛かる再計算時間の合計と、を紐付けて記憶しておく。このように記憶しておくことにより、各着目演算ノードの出力を記憶する場合においても記憶しない場合においても、当該着目演算ノードにおけるメモリ消費と時間消費とを算出することができる。
【００４９】
次に、最適化装置１の処理の流れについて説明する。図６は、本実施形態に係る処理の流れを示すフローチャートである。
【００５０】
まず、入力部１０を介してデータの入力を受け付ける（Ｓ１００）。入力されるデータは、例えば、ネットワークの構成に関するデータである。特に、変数と演算を行うノード及びそれらの流れを示すエッジの情報、及び、メモリ消費と時間消費に関するデータ、メモリ割当量に関するデータが含まれるデータである。メモリ消費に関するデータは、例えば、各ノードvにおけるメモリ消費Mvを含むデータである。一方、時間消費に関するデータは、各ノードvにおいて入力データが入力された場合に演算に掛かる時間Tvを含むデータである。これらの入力されたデータは、記憶部１２に記憶されてもよい。また、これらのデータは、記憶部１２に記憶されているものであってもよい。この場合、Ｓ１００のステップは、省略してもよい。
【００５１】
次に、初期化部１４は、最適化における変数の初期化を行う（Ｓ１０２）。グラフGの全ての下方集合を、そのサイズが昇順となるように並べた集合をLorderとして初期化する。例えば、Lorderの最初の要素は、空集合φであり、最後の要素は、Vを示すものである。さらに、opt[φ, 0]を、0に初期化し、L∈Lorderに対して、opt[φ, 0]以外のopt[L, t]を0≦t≦T(V)に対して∞に初期化する。その他初期化が必要な変数がある場合には、それらの各変数をさらに初期化してもよい。
【００５２】
次に、最適化の処理を実行する。下方集合及び時間について、それぞれループ処理を行う（Ｓ１０４，Ｓ１０６）。
【００５３】
Ｓ１０４〜Ｓ１１８のループにおいては、Lorderに属する各下方集合について、順番に演算を行う。すなわち、下方集合のうちサイズの小さい集合から順に、Ｓ１０６〜Ｓ１１６のループの演算が実行される。
【００５４】
Ｓ１０６〜Ｓ１１６のループにおいては、Ｓ１０４からのループで選択されている下方集合Lを自らの下方集合として有するL'∈Lorderのそれぞれについて、それぞれの時間消費t（={0, 1, … , T(V)}）におけるメモリ消費を算出し、メモリ消費と時間消費との関係を更新する処理を実行する。すなわち、各下方集合L'（L∈L'）においてL'まで処理するための各時間消費について、演算を実行する。このループにおいては、例えば、下方集合からL'を抽出し、抽出されたL'に対して、各時間消費tにおいて以下のメモリ消費の算出を行う。
【００５５】
ループ内においては、例えば、以下の順に演算が実行される。演算の順番が前後してもよい処理については、適宜処理の順番を入れ替えることが可能である。例えば、Ｓ１０８とＳ１１０の処理は、入れ替えてもよいし、Ｓ１１０の処理をＳ１１２においてＹＥＳと判断された後に実行してもよい。
【００５６】
まず、メモリ消費算出部１６は、メモリ消費を算出する（Ｓ１０８）。例えば、上述したメモリ消費のそれぞれのパターンに基づいて、V'=L'−Lとして、M=opt[L, t]＋2M(V')＋M(δ+(L')−L')＋M(δ−(δ+(L'))−(L'))を時間消費tにおけるメモリ消費として算出する。
【００５７】
次に、時間消費算出部１８は、時間消費を算出する（Ｓ１１０）。例えば、時間消費t'を、t'=t＋T(V'−∂(L'))として算出する。
【００５８】
次に、更新部２０は、Ｓ１０８で算出したメモリ消費Mとメモリ割当量Bとを比較する（Ｓ１１２）。メモリ消費Mがメモリ割当量B以下である場合（Ｓ１１２：ＹＥＳ）、最小メモリ消費を更新する（Ｓ１１４）。例えば、M≦Bであれば、opt[L', t']=min(opt[L', t'], opt[L, t]＋M(∂(L')−L)として、更新する。ここで、opt[L', t']が更新された場合には、これらのL'、t'において更新されたことを記憶してもよい。すなわち、本段落における処理は、m'＝opt[L, t]＋M(∂(L')−L)を計算した後に、opt[L', t']＞m'であるならば、opt[L', t']＝m'として更新し、optarg[L', t']＝(L, t)として、これらの更新するための値を記憶する処理としてもよい。
【００５９】
上記のように最小メモリ消費を更新した後、又は、メモリ消費Mがメモリ割当量Bを超えた場合（Ｓ１１２：ＮＯ）、次の時間消費tについて演算を実行する。時間消費tについてのループが終了すると、次の下方集合L'について演算を実行する。このように、Ｓ１０６〜Ｓ１１６の処理が繰り返される。
【００６０】
全ての下方集合L'及び時間消費tについて演算が終了した後、Lorderに含まれる次のLに対して、同様の処理を繰り返す（Ｓ１０４〜Ｓ１１８）。
【００６１】
Lorderに含まれる下方集合Lについて演算が終了した後、抽出部２２は、最小消費時間の最適メモリ消費を抽出する（Ｓ１２０）。opt[V, t]＜∞を満たすものがある場合、その中から最小のt0を有するものを抽出する。
【００６２】
次に、戦略取得部２４は、抽出したt0に基づいて、そのようなt0となる戦略を取得する（Ｓ１２２）。この処理により、最小の再計算時間であり、かつ、メモリ消費がB以下となる戦略を取得することができる。例えば、Ｓ１１４において最小メモリ消費が更新されたタイミングにおいて、記憶部１２にその最小メモリ消費となるようなt'とL'とを記憶しておくことにより、t0が抽出されると記憶部１２に記憶されているデータに基づいて戦略を取得することができる。すなわち、記憶したoptarg[L, t]を(V, t0)から逆順に辿ることにより、Lの増加列(L1, … , Lk)を戦略として取得する。
【００６３】
さらに、戦略取得部２４は、このように取得された戦略に基づいて、いずれの演算ノードにおける結果をメモリに格納するかを決定することが可能となる。訓練を実行する場合には、順伝播処理において、この決定された演算ノードの結果をメモリに格納し、他の演算ノードの結果をメモリに格納しない。逆伝播処理において、必要に応じて、メモリに格納されている値、及び、メモリに格納されている値から再計算された値を用いて、例えば、勾配を算出し、ネットワークを更新する。なお、出力部２６は、戦略取得部２４が取得した戦略そのものを出力してもよいし、当該戦略から決定された演算結果を記憶する演算ノードを出力してもよい。また、opt[・]＜∞を満たす戦略が存在しない場合には、戦略が存在しない旨を出力する。
【００６４】
時間消費tについては、上述したように適切に離散化され、各演算ノードVにおける演算時間を離散化してTv（tG(V)）として記憶部１２に記憶しておいてもよいし、このデータを入力部１０から入力してもよい。各演算ノードVにおける演算時間を正確に計算することが簡単では無い場合には、各演算ノードにおける演算を適切に見積もり、当該見積もった時間をTvとしてもよい。例えば、畳み込み演算のノードは、Tv=10とし、その他のノードは、Tv=1としてもよい。その他、重い演算が存在するノードにおいては、適宜1以外の値を割り当てるようにしてもよい。このように、演算によりTvをあらかじめ決定するようにしてもよい。あらかじめ離散化した値を割り当てる場合には、この割り当てた値を入力部１０から入力してもよいし、入力部１０からはノードごとに演算の種類について入力し、最適化装置１内で時間消費の離散化した値を付与してもよい。
【００６５】
以上のように、本実施形態によれば、逆伝播を実行する場合におけるメモリの使用及び順伝播処理の再計算の時間の双方のバランスがとれるように最適化を行うことが可能である。メモリに比較的余裕がある場合には、メモリを消費しつつも再計算の時間効率を向上し、メモリに余裕が無い場合には、メモリの消費量を下げる一方で再計算の時間効率の減少を少なくすることができる。
【００６６】
さらに、計算時間の増加を抑えつつメモリの消費量の増加をも抑えることにより、例えば、ミニバッチ処理を行う場合には、ミニバッチのサイズを増加させることも可能となる。ミニバッチサイズを増加させることにより、バッチ正規化の精度を向上させ、訓練精度を向上させることも可能である。このように、メモリ、再計算時間の効率向上のみならず、訓練の精度についても向上することが可能である。
【００６７】
前述の実施形態においては、Lを下方集合として含むL'について演算ループを実行したが、これには限られず、L'に着目し、下方集合Lごとに演算ループを構築させてもよい。この場合、初期値、演算順序等は、適宜適切に入れ替える。
【００６８】
境界は、δ＋(V−L)としてもよい。この場合、逆伝播の最初についての境界は、考慮に入れないように最適化を行ってもよい。さらに、前述した順伝播及び逆伝播の処理についても適切に境界が残り、メモリの消費量がオーバーフローしないように調整することが可能である。
【００６９】
なお、本実施形態においては、動的計画法を用いたが、グラフに含まれる計算対象となるノード数によっては、下方集合の個数は、高々2|V|であるので、ブルートフォースアタックにより最適解を求めてもよい。この場合、BFS（Breadth-First Search）又はDFS（Depth-First Search）に基づいて、検索を行ってもよい。
【００７０】
前述のフローチャートで示したアルゴリズムは、ヒューリスティック的にさらに高速化することもできる。このように高速化した態様を適用した最適化装置についても本実施形態の内容に含まれるものである。以下、いくつかの他の最適化例を挙げる。
【００７１】
（第１例）
上述の手法では、全ての下方集合から動的計画法により厳密に行ったが、ヒューリスティックにより枝刈りをしてもよい。すなわち、上述の厳密な手法では、L=LGとして最適化を行っていたが、下方集合をLGpruned=φ∪{Lv|v∈V}、Lv={w∈V|vはwから到達可能}というような集合として最適化を行ってもよい。vがwから到達可能とは、vからwに向かう有向枝のパスで0以上のものが存在することをいう。このように、上述した動的計画法において、L=LGprunedとして最適化を行うことにより、下方集合の枝刈りを行うことが可能であり、厳密な最適解ではないが、ほぼ遜色ない解をより高速に求めることが可能となる。
【００７２】
厳密な手法においては、ループの回数がO(T(V)×|LG|2)〜O(|V|×|LG|2)であるが、枝刈りの手法によれば、O(|V|3)とすることが可能となる。
【００７３】
（第２例）
上述の実施形態では、例えば、逆伝播においても順伝播と同様に、Viの各ノードの勾配を取得し、当該勾配を用いてパラメータ更新等の演算が終わった後に、δ+(Li−1)∩Viのノードを除いて勾配情報を消去する場合について説明した。同様に、過程として、Vi内の各ノードにおいて勾配の演算が終了するまで、順伝播により再計算された値の全てを記憶するようなメモリ消費を用いて最適化を行っていた。しかしながら、逆伝播において、勾配を順次計算しながら、不必要となった順伝播ノードのデータを記憶しているメモリを解放していくことも可能である。
【００７４】
例えば、再計算のストラテジは、上述の実施形態においては、
compute v：ノードvを計算し、結果をメモリに格納する and
release v：ノードvをメモリから解放する
といったもので表すことが可能である。release vをできる限り早いタイミングで行うことにより、演算処理のピーク時におけるメモリ消費を減少させることが可能となる。
【００７５】
そこで、再計算のストラテジにおいて、コマンド列に対して単純に上記のような変更を加え、さらにピークメモリ消費を削減したヒューリスティックを次のように与える。コマンド列に「release v」がある場合には、それをコマンド列上で矛盾が生じない、すなわち、開放したメモリにアクセスすることがない状態においてできる限り前のステップへと移動させ、早いタイミングでメモリの解放が発生するようにする。
【００７６】
このようにシンプルな変更を加えることにより、ピーク時のメモリ消費をより多く削減することが可能となる。この手法を演算順序最適化と記載する。
【００７７】
メモリ消費算出部１６は、上述の方法で、着目演算ノードにおける演算結果を記憶するためのメモリ消費に基づいて当該着目演算ノードのメモリ消費を算出することができる。さらに、メモリ消費算出部１６は、例えば、下記の方法により正確な計算が可能となる。
【００７８】
ノードuとノードvがあり、下記のコマンド列が存在する場合がある。
0 (初期状態)
1 compute u
2 compute v
3 release u
4 release v
【００７９】
0, 1, 2, 3, 4の各コマンドの実行が完了した状態におけるメモリ使用量の最大値が、計算したいメモリ消費の値になる。compute uではメモリ使用量がMu増加し、release uではMu減少するものとする。これに基づいて各コマンド実行後の状態におけるメモリ使用量をMc0(＝0), Mc1, ...と書くと、
Mc0＝0
Mc1＝Mc0＋Mu＝0＋Mu＝Mu (compute uにより、Mu分増加する)
Mc2＝Mc1＋Mv＝Mu＋Mv (compute vにより、Mv分増加)
Mc3＝Mc2−Mu＝(Mu＋Mv)−Mu＝Mv (release u により、 Mu分減少)
Mc4＝Mc3−Mv＝Mv−Mv＝0 (release v により、Mv分減少)
とできる。このようにコマンド列から各状態のメモリ使用量を計算し、Mc0, Mc1, ...の最大値を取ることで計算できる。上の例ではMc2＝Mu＋Mvが最大値となる。上のコマンド列は一例であり、実際の計算には演算順序最適化を行ったコマンド列に対して上の計算を行うものとする。
【００８０】
（第３例）
上記に示した再計算問題は、追加計算時間が最小化されるような戦略を求めた。これをTC（Time-Centric）と記載する。このTCにおいて、戦略のピークメモリ消費を演算順序最適化により最適化を行うのが、第２例に示したものである。
【００８１】
追加計算時間を最小化する代わりに、最大化して得られる戦略を演算順序最適化に適用すると、より多くのメモリが減らせることがある。追加計算時間の多くなるような頂点分割の方が粒度の大きいセグメントが表れやすくなり、それによって演算順序最適化によるメモリ削減の効果が大きくなるためであると考えられる。このように追加計算時間を最大化して得られる戦略をMC（Memory-Centric）と記載する。追加時間を最大化しても、各ノードで行う順伝播計算は、例えば、高々１回でよい。そこで、このMCをヒューリスティックとすることもできる。これは、t0を求める際に上述したように、最小のtを抽出するのではなく、最大のtを抽出するといった簡単な変更で実行することが可能である。
【００８２】
このような種々のヒューリスティックを用いることにより、演算の高速化、又は、メモリ消費の最小若しくは再計算時間の最小といった目的に応じた最適化を行うことが可能である。
【００８３】
（第４例）
動的計画法においても、高速化を行うことが可能である。例えば、動的計画法においてテーブルとして定義されるopt[・]を、スパーステーブルとして計算することにより、計算時間を大幅に短縮することが可能である。さらに、t＜t'に対してopt[L, t]＜opt[L, t']である場合には、opt[L, t']の計算を省略することも可能である。このように、前述の実施形態における動的計画法の計算時間を削減することも可能である。
【００８４】
また、例えば、計算過程に不要なノードが含まれている場合、そのようなノードを除去して計算することにより、より正確にメモリ消費または時間消費の計算を行うことができる。例えば、加算は、逆方向の計算時に順方向の入力を必要としないため、加算にのみ必要なデータを有するノードは記憶する必要がなく、不要なノードといえる。そのような不要なノードの少なくとも一部、好ましくはすべて除外して、着目演算ノードにおける演算結果を記憶するためのメモリ消費に基づいて、着目演算ノードの前記メモリ消費を算出することで、より正確な計算を行うことができる。
【００８５】
前述した実施形態における最適化装置１において、各機能は、アナログ回路、デジタル回路又はアナログ・デジタル混合回路で構成された回路であってもよい。また、各機能の制御を行う制御回路を備えていてもよい。各回路の実装は、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）等によるものであってもよい。
【００８６】
上記の全ての記載において、最適化装置の少なくとも一部はハードウェアで構成されていてもよいし、ソフトウェアで構成され、ソフトウェアの情報処理によりＣＰＵ（Central Processing Unit）等が実施をしてもよい。ソフトウェアで構成される場合には、最適化装置１及びその少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記憶媒体に収納し、コンピュータに読み込ませて実行させるものであってもよい。記憶媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記憶媒体であってもよい。すなわち、ソフトウェアによる情報処理がハードウェア資源を用いて具体的に実装されるものであってもよい。さらに、ソフトウェアによる処理は、ＦＰＧＡ等の回路に実装され、ハードウェアが実行するものであってもよい。ジョブの実行は、例えば、ＧＰＵ（Graphics Processing Unit）等のアクセラレータを使用して行ってもよい。
【００８７】
例えば、コンピュータが読み取り可能な記憶媒体に記憶された専用のソフトウェアをコンピュータが読み出すことにより、コンピュータを上記の実施形態の装置とすることができる。記憶媒体の種類は特に限定されるものではない。また、通信ネットワークを介してダウンロードされた専用のソフトウェアをコンピュータがインストールすることにより、コンピュータを上記の実施形態の装置とすることができる。こうして、ソフトウェアによる情報処理が、ハードウェア資源を用いて、具体的に実装される。
【００８８】
図７は、本発明の一実施形態におけるハードウェア構成の一例を示すブロック図である。最適化装置１は、プロセッサ７１と、主記憶装置７２と、補助記憶装置７３と、ネットワークインタフェース７４と、デバイスインタフェース７５と、を備え、これらがバス７６を介して接続されたコンピュータ装置７として実現できる。
【００８９】
なお、図９のコンピュータ装置７は、各構成要素を一つ備えているが、同じ構成要素を複数備えていてもよい。また、１台のコンピュータ装置７が示されているが、ソフトウェアが複数のコンピュータ装置にインストールされて、当該複数のコンピュータ装置それぞれがソフトウェアの異なる一部の処理を実行してもよい。
【００９０】
プロセッサ７１は、コンピュータの制御装置および演算装置を含む電子回路（処理回路、Processing circuit、Processing circuitry）である。プロセッサ７１は、コンピュータ装置７の内部構成の各装置などから入力されたデータやプログラムに基づいて演算処理を行い、演算結果や制御信号を各装置などに出力する。具体的には、プロセッサ７１は、コンピュータ装置７のＯＳ（Operating System）や、アプリケーションなどを実行することにより、コンピュータ装置７を構成する各構成要素を制御する。プロセッサ７１は、上記の処理を行うことができれば特に限られるものではない。最適化装置１及びそれらの各構成要素は、プロセッサ７１により実現される。ここで、処理回路とは、１チップ上に配置された１又は複数の電気回路を指してもよいし、２つ以上のチップあるいはデバイス上に配置された１又は複数の電気回路を指してもよい。
【００９１】
主記憶装置７２は、プロセッサ７１が実行する命令および各種データなどを記憶する記憶装置であり、主記憶装置７２に記憶された情報がプロセッサ７１により直接読み出される。補助記憶装置７３は、主記憶装置７２以外の記憶装置である。なお、これらの記憶装置は、電子情報を格納可能な任意の電子部品を意味するものとし、メモリでもストレージでもよい。また、メモリには、揮発性メモリと、不揮発性メモリがあるが、いずれでもよい。最適化装置１内において各種データを保存するためのメモリ、例えば、記憶部１２は、主記憶装置７２または補助記憶装置７３により実現されてもよい。例えば、前述した各記憶部の少なくとも一部は、この主記憶装置７２又は補助記憶装置７３に実装されていてもよい。別の例として、アクセラレータが備えられている場合には、前述した各記憶部の少なくとも一部は、当該アクセラレータに備えられているメモリ内に実装されていてもよい。
【００９２】
ネットワークインタフェース７４は、無線または有線により、通信ネットワーク８に接続するためのインタフェースである。ネットワークインタフェース７４は、既存の通信規格に適合したものを用いればよい。ネットワークインタフェース７４により、通信ネットワーク８を介して通信接続された外部装置９Ａと情報のやり取りが行われてもよい。
【００９３】
外部装置９Ａは、例えば、カメラ、モーションキャプチャ、出力先デバイス、外部のセンサ、入力元デバイスなどが含まれる。また、外部装置９Ａは、最適化装置１の構成要素の一部の機能を有する装置でもよい。そして、コンピュータ装置７は、最適化装置１の処理結果の一部を、クラウドサービスのように通信ネットワーク８を介して受け取ってもよい。
【００９４】
デバイスインタフェース７５は、外部装置９Ｂと直接接続するＵＳＢ（Universal Serial Bus）などのインタフェースである。外部装置９Ｂは、外部記憶媒体でもよいし、ストレージ装置でもよい。各記憶部は、外部装置９Ｂにより実現されてもよい。
【００９５】
外部装置９Ｂは出力装置でもよい。出力装置は、例えば、画像を表示するための表示装置でもよいし、音声などを出力する装置などでもよい。例えば、ＬＣＤ（Liquid Crystal Display）、ＣＲＴ（Cathode Ray Tube）、ＰＤＰ（Plasma Display Panel）、スピーカなどがあるが、これらに限られるものではない。
【００９６】
なお、外部装置９Ｂは入力装置でもよい。入力装置は、キーボード、マウス、タッチパネルなどのデバイスを備え、これらのデバイスにより入力された情報をコンピュータ装置７に与える。入力装置からの信号はプロセッサ７１に出力される。
【００９７】
本発明の態様は、上記した個々の実施形態に限定されるものではない。特許請求の範囲に規定された内容及びその均等物から導き出される本発明の概念的な思想と趣旨を逸脱しない範囲において種々の追加、変更及び部分的削除が可能である。例えば、前述した全ての実施形態において、説明に用いた数値は、一例として示したものであり、これらに限られるものではない。
【００９８】
また、本明細書において、「最適化」とは、必ずしも再計算の効率を最適に調整することに限られない。つまり、一部でも再計算の効率化が行われれば良い。また、「最適化装置」とは、そのような処理が可能な装置を指すものとする。
【符号の説明】
【００９９】
１：最適化装置、１０：入力部、１２：記憶部、１４：初期化部、１６：メモリ消費算出部、１８：時間消費算出部、２０：更新部、２２：抽出部、２４：戦略取得部、２６：出力部
【図１】
2020135748.tif 000003
【図２】
2020135748.tif 000004
【図３】
2020135748.tif 000005
【図４】
2020135748.tif 000006
【図５】
2020135748.tif 000007
【図６】
2020135748.tif 000008
【図７】
2020135748.tif 000009