(57)【要約】  コスト関数が凸関数でない場合にも機械学習を行うことができる機械学習技術を提供する。機械学習システムは、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含み、機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われ、代理凸関数は、コスト関数の主変数に関する一次勾配の式、又は、コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている。
2019198815.tif 000002
【特許請求の範囲】
【請求項１】
情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、
上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習が行われ、
上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
機械学習システム。
【請求項２】
請求項１に記載の機械学習システムにおいて、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b(t)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b(t)に関する一次勾配を∇fi(wi,b(t))とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、ηを正の数とし、Tを正の整数として、
【数３０９】
2019198815.tif 000311
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行う処理と、
【数３１０】
2019198815.tif 000312
(b) ノード部iが、以下の式に基づいて、主変数の更新を行う処理と、
【数３１１】
2019198815.tif 000313
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)の処理に加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信する処理と、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とする処理と、
が行われる、
機械学習システム。
【請求項３】
複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、
上記複数のノード部は、上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習を行い、
上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
機械学習方法。
【請求項４】
請求項３に記載の機械学習方法において、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b(t)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b(t)に関する一次勾配を∇fi(wi,b(t))とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、ηを正の数とし、Tを正の整数として、
【数３１２】
2019198815.tif 000314
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行うステップと、
【数３１３】
2019198815.tif 000315
(b) ノード部iが、以下の式に基づいて、主変数の更新を行うステップと、
【数３１４】
2019198815.tif 000316
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)のステップに加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信するステップと、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とするステップと、
が行われる、
機械学習方法。
【請求項５】
請求項１または２に記載の機械学習システムの各部として、コンピュータを機能させるためのプログラム。
【請求項６】
共通するある１つの主変数についての学習結果を得るための機械学習をする複数のノード部を含む機械学習システムにおいて、
上記複数のノード部のそれぞれは、
該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習部と、
上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信部と、
を含み、
上記学習部は、
上記送受信部が上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
機械学習システム。
【請求項７】
請求項６に記載の機械学習システムにおいて、
上記学習部における上記双対変数の更新処理は、
上記主変数の最適化の更新式が、上記主変数の更新前の項を含まず上記双対変数を含む式で表されることにより、行われる、
機械学習システム。
【請求項８】
請求項６に記載の機械学習システムにおいて、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wi,bのb個目の要素をwiとし、wi,bの最適解のb個目の要素をwi,b*とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、Tを正の整数として、
【数３１５】
2019198815.tif 000317
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行う処理と、
【数３１６】
2019198815.tif 000318
(b) ノード部iが、以下の式に基づいて、双対補助変数の更新を行う処理と、
【数３１７】
2019198815.tif 000319
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)の処理に加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信する処理と、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とする処理と、
が行われる、
機械学習システム。
【請求項９】
複数のノード部が、共通するある１つの主変数についての学習結果を得るための機械学習をする機械学習方法において、
上記機械学習方法は、
上記複数のノード部のそれぞれの学習部が、該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習ステップと、
該ノード部の送受信部が、上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信ステップと、
を含み、
上記学習ステップは、
上記送受信ステップが上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
機械学習方法。
【請求項１０】
請求項９に記載の機械学習方法において、
上記学習ステップにおける上記双対変数の更新処理は、
上記主変数の最適化の更新式が、上記主変数の更新前の項を含まず上記双対変数を含む式で表されることにより、行われる、
機械学習方法。
【請求項１１】
請求項９に記載の機械学習方法において、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wi,bのb個目の要素をwiとし、wi,bの最適解のb個目の要素をwi,b*とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、Tを正の整数として、
【数３１８】
2019198815.tif 000320
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行うステップと、
【数３１９】
2019198815.tif 000321
(b) ノード部iが、以下の式に基づいて、双対補助変数の更新を行うステップと、
【数３２０】
2019198815.tif 000322
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)のステップ加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信するステップ、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とするステップと、
が行われる、
機械学習方法。
【請求項１２】
請求項６ないし８のいずれか１項に記載の機械学習システムの各部として、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械学習の技術に関する。
【背景技術】
【０００２】
近年、機械学習がブームになっており、収集したデータと出力したい情報の間の写像(mapping)を、データと教師データを用いた学習により得るフレームワークが一般的になってきている。なお、教師データに代えて、コスト関数が用いられる場合もある。【０００３】
現在行われている研究のほとんどで、データを中央集約化し、教師データ又は設計したコスト関数を用いて写像を学習するフレームワークが取られている。しかし、音声及び映像といった情報を中央集約化するのは、データ容量がかなり膨大になってきている今日では現実的ではなくなりつつある。円滑なサービスを提供する上で(例えば、ユーザとサーバ間のネットワーク距離が近ければレスポンスタイムが早くなる)、分散したノード群(例えば、サーバ、PC)に分散してデータを収集し、そのノード群が連結し、容量の大きなデータそのものではなく、その潜在変数のみをやりとりするだけで、写像が最適化され、すべてのノード間で共有されるようなフレームワークこそが、今日の機械学習の分野で熱望されている技術の一つである。こういった技術は、エッジコンピューティングにおける合意形成アルゴリズム(コンセンサスアルゴリズム)と呼ばれる。【０００４】
図１に、この合意形成アルゴリズムの適用先となるネットワークシステムを例示する。図１のネットワークシステムには、様々な環境(例えば、家、工場、野外及びビル)に多数のセンサーＡ−１０１など(例えば、マイク、カメラ、温度計)が分散して配置されており、それらのセンサーＡ−１０１を通じて得られたデータが、分散して配置された複数のノード部Ａ−１０２(例えば、サーバ、PC)のそれぞれに蓄積される。中央集約型のフレームワークでは中央サーバが必要であり、全てのデータが中央サーバに蓄積される必要があるが、合意形成アルゴリズムを用いる場合には、中央サーバは存在しなくてもよく、データは分散して配置された複数のノード部Ａ−１０２のそれぞれに蓄積されればよい。なお、データは、センサーＡ−１０１から得られるものに限らず、入力装置やWeb等から得られる文字データ等でも構わない。図１のネットワークシステムのノード部Ａ−１０２間は、エッジＡ−１０３によって疎に結合しており、全結合でなくてもよく、ノード部Ａ−１０２間で直接または間接的に何らかのデータを交換できる関係にあればよい。エッジＡ−１０３の連結構造についての制約はなく、木構造、循環/円構造でもなんでもよい。しかし、全てのノード部Ａ−１０２が直接または間接的につながっていればよい。すなわち、エッジＡ−１０３の連結構造は、分割された構造でなければよい。【０００５】
エッジコンピューティングにおける合意形成アルゴリズムを用いれば、図１のネットワークシステムのような条件の下で、データそのものではなく、写像を学習する過程で生成される変数をノード間で交換しながら、写像を最適化し、共有することができ、レスポンスタイムを早めたりデータ量を削減したりすることが可能である。【０００６】
従来技術として、凸最適化技術に基づく合意形成型のエッジコンピューティングについて述べる。コスト関数が凸関数であることに限定されるが、合意形成型のエッジコンピューティング技術は既に存在する。１つ目はDistributed ADMM法(Alternating Direction Method of Multipliers)に基づく方法（例えば、非特許文献１参照。）、２つ目はPDMM法(Primal Dual Method of Multipliers)に基づく方法（例えば、非特許文献２参照）である。なお、DNNは、非凸のコスト関数であるのでこの枠組みには入らない。
《Distributed ADMM法の合意形成アルゴリズム》
以下、Distributed ADMM法の合意形成アルゴリズムについて説明する。【０００７】
コスト関数は、閉真凸関数(Closed Proper Convex function)に限定する。Distributed ADMMベースの合意形成アルゴリズムでは、主変数と双対変数を更新しながら全体最適化を図る。その過程において、主変数をノード間で共有し、それらが一致するように合意形成するようにして、コスト関数が生成される。【０００８】
図２は、３種類のノードが全連結されている状況を示している。図２の例では、変数は、３種類の主変数w1,w2,w3、６種類の双対変数λ1|2,λ2|1,λ1|3,λ3|1,λ2|3,λ3|2、６種類のノード間で交換される主変数w1<1>,w1<2>,w2<1>,w2<2>,w3<1>,w3<2>で構成される。【０００９】
ノードを表すインデックス集合~Vとノード数Vを以下のように書く。【００１０】
【数１】
2019198815.tif 000003
【００１１】
i番目のノードにつながっているノードのインデックス集合(エッジの情報)~N(i)とその数N(i)を以下のように書く。なお、~N(i)は、N(i)の上に「~」が付されていることを表す。後に出てくる~V,~Bについても同様である。【００１２】
【数２】
2019198815.tif 000004
【００１３】
i番目のノードにおけるj番目のノードに対する双対変数をλi|jとする。【００１４】
写像の一つの事例として、教師データとの最小二乗問題を扱う。【００１５】
以下のように記号を定義する。sを教師データ、xを入力データ（「観測データ」と言う場合もある）、wを重みベクトル、Bを教師データ(「出力データ」と言う場合もある)の次元(b=1,…,B)、λを双対変数とする。なお、双対変数λの次元は、重みベクトルwの次元と同じであるとする。添え字が付いたこれらのアルファベットの意味は、添え字が付いてないアルファベットと同じであるとする。例えば、siは、sと同じく教師データを意味する。また、~B={1,…,B}であるとする。Bは所定の正の整数である。識別問題を扱う場合には、Bを２以上の整数とする。例えば、10種類の数字を認識するタスクであれば、B=10である。また、回帰問題を扱う場合には、例えばB=1とする。【００１６】
このとき、i=1,…,Vとして、教師データsiは以下のような構成になる。【００１７】
【数３】
2019198815.tif 000005
【００１８】
同様にして、xi=[xi,1,…,xi,B]Tであり、wi=[wi,1,…,wi,B]Tであり、λi|j=[λi|j,1,…, λi|j,B]Tであるとする。【００１９】
i番目ノードにあるデータxiに重み付け加算することでsiを得るような算術を写像として用いるとき、写像を最適化するためのコストは以下の真凸閉関数fiで書ける。i番目のノードにおけるコスト関数をfiとし、これを最小化するようなwを探索する。【００２０】
【数４】
2019198815.tif 000006
【００２１】
ここで、写像関数は線形の重みづけ加算^si,b=xiTwi,bであるとする。si,bの左上の^は、学習後又は学習途中に得られたwi,bにより得られることを表す。また、・を任意の数として、||・||pはL-pノルムを意味する。【００２２】
wを以後、主変数と呼ぶ。V個のノードが連結していて、変数が同一となるような制約下でコストを最小化する問題は以下で書ける。【００２３】
【数５】
2019198815.tif 000007
【００２４】
ここで、wj,b<i>は、i番目のノードに蓄積されたj番目のノードの主変数を意味する。後述するように、wj,b<i> は適宜更新される。【００２５】
この式は、双対変数λを最大化する条件下(ノード間の主変数が連結しているノード間で一致する条件を満たせば、λに掛かっている項が０になるという意図)で、コスト関数を最小化するように主変数wを最適化するということを表している。【００２６】
なお、主変数wが連結しているノード間で一致するという条件は、例えば行列Aを、互いを加算して０になる関係で記述することができる。例えば、行列Aは、以下のようにI,-I,0で記述することができる。Iは単位行列であり、0は零行列である。【００２７】
【数６】
2019198815.tif 000008
【００２８】
非特許文献３のp.154-155にあるミニマックス定理より、コスト関数”f”が真凸関数であれば、「双対変数を最大化しながら主変数を最小化する」という元々の問題の最適解は、「主変数を最小化しながら、双対変数を最大化する」問題を解いた場合の最適解と一致する。【００２９】
【数７】
2019198815.tif 000009
【００３０】
この問題を解くための方式として拡張ラグランジュ法がある（例えば、非特許文献２参照。）。これは、最適化処理を安定化させるために、罰則項を加算する方法である。ρiは、所定の正の数である。【００３１】
【数８】
2019198815.tif 000010
【００３２】
内側のwに関する最小化する問題を最初に解く。すなわち、wに関して微分が０になるポイントを探る。w*は、wに関して最適化されたポイントを指す。また、tは更新回数のインデックスを表す。【００３３】
【数９】
2019198815.tif 000011
【００３４】
このため、t+1回目の主変数の更新は以下のように行われる。【００３５】
【数１０】
2019198815.tif 000012
【００３６】
双対変数に関するt+1回目の更新は以下のように行われる。【００３７】
【数１１】
2019198815.tif 000013
【００３８】
従来法のDistributed ADMM法の合意形成アルゴリズムをまとめると以下になる。【００３９】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(3)の処理を行う。ここで、Tは、繰り返し回数であり、所定の正の整数である。この明細書では、Tは、繰り返し回数又は行列及びベクトルの転置を表すが、当業者であれば文脈に応じてどちらを意味するのか明確であるため、以降の説明ではどちらを意味するのかを明示せずにTを用いることにする。
(1)主変数更新【００４０】
【数１２】
2019198815.tif 000014
【００４１】
(2)双対変数更新【００４２】
【数１３】
2019198815.tif 000015
【００４３】
(3)毎回である必要はないし、エッジごとに独立(非同期)でよいが、主変数をノード間で更新する。【００４４】
【数１４】
2019198815.tif 000016
【００４５】
Distributed ADMM法の合意形成アルゴリズムの長所は、理論的な背景はないが、いくつかの実験を通じて、各ノードに蓄積されるデータセット間に統計的性質差がある場合にも収束することが確認されているということである。ただし、その収束率は低い。【００４６】
一方、Distributed ADMM法の合意形成アルゴリズムの短所は、以下の(1)から(4)である。(1)収束率が低い。(2)原理的に、非凸関数の最適化(DNN等を含む)に適用できない。(3)主変数を交換するという観点で、情報の秘密性がやや低い。すなわち、主変数にはデータの性質が色濃く反映されることがあるので、主変数をハッキングすることで、データの統計的性質を得られる可能性がある。(4)伝送レートがやや高い。すなわち、主変数のデータに統計的な偏りが見られない場合、伝送レートは高くなりがちであることである。
《PDMMベースの合意形成アルゴリズム》
次に、PDMMベースの合意形成アルゴリズムについて説明する。Distributed ADMMと大きく異なる点は、主変数だけでなく、双対変数も共有することである。後述するが、双対変数のペアについて合意形成される。【００４７】
λi|j=λj|iという条件下で最適化問題を解くことは、主変数も暗に合意することに相当する。すなわち、主変数及び双対変数のそれぞれで合意形成される。また、その制約を課すことで、収束速度が高くなることが理論的に明らかになっている。【００４８】
図３の例では、６種類の双対変数λ1|2,λ2|1,λ1|3,λ3|1,λ2|3,λ3|2が３種類のペアλ1|2=λ2|1,λ1|3=λ3|1,λ2|3=λ3|2を形成している。双対変数と主変数を連結しているノード間で情報交換しながら、合意形成することを目指す。なお、双対変数は、各更新時における主変数間の差分に物理的には相当する。【００４９】
Distributed ADMMと同様にコスト関数は閉真凸関数に限る。一つの事例として、最小二乗問題を解く場合、以下がコストとなる。【００５０】
【数１５】
2019198815.tif 000017
【００５１】
Distributed ADMMと同様に双対問題を定義すると以下のようになる。【００５２】
【数１６】
2019198815.tif 000018
【００５３】
以下に変数の定義を書く。以下では、V個のノードを連結して変数を表現している。【００５４】
【数１７】
2019198815.tif 000019
【００５５】
図３のようなエッジ構成を想定して、言い換えればλi|j=λj|iという制約の下で式を書き下すと以下のようになる。【００５６】
【数１８】
2019198815.tif 000020
【００５７】
主変数及び双対変数のそれぞれで合意形成するという条件は以下で書ける。【００５８】
【数１９】
2019198815.tif 000021
【００５９】
wを最適化するうえでの一つのテクニックとして、fのルジャンドル変換である凸共役関数f*を導入する。これは、fが閉真凸関数であるとき、f*もまた閉真凸関数になることが知られているので、このような記述をする（例えば、非特許文献３参照。）。【００６０】
【数２０】
2019198815.tif 000022
【００６１】
なお、上記の第一式の右辺は、下記の式の下線部分を取り出したものである。【００６２】
【数２１】
2019198815.tif 000023
【００６３】
元々の問題は、以下のようにかける。以下の式変形では、f*が閉真凸関数であるので、その最小化問題として書けることを利用している。【００６４】
【数２２】
2019198815.tif 000024
【００６５】
双対変数の合意条件下での最適化問題であることを追加すると、解くべき問題は以下で再定義される。【００６６】
【数２３】
2019198815.tif 000025
【００６７】
この問題は、以下を解くことに相当する。【００６８】
【数２４】
2019198815.tif 000026
【００６９】
関数δは指示関数と呼ばれる。指示関数も凸関数の一種である。行列Pは、以下に示すように、i,j番目のノード間にある双対変数のペアを交換するという演算(permutationのP)であり、双対変数が一致した時に指示関数が0を出力する(コストを下げる)ということを意味している。【００７０】
【数２５】
2019198815.tif 000027
【００７１】
解くべき問題は、２種類の凸関数で構成されている。こういった問題を解くためのテクニックとして、オペレータ分割法がある（例えば、非特許文献４参照。）。これは、全体最適化を一度に行うことが難しい問題であっても、交互に最適化しながら解くテクニックである。【００７２】
オペレータ分割法には、様々な方法が存在するが、代表的なものとして、Peaceman-Rachford splitting (P-R分割) がある。【００７３】
P-R分割を使ったPDMMベースの合意形成アルゴリズムは、以下のようになる。【００７４】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(3)の処理を行う。
(1)主変数更新【００７５】
【数２６】
2019198815.tif 000028
【００７６】
(2)双対変数更新【００７７】
【数２７】
2019198815.tif 000029
【００７８】
(3) 主変数をノード間で更新する。なお、更新過程は非連続であってもよく(毎回更新する必要はない)、かつ、エッジごとに独立(非同期)に実行してよい。【００７９】
【数２８】
2019198815.tif 000030
【００８０】
このPDMMベースの合意形成アルゴリズムの長所は、収束率が高いということである。【００８１】
一方、このPDMMベースの合意形成アルゴリズムの短所は、以下の(1)から(4)である。(1)いくつかのケースで、各ノードに蓄積されるデータセット間に統計的性質差がある場合に、収束しないという結果を得たということである。しかし、異質なデータセットに対しても収束するという理論的保証はない。(2) 原理的に、非凸関数の最適化(DNN等を含む)に適用できない。(3)主変数を交換するという観点で、情報の秘密性がやや低い。すなわち、主変数にはデータの性質が濃く反映されることがあるので、主変数をハッキングすることで、データの統計的性質を得られる可能性がある。(4)伝送レートが高い。すなわち、主変数と双対変数を送るので、伝送レートは高くなりがちである。【００８２】
次に、機械学習の対象となるモデルの潜在変数を学習する際に扱うコストの最小化問題を考える。この最小化問題は、以下のように定式化される。
（問題）
コスト関数Gは、関数G1と関数G2に加法分割されるものとする。ただし、関数G1, G2はいずれも閉真凸関数であるものとする（以後、閉真凸関数のことを単に凸関数という）。【００８３】
【数２９】
2019198815.tif 000031
【００８４】
ここで、w∈Rm（mは1以上の整数）、Gi:Rm→R∪{∞} (i=1, 2)である。つまり、wは、m次元実ベクトル空間Rmの要素であり、Giは、m次元実ベクトルwを入力とし、（1次元の）実数を出力する関数である。【００８５】
なお、Giの入力は、ベクトルであるとしたが、行列やテンソルであってもよい。行列やテンソルはベクトルを用いて表現することができるので、以下、Giの入力はベクトルであるものとして話を進める。【００８６】
コストGを最小化するように潜在変数wを最適化する問題は、以下のように表される。【００８７】
【数３０】
2019198815.tif 000032
【００８８】
この問題の最適解w*（wの停留点ともいう）は、コストGの劣微分が0ベクトル（零ベクトル）を含むときに得られる。【００８９】
【数３１】
2019198815.tif 000033
【００９０】
ここで、∂Giは、Giの劣微分を表す。なお、入力と出力が１対１対応となる等号を表す記号”=“の代わりに、記号“∈”を用いるのは、凸関数Giが不連続点を含む場合、その劣微分は不連続点において多点出力対応となるためである。【００９１】
最適解w*を求める従来方法を説明する前に、式(1-1)に従う具体的問題をいくつか挙げる。
《具体的問題１：エッジコンピューティングにおける合意形成問題》
V個のノードが任意に接続されたグラフG(v, e)（ただし、vはノードの集合、eはエッジの集合である）を考える。【００９２】
【数３２】
2019198815.tif 000034
【００９３】
ここで、N(i)はi番目のノードに接続されたノード群のインデックスの集合を表す。【００９４】
図９は、V個のノード（サーバ）がエッジ構造eに従って繋がっている状態（V=5の場合）を示す。各ノードに蓄積された膨大なデータをノード間で交換するのではなく、潜在変数やその補助変数（例えば、双対変数）を交換しながら全体最適化する問題がエッジコンピューティングにおける合意形成問題である。【００９５】
i番目のノードにある凸関数で表現されたコストを以下のように表す。【００９６】
【数３３】
2019198815.tif 000035
【００９７】
ここでは、問題の理解を容易にするために、コストF1,iの具体例として、教師データsiに対する二乗誤差を用いることにする。【００９８】
【数３４】
2019198815.tif 000036
【００９９】
ここで、Tは転置、||・||pはLpノルムを表す。また、u(i)={1,…,U(i)}である。【０１００】
このコストF1,iは、p’次元ベクトルvi∈Rp’を入力データとし、教師データsiを出力するように、U(i)個のデータの組(vi,u, si,u)を用いて、潜在変数pi(pi∈Rp’)を最適化する問題のコスト関数である。ノードによってデータやその数U(i)が異なることをインデックスが示している。一般に、各ノードに蓄積されたデータは異なるが、同一であってもよい。なお、入力データと教師データの組のことを学習データという。また、以下、m=p’Vとする。【０１０１】
この例では、教師データを用いる形で定式化したが、教師データを用いることなく定式化することもできる。【０１０２】
また、同一のロケーションにある複数のサーバによる並列コンピューティングについても、上記合意形成問題と同一の問題として定式化できる。例えば、多数のコンピュータを使って並列計算をして、音声認識、画像認識などのモデルを高速に学習するような場合が該当する。この場合、各サーバに蓄積されるデータセットは基本的には同一になる。【０１０３】
合意形成問題では、ノード間で潜在変数pの値が同一になるように制約しながら、コストを最小化する停留点を探すことになる。【０１０４】
【数３５】
2019198815.tif 000037
【０１０５】
ここで、pi∈Rp’、Ai|j∈Rp’×p’である。Ai|jは合意形成を表現するp’×p’の実数行列である。この行列Ai|jとして任意の行列を用いることができるが、”ノード間で潜在変数の値が同一になるように学習を進めたい”という意図がある場合、例えば、以下のような簡単な行列を用いることができる。【０１０６】
【数３６】
2019198815.tif 000038
【０１０７】
ここで、Iは単位行列である。【０１０８】
式(2-1)のような線形拘束下でのコスト最小化問題を解く場合、ラグランジュの未定乗数法を用いることが多い。双対変数νi,j∈Rp’を用いて、ラグランジュ関数Lを以下のように定義する。【０１０９】
【数３７】
2019198815.tif 000039
【０１１０】
式(2-1)を解くことは、以下の式(2-2)の問題（主問題）を解くことに対応する。しかし、この問題を直接解くことは困難な場合が多い。【０１１１】
F1,iが閉真凸関数であるとき、強双対性が成立する、つまり、最適点において式(2-2)と式(2-3)間の統合性が成り立つので、式(2-2)を解く代わりに、式(2-3)の問題（双対問題）を解くことが一般的である。【０１１２】
【数３８】
2019198815.tif 000040
【０１１３】
ここで、F1,i*は、凸関数F1,iの凸共役関数を表す。【０１１４】
【数３９】
2019198815.tif 000041
【０１１５】
F1,iが凸関数である場合、F1,i*も凸関数になる。【０１１６】
式(2-4)は、凸関数F1,i*を最小化する双対変数νi,jを探す問題を表している。式(2-1)を解くためには、式(2-4)を解けばよいが、式(2-4)の形式のままでは、ノードごとに非同期で潜在変数を更新するような処理を実現することができない。そこで、双対変数νi,jをノードごとに帰属するようにリフティング処理を行う。具体的には、双対変数νi,jをi番目のノードに帰属する双対変数λi|j∈Rp’とj番目のノードに帰属する双対変数λj|i∈Rp’の2つに分け、これらの変数が一致するという制約を入れる。【０１１７】
【数４０】
2019198815.tif 000042
【０１１８】
図１０Ａ及び図１０Ｂは、双対変数のリフティング処理の様子を示す図である。図１０Ａは、ノードiとノードjの合意形成における誤差を制御しているのが変数νi,jであることを表している。しかし、このままではi番目の潜在変数とj番目の潜在変数を同期しながら更新しなければならない。そこで、i番目の潜在変数とj番目の潜在変数を非同期でも更新できるようにするために、図１０Ａでは無方向であったエッジを、図１０Ｂのように方向性のある2つのエッジに書き換える。この2つのエッジは1つの無方向のエッジから生成されたものであるので、一致するという制約が必要になるが、変数更新における同期性の問題を解決することができる。【０１１９】
双対変数のリフティング処理により、式(2-4)の問題は、以下の問題（線形拘束付の最適化問題）に書き換えられる。【０１２０】
【数４１】
2019198815.tif 000043
【０１２１】
V個に分けて書いていた変数群をベクトルや行列を用いて表現することにより、式(2-5)は以下のように表現する。もちろん、式の意味は変わることなく、同一の問題を表している。【０１２２】
【数４２】
2019198815.tif 000044
【０１２３】
ここで、凸共役関数F1*は、次式のようになる。【０１２４】
【数４３】
2019198815.tif 000045
【０１２５】
なお、F1:Rm→R∪{∞}, F1*:Rm→R∪{∞}(m=p’V)である。【０１２６】
また、V個のノードごとに分けて書いていた変数群（つまり、pi, λi|j, Ai|j）は以下のようになる。【０１２７】
【数４４】
2019198815.tif 000046
【０１２８】
ここで、さらに、リフティング処理された双対変数が一致するという制約を記述するにあたって、変数が一致するという観点で適切な性質をもつ指示関数F2を用いることにする。指示関数F2を用いると、式(2-6)の問題は、以下の問題に帰着する。【０１２９】
【数４５】
2019198815.tif 000047
【０１３０】
ここで、指示関数F2は、以下のように定義される。【０１３１】
【数４６】
2019198815.tif 000048
【０１３２】
ここで、Pは順序入替行列（パーミュテーション行列）である。順序入替行列Pの要素はすべて0または1であり、P2=Iという性質を持つ。行列Pをベクトルλにかけることは、以下のようにノードiとノードjの間のエッジに対応する双対変数λi|j, λj|iを入れ替える処理（λj|i⇔λi|j）に相当する。【０１３３】
【数４７】
2019198815.tif 000049
【０１３４】
ここで、式(2-7)に対して以下のようなに置き換えを適用することにより、エッジコンピューティングにおける合意形成問題（つまり、式(2-7)）が式(1-1)に帰着することがわかる。【０１３５】
【数４８】
2019198815.tif 000050
【０１３６】
また、別の例として以下のようなものがある。
《具体的問題２：画像／音声／言語の認識タスクにおける汎用モデル生成問題》
画像/音声/言語等の認識タスクにおける汎用モデルを生成するための方法として、以下のようなコストを用いて潜在変数pを学習させることが有用であることが知られている（参考非特許文献１）。
（参考非特許文献１：V. Vapnik, “Principles of Risk Minimization for Learning Theory”, Advances in Neural Information Processing Systems 4 (NIPS1991), pp.831-838, 1992.）【０１３７】
【数４９】
2019198815.tif 000051
【０１３８】
ここで、p∈Rmは潜在変数、λ∈Rmは双対変数、A=[a1, …, an]T∈Rn×mは入力データを表す。【０１３９】
式(2-8)に対して以下のようなに置き換えを適用することにより、画像／音声／言語の認識タスクにおける汎用モデル生成問題（つまり、式(2-8)）は式(1-1)に帰着することがわかる。【０１４０】
【数５０】
2019198815.tif 000052
【０１４１】
また、式(2-9)に対しても以下のようなに置き換えを適用することにより、式(1-1)に帰着することがわかる。【０１４２】
【数５１】
2019198815.tif 000053
【０１４３】
例えば、F1には二乗誤差やクロスエントロピーを用い、F2には正則化項としてL1ノルムを用いることができる。もちろん、F1、F2はこれに限るものではない。【０１４４】
【数５２】
2019198815.tif 000054
【０１４５】
ここで、sは、所望する出力情報の教師データである。なお、aiは、上述の入力データA=[a1, …, an]T∈Rn×mを構成するベクトルである。【０１４６】
なお、認識タスク以外のタスク、例えば、画像／音声の雑音除去にも用いることができる。
《最適解w*を求める従来方法》
ここでは、従来の解法について簡単に説明する。先述したように解くべき問題は式(1-1)である。また、式(1-1)で表される問題の最適解w*（wの停留点）は、式(1-2)が示すように、コストGの劣微分が0ベクトル（零ベクトル）を含むときに得られる。なお、Giが凸関数である場合、Giの劣微分∂Giは単調作用素となる。【０１４７】
式(1-2)を解いて最適解w*を求めるために、劣微分を連続線形写像に変換する。この変換方法のことを単調作用素分割法(Monotone operator splitting)という（非特許文献４）。単調作用素分割法には様々な方法が存在するが、ここでは、再帰的な変数更新に伴うコストの非拡大性（つまり、変数を更新するにつれて、コストが縮小していくという性質）を担保することができるPeaceman-Rachford(P-R)型とDouglus-Rachford(D-R)型の2種類の単調作用素分割法について説明する。【０１４８】
具体的な導出手続きについては省略するが、式(1-2)を変形していくと、P-R型単調作用素分割とD-R型単調作用素分割が得られる。なお、変形に際して、リゾルヴェント作用素Ωnとケーリー作用素Ψnを用いる(n=1, 2)。【０１４９】
【数５３】
2019198815.tif 000055
【０１５０】
ただし、Iは同一作用素、-1は逆作用素を表す。【０１５１】
また、w(w∈Rm)の補助変数z(z∈Rm)を導入する。その関係は以下のようにリゾルヴェント作用素で接続される。【０１５２】
【数５４】
2019198815.tif 000056
【０１５３】
P-R型単調作用素分割、D-R型単調作用素分割は、それぞれ式(3-1)、式(3-2)で表される。【０１５４】
【数５５】
2019198815.tif 000057
【０１５５】
式(3-1)と式(3-2)をみると、P-R型単調作用素分割に平均化作用素を導入することで、D-R型単調作用素分割が得られることがわかる。【０１５６】
以下、エッジコンピューティングにおける合意形成問題を例として、式(3-1)、式(3-2)から得られる再帰的な変数更新則である変数更新アルゴリズムについて説明する。この合意形成問題は、以下の式(2-7)のλをwで置き換えたもので表される。【０１５７】
【数５６】
2019198815.tif 000058
【０１５８】
このとき、リゾルヴェント作用素Ω2とケーリー作用素Ψ2は次のようになる。【０１５９】
【数５７】
2019198815.tif 000059
【０１６０】
ここで、上記指示関数F2を用いる場合、ケーリー作用素Ψ2は順序入替行列Pに対応することが非特許文献２に示されている。【０１６１】
式(3-1)、式(3-2)を再帰的な変数更新則として表現すると、以下のようになる。式(3-5)が式(3-1)のP-R型単調作用素分割に、式(3-6)が式(3-2)のD-R型単調作用素分割に対応する。【０１６２】
【数５８】
2019198815.tif 000060
【０１６３】
ここで、変数w, λ, z(w∈Rm, λ∈Rm, z∈Rm, m=p’V)はリゾルヴェント作用素やケーリー作用素を通して得られる変数であり、いずれも双対変数である。また、tは更新回数を表す変数である。【０１６４】
関数F1*の定義からわかるように、式(3-3)には潜在変数pと双対変数wの更新が含まれている。これらの変数を更新するための方法として、非特許文献２に記載の方法を説明する。式(3-3)を以下のように変形していく。【０１６５】
【数５９】
2019198815.tif 000061
【０１６６】
なお、上記変形で第2式から第3式を導出する際、積分形を用いた。【０１６７】
F1*は潜在変数pの最適化計算を含むため、式(3-7)を解く方法は、2種類ある。ここでは、まず潜在変数pを最適化し、pをその最適値に固定したうえで、双対変数wを最適化する方法を導出することにする。潜在変数pを逐次最適化計算する（つまり、ptからpt+1を計算する）ため、pに関する罰則項をF1*に含まれるコストに加えて計算する。【０１６８】
【数６０】
2019198815.tif 000062
【０１６９】
ここで、式(3-8)の右辺のargminの中の第3項が罰則項であり、γ>0である。罰則項を用いることで潜在変数pの逐次最適化計算が可能になる。【０１７０】
次に、潜在変数pを固定したうえで、式(3-7)に含まれる双対変数wの最適化を行う。【０１７１】
【数６１】
2019198815.tif 000063
【０１７２】
また、式(3-4)は以下のように計算できる。【０１７３】
【数６２】
2019198815.tif 000064
【０１７４】
式(3-10)からわかるように、wを用いることなく、λを計算できるようになる。【０１７５】
以上まとめると、再帰的な変数更新則（式(3-3)〜式(3-6)）は、以下のようになる。【０１７６】
【数６３】
2019198815.tif 000065
【０１７７】
この更新則をノードごとに変数を更新できるようにすると、図１１に示すアルゴリズムが得られる。なお、Transmitj→i{・}はノードjからノードiへ変数を送信する演算を表す。
【先行技術文献】
【非特許文献】
【０１７８】
【非特許文献１】S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers”, Foundations and Trends in Machine Learning, 3(1):1-122, 2011.
【非特許文献２】T. Sherson, R. Heusdens, and W. B. Kleijn, “Derivation and Analysis of the Primal-Dual Method of Multipliers Based on Monotone Operator Theory”, arXiv:1706.02654
【非特許文献３】金森敬文，鈴木 大慈，竹内 一郎，佐藤 一誠，“機械学習のための連続最適化”，講談社，2016年．
【非特許文献４】E. K. Ryu and S. Boyd, “Primer on Monotone Operator Methods”, Appl. Comput. Math., 15(1):3-43, January 2016.
【発明の概要】
【発明が解決しようとする課題】
【０１７９】
まず、第１の課題について説明する。上記の非特許文献１及び２の技術は、ノード間で主変数が送受信されているため、情報の秘密性が高くないと言える。これが第１の課題である。【０１８０】
次に、第２の課題について説明する。上記の非特許文献１及び２の技術は、コスト関数が非凸関数である場合には機械学習を行うことができなかった。これが第２の課題である。【０１８１】
次に、第３の課題について説明する。従来の変数更新則は、リゾルヴェント作用素やケーリー作用素を用いた単調作用素分割に基づき生成したものである。この従来の変数更新則では、場合によっては、最適解への収束に時間がかかるという問題があった。つまり、潜在変数の学習に時間がかかるという問題があった。これが第３の課題である。【０１８２】
そこで本発明では、コスト関数が凸関数でない場合にも機械学習を行うことができる機械学習技術を提供することを目的とする。
【課題を解決するための手段】
【０１８３】
本発明の一態様は、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含み、上記機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われ、代理凸関数は、コスト関数の主変数に関する一次勾配の式、又は、コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている。
【発明の効果】
【０１８４】
本発明によれば、コスト関数に代えてコスト関数の上界となる代理凸関数を用いることで、コスト関数が凸関数でない場合にも機械学習を行うことができる。
【図面の簡単な説明】
【０１８５】
【図１】従来技術を説明するための図である。
【図２】従来技術を説明するための図である。
【図３】従来技術を説明するための図である。
【図４】技術的背景を説明するための図である。
【図５】機械学習システムの例を説明するためのブロック図である。
【図６】ノード部の例を説明するためのブロック図である。
【図７】機械学習方法の例を説明するための流れ図である。
【図８】機械学習方法の変形例を説明するための流れ図である。
【図９】エッジコンピューティングの一例を示す図である。
【図１０Ａ】双対変数のリフティング処理の様子を示す図である。
【図１０Ｂ】双対変数のリフティング処理の様子を示す図である。
【図１１】エッジコンピューティングにおける合意形成問題に関する従来の変数更新アルゴリズムを示す図である。
【図１２】エッジコンピューティングにおける合意形成問題に関する本願の変数更新アルゴリズムを示す図である。
【図１３】エッジコンピューティングにおける合意形成問題に関する本願の変数更新アルゴリズムを示す図である。
【図１４】実験で用いた分散計算器の構成を示す図である。
【図１５】実験結果を示す図である。
【図１６】潜在変数学習装置１００の構成を示すブロック図である。
【図１７】潜在変数学習装置１００の動作を示すフローチャートである。
【図１８】モデル学習部１２０の構成を示すブロック図である。
【図１９】モデル学習部１２０の動作を示すフローチャートである。
【図２０】潜在変数学習システム２０の構成を示すブロック図である。
【図２１】潜在変数学習装置２００の構成を示すブロック図である。
【図２２】モデル学習部２２０の構成を示すブロック図である。
【図２３】モデル学習部２２０の動作を示すフローチャートである。
【図２４】モデル学習部２３０の構成を示すブロック図である。
【図２５】モデル学習部２３０の動作を示すフローチャートである。
【発明を実施するための形態】
【０１８６】
以下、図面を参照して、この発明の一実施形態である第１実施形態について説明する。
【０１８７】
＜技術的背景＞
以下、秘密性を高めた合意形成アルゴリズムについて説明する。この合意形成アルゴリズムは、従来のPDMMを変形したものである。
【０１８８】
まず、以降の説明で用いる記号の定義について説明する。
【０１８９】
Vを２以上の所定の正の整数とし、~V={1,…,V}とする。
【０１９０】
Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とする。
【０１９１】
ノード部iにつながっているノード部の集合を~N(i)とする。
【０１９２】
ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とする。
【０１９３】
機械学習で用いられるノード部iに対応するコスト関数をfiとする。
【０１９４】
双対変数λi|jの補助変数として双対補助変数zi|jを導入し、それを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とする。なお、zi|jの基本的な性質は、λi|jと同じである。
【０１９５】
双対変数λi|jの補助変数として双対補助変数yi|jを導入し、それを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とする。なお、yi|jの基本的な性質は、λi|jと同じである。
【０１９６】
ノード部iの主変数wi,bのb個目の要素をwiとし、wi,bの最適解のb個目の要素をwi,b*とする。
【０１９７】
Ai|jは以下の式により定義されるとする。
【０１９８】
【数６４】
2019198815.tif 000066
【０１９９】
Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とする。Tは更新の総回数であり、正の整数であるが、オンラインの学習を想定した場合には、定数ではない。
【０２００】
解くべき問題は従来のPDMMと同じであるので、再掲する。
【０２０１】
【数６５】
2019198815.tif 000067
【０２０２】
また、この問題をオペレータ分割法で解くという点についても従来のPDMMと同様である。以後、オペレータ分割法の一つであるP-R分割を用いた例について説明する。双対変数λbの補助変数として２種類の双対補助変数yb,zbをを以後用いる。
【０２０３】
P-R分割に基づいて、変数群(主変数，双対変数，双対補助変数)を最適化するステップは以下で書ける。
【０２０４】
【数６６】
2019198815.tif 000068
【０２０５】
上記の式において、「∈」の記号は、集合の要素を表すのではなく、右辺の演算結果を左辺に代入することを意味する。通常、こうした操作は「＝」を用いて表現することが多いが、コスト関数に不連続な閉真凸関数を用いた場合に、非可逆な変換が行われることがある(1対1対応しない演算をすることがあり得る)。「＝」は通常、1対1対応するような変換(関数)に用いられる記号であるため、それと区別するために「∈」の記号を用いることとする。
【０２０６】
ここで、Cn (n=1,2)はケーリー演算子(Cayley operator)である。
【０２０７】
【数６７】
2019198815.tif 000069
【０２０８】
Rn (n=1,2)は リゾルヴェント演算子(Resolvent operator)である。
【０２０９】
【数６８】
2019198815.tif 000070
【０２１０】
Tn(n=1,2)はモノトーン演算子(Monotone operator)である。問題を構成するf*やδ(I-P)とも真凸閉関数であるので、その双対変数に関する偏微分はモノトーン演算子になる。
【０２１１】
【数６９】
2019198815.tif 000071
【０２１２】
理論背景については詳細をここに記述しないが、P-R分割は高速な収束を保証する最適化方式である。P-R分割による最適化zb∈C2C1zbを分解表現すると以下になる。
【０２１３】
【数７０】
2019198815.tif 000072
【０２１４】
なお、２番目のケーリー演算子C2が順序入れ替え行列Pに対応するということについては、非特許文献２にその証明が掲載されている。一番上の双対変数をリゾルヴェント演算子を使った更新は、以下のように変形できる。
【０２１５】
【数７１】
2019198815.tif 000073
【０２１６】
この式に含まれるf*を双対変数に関する閉凸真関数として導出したい。それがノード間で交換する情報量を削減につながるから。その過程について以下説明する。まず、f*の定義を再掲する。
【０２１７】
【数７２】
2019198815.tif 000074
【０２１８】
なお、一つの事例として、最小二乗問題をコストとして扱う場合には、以下となる。
【０２１９】
【数７３】
2019198815.tif 000075
【０２２０】
以後は、説明を分かりやすくするために、最小二乗問題をコストとして扱った場合の更新式について導出する。
【０２２１】
括弧内を微分すると、wの最適解は以下で得られる。このように、最小二乗問題をコストとして扱った場合のwの最適解w*は、双対変数の式で表される。
【０２２２】
【数７４】
2019198815.tif 000076
【０２２３】
このw*をf*に代入することで、f*をλの関数として表せる。ここで、Q=XXTである。
【０２２４】
【数７５】
2019198815.tif 000077
【０２２５】
ここで、Q=XXTである。
【０２２６】
P-R分割に含まれる双対変数の更新式を再掲する。
【０２２７】
【数７６】
2019198815.tif 000078
【０２２８】
最小二乗問題をコストとして扱った場合、括弧内を双対変数に関して微分すると、以下のようになる。
【０２２９】
【数７７】
2019198815.tif 000079
【０２３０】
だから、最小二乗問題をコストとして扱った場合の双対変数に関する最適化は以下で得られる。
【０２３１】
【数７８】
2019198815.tif 000080
【０２３２】
この工夫は、双対変数λを最適化する中で、暗に主変数wも最適化されることを意味している。そして、双対補助変数yをノード間で交換するだけで、P-R分割ベースの分散最適化処理が実現できる。この時点で以下のようにアルゴリズムを書き換えられる。ここでは一般形式で記述する。 
【０２３３】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(5)の処理を行う。(2)主変数更新の処理は、行われなくてもよい。なぜならば、wの最適解であるw*はλの式で表されるため、λの最適化過程において、wの更新を必要としないためである。（λが最適化されればwも暗に最適化されたことを意味する）
(1)双対変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
【０２３４】
【数７９】
2019198815.tif 000081
【０２３５】
(2)主変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
【０２３６】
【数８０】
2019198815.tif 000082
【０２３７】
(3)双対補助変数更新
【０２３８】
【数８１】
2019198815.tif 000083
【０２３９】
(4) 毎回である必要はないし、エッジごとに独立(非同期)でよいが、双対補助変数をノード間で更新する。ここで、「・」を任意の情報として、Nodej←Nodei(・)は、ｉ番目のノード部iがノード部jに情報「・」を送信することを意味する。
【０２４０】
【数８２】
2019198815.tif 000084
【０２４１】
(5) 交換して得た情報を使って双対補助変数更新
【０２４２】
【数８３】
2019198815.tif 000085
【０２４３】
なお、最後の(5)のステップについては、以下の演算と置き換えることで、収束性を低くする代わりに、収束過程において高い安定性を見込めるDouglas Rachford (D-R)分割になる。通常βは1/2が使われる。
【０２４４】
【数８４】
2019198815.tif 000086
【０２４５】
なお、上記の主変数、双対変数の更新は、一般形式のコスト関数を用いている。以下のコスト関数を用いた場合には、合意形成アルゴリズムは以下のようになる。
【０２４６】
【数８５】
2019198815.tif 000087
【０２４７】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(5)の処理を行う。なお、(2)主変数更新の処理は、行われなくてもよい。なぜならば、wの最適解であるw*はλの式で表されるため、λの最適化過程において、wの更新を必要としないためである。（λが最適化されればwも暗に最適化されたことを意味する。）
(1)双対変数更新
【０２４８】
【数８６】
2019198815.tif 000088
【０２４９】
(2)主変数更新
【０２５０】
【数８７】
2019198815.tif 000089
【０２５１】
(3)双対補助変数更新
【０２５２】
【数８８】
2019198815.tif 000090
【０２５３】
(4) 毎回である必要はないし、エッジごとに独立(非同期)でよいが、双対補助変数をノード間で更新する。
【０２５４】
【数８９】
2019198815.tif 000091
【０２５５】
(5) 交換して得た情報を使って双対補助変数更新
【０２５６】
【数９０】
2019198815.tif 000092
【０２５７】
なお、最後の(5)のステップについては、以下の演算と置き換えることで、収束性を低くする代わりに、収束過程において高い安定性を見込めるDouglas Rachford (D-R)分割になる。通常βは1/2が使われる。
【０２５８】
【数９１】
2019198815.tif 000093
【０２５９】
双対補助変数yをノード間で交換しているが、変数の性質は双対変数λと同等と言ってよい。その双対変数は以下のように算出される。
【０２６０】
【数９２】
2019198815.tif 000094
【０２６１】
主変数wには、データの統計的性質が濃く反映されることが多いが、双対変数の統計的性質は、そのルジャンドル変換後のデータに左右される。ルジャンドル変換は関数の構造を知っていないと主変数には戻せないため、双対変数やその双対補助変数をノード間で伝送するのは、秘密性の高いデータ通信と言える。
【０２６２】
＜第１実施形態＞
図５に示すように、機械学習システムは、複数のノード部1,…,V、複数のセンサ部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγ、インターネット0N、LAN 1N,…,VNを例えば備えている。複数のノード部1,…,Vのそれぞれは、サーバ、PC等の情報処理機器である。ノード部1,…,Vのそれぞれには、図６で示すように、学習部１０と送受信部１１が設けられており、学習部１０内には記憶部１２が設けられている。記憶部１２には、以下に説明する処理及び計算に必要なデータが記憶されているとする。
【０２６３】
センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγは、様々な環境(例えば、家、工場、野外及びビル)に、分散して配置された多数のセンサー(例えば、マイク、カメラ、温度計)である。図５の例では、センサー部は1S1,…,1Sαはノード部1に対応するセンサーである。すなわち、センサー部は1S1,…,1Sαはノード部1の学習部１０での機械学習で用いられるデータを取得するセンサーであり、センサー部は1S1,…,1Sγのそれぞれはノード部1とLAN 1Nで接続されている。その他のセンサー部についても同様である。それらのセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγを通じて得られたデータは、複数のノード部1,…,V(例えば、サーバ、PC)に蓄積される。なお、データは、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγから得られるものに限らず、入力装置やWeb等から得られる文字データ等でも構わない。また、図５の例ではセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはLAN1N,…,VNでノード部1,…,Vに接続されているが、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはインターネット0Nを介してノード部1,…,Vに接続されていてもよいし、その他の接続手段で接続されていてもよいし、要するに、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγが得たデータをノード部1,…,Vが用いるようにされていればよい。
【０２６４】
図５の例ではノード部1,…,Vはインターネット0Nを介して接続されているが、ノード部1,…,V間は、全結合ではなく疎に結合されていてもよく、何らかのデータを交換できる関係にあればよい。エッジの連結構造についての制約はなく、木構造、循環／円構造でもなんでもよい。要するに、全てのノード部1,…,Vが直接又は間接的につながっている。すなわち、エッジの連結構造は、分割された構造ではない。
【０２６５】
複数のノード部1,…,Vは、送受信部１１からデータの受信、送受信部１１からのデータの送信、記憶部１２からデータの読み込み、記憶部１２に対するデータの書き込みを適宜行いながら、以下に説明する機械学習処理を行う。機械学習処理は、複数のノード部1,…,Vが図７のステップＳ１からステップＳ８の処理を行うことにより例えば実現される。
【０２６６】
ノード部1,…,Vは、t=0とする（ステップＳ１）。
【０２６７】
ノード部i（より詳細には、ノード部iの学習部１０）は、ノード部iに対応するセンサー部により得られたデータを用いて、以下の式に基づいて双対変数の更新を行う（ステップＳ２）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるλi|j,b(t+1)の計算を行う。
【０２６８】
【数９３】
2019198815.tif 000095
【０２６９】
ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて主変数の更新を行う（ステップＳ３）。すなわち、ノード部iは、i∈~V,b∈~Bのそれぞれに対して、以下の式により定義されるwi,b(t+1)の計算を行う。なお、ステップＳ３の処理は、主変数が必要な場合に行われる。言い換えれば、ステップＳ３の処理は、毎回行われなくてもよい。
【０２７０】
【数９４】
2019198815.tif 000096
【０２７１】
ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて双対補助変数の更新を行う（ステップＳ４）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるyi|j,b(t+1)の計算を行う。なお、このステップＳ４の処理は、ステップＳ５において双対補助変数yi|j,b(t+1)を送信する場合以外は行わなくてもよい。
【０２７２】
【数９５】
2019198815.tif 000097
【０２７３】
ノード部i（より詳細には、ノード部iの送受信部１１）は、双対補助変数yi|j,b(t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信した双対補助変数yj|i,b(t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ５）。例えば、ノード部iは、ノード部iの学習部１０が得た双対補助変数yi|j,b(t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信した双対補助変数をノード部iの学習部１０に双対補助変数yj|i,b(t+1)として入力するように動作する。なお、ステップＳ５の処理は毎回行わなくてよいし、ノード間で非同期でよい。例えば、tが偶数のときにのみ、全てのノード部iが、ノード部iが得た双対補助変数yi|j,b(t+1)を別のノード部jに対して送信する処理と、別のノード部jが出力した双対補助変数yj|i,b(t+1)を受信する処理と、の両方を行い、tが奇数のときには何れのノード部iも双対補助変数の送信も受信もしないようにしてもよい。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信し、ノード部jが出力した双対補助変数yj|i,b(t+1)を受信する。
【０２７４】
【数９６】
2019198815.tif 000098
【０２７５】
ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて、双対補助変数の更新を行う（ステップＳ６）。すなわち、i∈~V, j∈~N(i), b∈~Bとして、ノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とする処理を行う。なお、ステップＳ６の処理は、ステップＳ５において双対補助変数yj|i,b(t+1)を受信した場合以外は行わなくてよい。すなわち、ステップＳ６の処理は、双対補助変数yj|i,b(t+1)を受信したノード部iのみが行えばよい。
【０２７６】
【数９７】
2019198815.tif 000099
【０２７７】
ノード部1,…,Vは、t=t+1とする（ステップＳ７）。すなわち、ノード部1,…,Vは、tを１だけインクリメントする。
【０２７８】
ノード部1,…,Vは、t=Tであるか判定し（ステップＳ８）、t=Tであれば処理を終了する。t=Tでない場合には、ステップＳ２の処理に戻る。
【０２７９】
このように、それぞれ入力データが記憶されており、情報を互いに送受信しながら、教師データ及び入力データに基づいて主変数wを用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、複数のノード部iは、機械学習において用いられる双対変数を最適化すれば、主変数も最適化されるように、かつ、主変数ではなく、双対変数を互いに送受信しながら、機械学習を行う。これにより、ノード部iの間で主変数が送受信されないため、従来よりも秘密性が高い機械学習を行うことができる。
《変形例》
［変形例１］
一般形式のコスト関数ではなく、以下のコスト関数を用いた場合には、
【０２８０】
【数９８】
2019198815.tif 000100
【０２８１】
ステップＳ２において、ノード部iは、以下の式に基づいて双対変数の更新を行う。
【０２８２】
【数９９】
2019198815.tif 000101
【０２８３】
また、ステップＳ３において、ノード部iは、以下の式に基づいて主変数の更新を行う。
【０２８４】
【数１００】
2019198815.tif 000102
【０２８５】
［変形例２］
i=1,…,Vとして、ノード部iにDi個のデータが蓄積されているが、Diは時間によって変化してもよい。オンラインの最適化にも対応可能である。このとき、コスト関数は、以下のよう書ける
【０２８６】
【数１０１】
2019198815.tif 000103
【０２８７】
［変形例３］
ステップＳ５において、ノード部iは、双対補助変数yi|j,b(t+1)ではなく、双対変数λi|j,b(t+1)を送受信してもよい。
【０２８８】
この場合、ステップＳ６の処理は行われない。ステップＳ６以外のステップの処理は上記と同様に行われる。
［変形例４］
以下では、伝送容量を圧縮するための工夫について説明する。
【０２８９】
最適化処理が収束するにつれて、更新差分が0に近づく。その性質を利用して、非可逆な圧縮処理をすれば、更に伝送容量を低く抑えられるはずである。
【０２９０】
情報圧縮の方法については様々考えられるが、更新差分を伝送しあうというアイデアを基軸に、(i) フロアリングベースの圧縮処理と、(ii) エントロピー符号化ベースの圧縮処理がある。
【０２９１】
まず、参照データがときどき更新されるとし、そのデータとの差分データを変数vとおく。ここで、vi|j,b(t+1)は、更新差分情報である。vi|j,b(t+1)は、収束するほど、0に近い数字に偏る傾向がある。vi|j,b(t+1)は、本来、ノード間で交換したい情報である。mi|j,b(export)は、既に得ている参照情報である。
【０２９２】
【数１０２】
2019198815.tif 000104
【０２９３】
そのvに圧縮処理Cを適用する。
【０２９４】
【数１０３】
2019198815.tif 000105
【０２９５】
(i) フロアリングベースの圧縮処理の場合には、vを構成するそれぞれの要素と閾値thrを比較し、閾値以下であれば0にするような処理をする。thrは、所定の0より大きな所定の数であり、例えば1×10-5等の非常に小さな数である。
【０２９６】
【数１０４】
2019198815.tif 000106
【０２９７】
(ii) エントロピー符号化ベースの圧縮処理の場合には、出現確率に応じてシンボルを割り当てるような処理をしてuを生成する。例えば、出現確率が値に対して、短いシンボルを割り当てることによりuを生成する。
【０２９８】
このとき、コスト関数を一般形式で記述した場合の合意形成アルゴリズムは以下のようになる。
【０２９９】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(10)の処理を行う。(2)主変数更新の処理は、行われなくてもよい。なぜならば、wの最適解であるw*はλの式で表されるため、λの最適化過程において、wの更新を必要としないためである。（λが最適化されればwも暗に最適化されたことを意味する）
(1)双対変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
【０３００】
【数１０５】
2019198815.tif 000107
【０３０１】
(2)主変数更新（ここでは、最小二乗問題に限定せず、コストを一般形式として記述する。）
【０３０２】
【数１０６】
2019198815.tif 000108
【０３０３】
(3)双対補助変数更新
【０３０４】
【数１０７】
2019198815.tif 000109
【０３０５】
mod (t, Tinterval)=0である場合には、以下の(4)から(6)の処理を行う。すなわち、たまに参照データを更新する。ここで、Tintervalは、所定の正の整数である。
(4) 参照データの更新
【０３０６】
【数１０８】
2019198815.tif 000110
【０３０７】
(5) ノード間で情報交換 (エッジごとに独立（非同期）でよい。)
【０３０８】
【数１０９】
2019198815.tif 000111
【０３０９】
(6)交換して得た情報を使って双対補助変数更新
【０３１０】
【数１１０】
2019198815.tif 000112
【０３１１】
mod (t, Tinterval)=0でない場合には、以下の(7)から(10)の処理を行う。すなわち、ほとんどの時刻で更新差分を伝送しあう。
(7) 更新差分を計算
【０３１２】
【数１１１】
2019198815.tif 000113
【０３１３】
(8) データを圧縮する
【０３１４】
【数１１２】
2019198815.tif 000114
【０３１５】
(9) 圧縮されたデータをノード間で交換
【０３１６】
【数１１３】
2019198815.tif 000115
【０３１７】
(10) 交換して得た情報を使って双対補助変数更新
【０３１８】
【数１１４】
2019198815.tif 000116
【０３１９】
このような伝送容量の削減を行うために、上記の実施形態において、ノード部iは、ステップＳ５からステップＳ６の処理に代えて、以下に説明するステップＳ９からステップＳ１６の処理を行えばよい。他の処理は、上記の実施形態と同様であるため、ここでは重複説明を省略する。図８に、伝送容量の削減を行った機械学習方法の例の流れ図を示す。
【０３２０】
ノード部1,…,Vは、mod (t, Tinterval)=0であるか判定する（ステップＳ９）。
【０３２１】
mod (t, Tinterval)=0である場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。
【０３２２】
【数１１５】
2019198815.tif 000117
【０３２３】
ノード部i（より詳細には、ノード部iの送受信部１１）は、mi|j,b(export)を別のノード部jに対して送信する処理と、別のノード部jが送信したmj|i,b(import)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ１１）。例えば、ノード部iは、ノード部iの学習部１０が得たmi|j,b(export)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したmj|i,b(import)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jにmi|j,b(export)を送信し、ノード部jが出力したmj|i,b(import)を受信する（ステップＳ１１）。
【０３２４】
【数１１６】
2019198815.tif 000118
【０３２５】
ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に示すように、交換して得た情報を使って双対補助変数zi|j,b(t+1)の更新を行う（ステップＳ１２）。
【０３２６】
【数１１７】
2019198815.tif 000119
【０３２７】
mod (t, Tinterval)=0でない場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて更新差分を計算する（ステップＳ１３）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるvi|j,b(t+1)の計算を行う。
【０３２８】
【数１１８】
2019198815.tif 000120
【０３２９】
ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、データを圧縮することにより符号をui|j,b(t+1)生成する（ステップＳ１４）。このデータの圧縮は、非可逆であってもよい。ここで、Cは、フロアリングベースの圧縮処理、エントロピー符号化ベースの圧縮処理等の所定の圧縮処理を意味する。
【０３３０】
【数１１９】
2019198815.tif 000121
【０３３１】
ノード部i（より詳細には、ノード部iの送受信部１１）は、ui|j,b(t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信したuj|i,b(t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に基づいて、圧縮されたデータをノード部間で交換する（ステップＳ１５）。例えば、ノード部iは、ノード部iの学習部１０が得たui|j,b(t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したuj|i,b(t+1)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに符号ui|j,b(t+1)を送信し、ノード部jが出力した符号uj|i,b(t+1)を受信する（ステップＳ１５）。
【０３３２】
【数１２０】
2019198815.tif 000122
【０３３３】
ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、双対補助変数zi|j,b(t+1)の更新を行う（ステップＳ１６）。
【０３３４】
【数１２１】
2019198815.tif 000123
【０３３５】
なお、ステップ１２において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
【０３３６】
【数１２２】
2019198815.tif 000124
【０３３７】
また、ステップＳ１６において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
【０３３８】
【数１２３】
2019198815.tif 000125
【０３３９】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
《プログラム及び記録媒体》
機械学習システムを、１つのコンピュータによって実現してもよい。この場合、機械学習システムの各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、機械学習システムの処理がコンピュータ上で実現される。
【０３４０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０３４１】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【０３４２】
以下、図面を参照して、この発明の一実施形態である第２実施形態について説明する。
【０３４３】
＜技術的背景＞
以下、非凸関数に対する最適化にも適用できる合意形成アルゴリズムについて説明する。
【０３４４】
まず、以降の説明で用いる記号の定義について説明する。
【０３４５】
Vを２以上の所定の正の整数とし、~V={1,…,V}とする。
【０３４６】
Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とする。
【０３４７】
ノード部iにつながっているノード部の集合を~N(i)とする。
【０３４８】
ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とする。
【０３４９】
双対変数λi|jの補助変数として双対補助変数zi|jを導入し、それを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とする。なお、zi|jの基本的な性質は、λi|jと同じである。
【０３５０】
双対変数λi|jの補助変数として双対補助変数yi|jを導入し、それを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とする。なお、yi|jの基本的な性質は、λi|jと同じである。
【０３５１】
ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b(t)とする。
【０３５２】
機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b(t)に関する一次勾配を∇fi(wi,b(t))とする。
【０３５３】
Ai|jは以下の式により定義されるとする。
【０３５４】
【数１２４】
2019198815.tif 000126
【０３５５】
Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とする。Tは更新の総回数であり、正の整数であるが、オンラインの学習を想定した場合には、定数ではない。ηを正の数とする。
【０３５６】
基本的なアイデアは、非凸関数を凸関数によって置き換えることである。この操作は、非特許文献３の15.3節にある近接勾配法の考え方に基づく。関数fの勾配が以下のようにリプシッツ連続であると仮定する。ここで、fは非凸の関数であってもよい。
【０３５７】
【数１２５】
2019198815.tif 000127
【０３５８】
ここで、ηは、fiの勾配の平滑さを表しており、ηを十分小さい値にすれば、多くの場合で満たされる仮定である。例えば、h=0.001とする。上記の式を満たすとき、fiは1/η平滑関数と呼ばれる。
【０３５９】
fiが1/η平滑関数であるとき、以下の不等式関係が成り立つ。
【０３６０】
【数１２６】
2019198815.tif 000128
【０３６１】
ここから以下を導ける。ここで、x,yを任意のベクトルとして、<x,y>はxとyの内積を表す。なお、ηが小さいほど、右辺の凸関数の勾配が大きい(鋭い関数になる)ので、コストの上界であるという条件を満たす。このため、ηは、小さい数であってもよい。ただし、ηが小さすぎると、更新のステップが小さくなるので、最適解にたどり着くまでに時間がかかるという特徴がある。
【０３６２】
【数１２７】
2019198815.tif 000129
【０３６３】
この式は、コスト関数fiの上界となる凸関数(右辺)を導出したことを示している。たとえ、fiが非凸関数であったとしても、その代わりに上界となる代理凸関数(右辺)を最小化するという手段をとれば、PDMMの合意型エッジコンピューティングの考え方を非凸関数にも取り入れられるはずである。
【０３６４】
ここで、補足説明として、コスト関数fiの代わりにその上界となる代理凸関数を最小化するとはどういうことかについて説明する。
【０３６５】
図４において、実線は元々のコスト関数fiを表す。図４では、コスト関数fiを非凸関数として書いている。図４において、一点鎖線は、上界となる代理凸関数giを表す。
【０３６６】
【数１２８】
2019198815.tif 000130
【０３６７】
ここで、fi(wi,b(t))は、更新時刻tにおける関数出力であり、計算可能である。また、∇fi(wi,b(t))は、更新時刻tにおける関数の勾配であり、DNNを想定した場合、確率的最適化の枠組みで計算可能である。
【０３６８】
このため、fiに関する一次勾配さえ計算できるのであれば、上記の代理凸関数giは計算できる。DNNはそれに該当する。
【０３６９】
なお、代理関数は、上記以外の別のものでもよい。先に示した代理凸関数giは、元のコストの上界を表現しており、コスト関数の一次勾配さえ求まればよいという利点があった。それは非凸関数にも適用できるというメリットでもある。
【０３７０】
しかし、もし、コスト関数の二次勾配が求まるのであれば、以下のような代理関数を使ってもよい。以下の式の下線部分を代理関数とする。
【０３７１】
【数１２９】
2019198815.tif 000131
【０３７２】
これは、二次のテーラー展開を用いて表現した(上界ではなく)近似関数である。この代理関数を用いると、元のコスト関数に対する近似精度が高いので、元のコストを小さくすることとのギャップがより小さくなることが見込める。
【０３７３】
代理凸関数の概念としては、元のコスト関数を最小化することと相反しない凸関数であり、上界や近似といった考え方で実装できる。具体的には、元のコスト関数の主変数に関する一次、場合によっては二次の勾配を使って計算できる凸関数である。
【０３７４】
以下では、コスト関数を代理凸関数giとした場合のPDMMアルゴリズムの導出について説明する。
【０３７５】
【数１３０】
2019198815.tif 000132
【０３７６】
この時、双対問題は以下で書ける。
【０３７７】
【数１３１】
2019198815.tif 000133
【０３７８】
変数の定義は以下の通りである。なお、以下のfは一例であり、他のfを用いてもよい。
【０３７９】
【数１３２】
2019198815.tif 000134
【０３８０】
主変数及び双対変数のそれぞれで合意形成するという条件は以下で書ける。
【０３８１】
【数１３３】
2019198815.tif 000135
【０３８２】
関数gの凸共役関数g*を解くことで、wの最適解を導く。
【０３８３】
【数１３４】
2019198815.tif 000136
【０３８４】
括弧内を最大化するwは、以下である。
【０３８５】
【数１３５】
2019198815.tif 000137
【０３８６】
このプロセスは各ノードごとに分割して書くことができる。
【０３８７】
【数１３６】
2019198815.tif 000138
【０３８８】
これを双対関数に代入することで、以下の式を得る。このように、双対変数λに関する真凸閉関数にする。
【０３８９】
【数１３７】
2019198815.tif 000139
【０３９０】
元の双対問題は以下で書ける。
【０３９１】
【数１３８】
2019198815.tif 000140
【０３９２】
この問題を解くために、PDMMと同様に以下のようなコストを設計する。
【０３９３】
【数１３９】
2019198815.tif 000141
【０３９４】
この問題をP-R分割で解く場合には、以下の演算で構成されることは従来法で説明した。
【０３９５】
【数１４０】
2019198815.tif 000142
【０３９６】
上記の式において、「∈」の記号は、集合の要素を表すのではなく、右辺の演算結果を左辺に代入することを意味する。通常、こうした操作は「＝」を用いて表現することが多いが、コスト関数に不連続な閉真凸関数を用いた場合に、非可逆な変換が行われることがある(1対1対応しない演算をすることがあり得る)。「＝」は通常、1対1対応するような変換(関数)に用いられる記号であるため、それと区別するために「∈」の記号を用いることとする。
【０３９７】
このうち、一番上の演算は、以下に対応している。
【０３９８】
【数１４１】
2019198815.tif 000143
【０３９９】
g*を再掲する。
【０４００】
【数１４２】
2019198815.tif 000144
【０４０１】
括弧内を最大化するw(主変数の最適解)を求める。すなわち、上記式の括弧内を微分した値を０とするwb*を求めると以下のようになる。
【０４０２】
【数１４３】
2019198815.tif 000145
【０４０３】
次に、P-R分割の一番上の演算を満たす双対変数の最適解を導く。
【０４０４】
【数１４４】
2019198815.tif 000146
【０４０５】
括弧内を双対変数に関して微分し、途中計算を省略するが以下の式が得られる。
【０４０６】
【数１４５】
2019198815.tif 000147
【０４０７】
ノードごとの演算に分割すると、P-R分割ベースで代理凸関数を用いて変数最適化アルゴリズムが得られる。このアルゴリズムのことを、Quadratic PDMMとも呼ぶ。Quadratic PDMMは、以下のようになる。
【０４０８】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(5)の処理を行う。
(1)双対変数更新
【０４０９】
【数１４６】
2019198815.tif 000148
【０４１０】
(2)主変数更新
【０４１１】
【数１４７】
2019198815.tif 000149
【０４１２】
(3)双対補助変数更新
【０４１３】
【数１４８】
2019198815.tif 000150
【０４１４】
(4) 毎回である必要はないし、エッジごとに独立(非同期)でよいが、双対補助変数をノード間で更新する。
【０４１５】
【数１４９】
2019198815.tif 000151
【０４１６】
(5) 交換して得た情報を使って双対補助変数更新
【０４１７】
【数１５０】
2019198815.tif 000152
【０４１８】
なお、最後の(5)のステップについては、以下の演算と置き換えることで、収束性を低くする代わりに、収束過程において高い安定性を見込めるDouglas Rachford (D-R)分割になる。通常βは1/2が使われる。
【０４１９】
【数１５１】
2019198815.tif 000153
【０４２０】
Quadratic-PDMMアルゴリズムでは、代理凸関数が更新時刻ごとに変わっている点で秘密性は高いと言える。
【０４２１】
Quadratic-PDMMアルゴリズムがノード間で異質なデータセットを持っている場合にも、収束することを示すために、収束率を導出する。問題は、以下のように２種類の凸関数で構成されたコストの最小化問題であった。
【０４２２】
【数１５２】
2019198815.tif 000154
【０４２３】
まず、gは、1/η-強凸関数であることを示す。
【０４２４】
もし、g(wb)-(1/(2η))||wb||2が凸関数であれば、gが 1/η-強凸関数であることと等価である（例えば、非特許文献３の2.2.5節参照。）。
【０４２５】
【数１５３】
2019198815.tif 000155
【０４２６】
ここで、ηが十分に小さいことが仮定されていることから、cosθは負値になるだろう。
【０４２７】
【数１５４】
2019198815.tif 000156
【０４２８】
そのとき、g(wb)-(1/(2η))||wb||2は凸関数になるから、gは1/η-強凸関数であろう。
【０４２９】
次に、非特許文献３の2.2.5節より、gが1/η-強凸関数であるとき、g*はη-平滑関数になることが知られている。そのとき、以下の性質を満たす。
【０４３０】
【数１５５】
2019198815.tif 000157
【０４３１】
近接写像関数を以下のように定義する。
【０４３２】
【数１５６】
2019198815.tif 000158
【０４３３】
近接写像の定義より、以下の関係を得られる。
【０４３４】
【数１５７】
2019198815.tif 000159
【０４３５】
そのとき、
【０４３６】
【数１５８】
2019198815.tif 000160
【０４３７】
g*がη-平滑関数であるから、以下の関係を満たす。
【０４３８】
【数１５９】
2019198815.tif 000161
【０４３９】
そのとき、以下の関係を満たす。
【０４４０】
【数１６０】
2019198815.tif 000162
【０４４１】
【数１６１】
2019198815.tif 000163
【０４４２】
と代入すると、以下の関係を得られる。
【０４４３】
【数１６２】
2019198815.tif 000164
【０４４４】
Gは、η-平滑関数であるg*と凸性の非常に強い指示関数δで構成される。指示関数がGに含まれているので、Gは強い凸性の関数であると言える。Gをξ-強凸関数であると仮定すると、以下を満たす。
【０４４５】
【数１６３】
2019198815.tif 000165
【０４４６】
そのとき、以下を満たす。
【０４４７】
【数１６４】
2019198815.tif 000166
【０４４８】
よって以下になる。
【０４４９】
【数１６５】
2019198815.tif 000167
【０４５０】
式変形をすると、収束率が求まる。
【０４５１】
【数１６６】
2019198815.tif 000168
【０４５２】
ξは十分値が大きく、ηは十分小さな値であることを仮定しているので、収束率は高い。また、この中にデータセットの異質性に依存する変数が存在しないことから、データセットの統計的性質に依存しないで、収束することが想定される。
【０４５３】
＜第２実施形態＞
図５に示すように、機械学習システムは、複数のノード部1,…,V、複数のセンサ部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγ、インターネット0N、LAN 1N,…,VNを例えば備えている。複数のノード部1,…,Vのそれぞれは、サーバ、PC等の情報処理機器である。ノード部1,…,Vのそれぞれには、図６で示すように、学習部１０と送受信部１１が設けられており、学習部１０内には記憶部１２が設けられている。記憶部１２には、以下に説明する処理及び計算に必要なデータが記憶されているとする。
【０４５４】
センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγは、様々な環境(例えば、家、工場、野外及びビル)に、分散して配置された多数のセンサー(例えば、マイク、カメラ、温度計)である。図５の例では、センサー部は1S1,…,1Sαはノード部1に対応するセンサーである。すなわち、センサー部は1S1,…,1Sαはノード部1の学習部１０での機械学習で用いられるデータを取得するセンサーであり、センサー部は1S1,…,1Sγのそれぞれはノード部1とLAN 1Nで接続されている。その他のセンサー部についても同様である。それらのセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγを通じて得られたデータは、複数のノード部1,…,V(例えば、サーバ、PC)に蓄積される。なお、データは、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγから得られるものに限らず、入力装置やWeb等から得られる文字データ等でも構わない。また、図５の例ではセンサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはLAN1N,…,VNでノード部1,…,Vに接続されているが、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγはインターネット0Nを介してノード部1,…,Vに接続されていてもよいし、その他の接続手段で接続されていてもよいし、要するに、センサー部1S1,…,1Sα,2S1,…,2Sβ,VS1,…,VSγが得たデータをノード部1,…,Vが用いるようにされていればよい。
【０４５５】
図５の例ではノード部1,…,Vはインターネット0Nを介して接続されているが、ノード部1,…,V間は、全結合ではなく疎に結合されていてもよく、何らかのデータを交換できる関係にあればよい。エッジの連結構造についての制約はなく、木構造、循環／円構造でもなんでもよい。要するに、全てのノード部1,…,Vが直接又は間接的につながっている。すなわち、エッジの連結構造は、分割された構造ではない。
【０４５６】
複数のノード部1,…,Vは、送受信部１１からデータの受信、送受信部１１からのデータの送信、記憶部１２からデータの読み込み、記憶部１２に対するデータの書き込みを適宜行いながら、以下に説明する機械学習処理を行う。機械学習処理は、複数のノード部1,…,Vが図７のステップＳ１からステップＳ８の処理を行うことにより例えば実現される。
【０４５７】
ノード部1,…,Vは、t=0とする（ステップＳ１）。
【０４５８】
ノード部i（より詳細には、ノード部iの学習部１０）は、ノード部iに対応するセンサー部により得られたデータを用いて、以下の式に基づいて双対変数の更新を行う（ステップＳ２）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるλi|j,b(t+1)の計算を行う。
【０４５９】
【数１６７】
2019198815.tif 000169
【０４６０】
ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて主変数の更新を行う（ステップＳ３）。すなわち、ノード部iは、i∈~V,b∈~Bのそれぞれに対して、以下の式により定義されるwi,b(t+1)の計算を行う。
【０４６１】
【数１６８】
2019198815.tif 000170
【０４６２】
ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて双対補助変数の更新を行う（ステップＳ４）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるyi|j,b(t+1)の計算を行う。なお、このステップＳ４の処理は、ステップＳ５において双対補助変数yi|j,b(t+1)を送信する場合以外は行わなくてもよい。
【０４６３】
【数１６９】
2019198815.tif 000171
【０４６４】
ノード部i（より詳細には、ノード部iの送受信部１１）は、双対補助変数yi|j,b(t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信した双対補助変数yj|i,b(t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ５）。例えば、ノード部iは、ノード部iの学習部１０が得た双対補助変数yi|j,b(t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信した双対補助変数をノード部iの学習部１０に双対補助変数yj|i,b(t+1)として入力するように動作する。なお、ステップＳ５の処理は毎回行わなくてよいし、ノード間で非同期でよい。例えば、tが偶数のときにのみ、全てのノード部iが、ノード部iが得た双対補助変数yi|j,b(t+1)を別のノード部jに対して送信する処理と、別のノード部jが出力した双対補助変数yj|i,b(t+1)を受信する処理と、の両方を行い、tが奇数のときには何れのノード部iも双対補助変数の送信も受信もしないようにしてもよい。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信し、ノード部jが出力した双対補助変数yj|i,b(t+1)を受信する。
【０４６５】
【数１７０】
2019198815.tif 000172
【０４６６】
ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて、双対補助変数の更新を行う（ステップＳ６）。すなわち、i∈~V, j∈~N(i), b∈~Bとして、ノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とする処理を行う。なお、ステップＳ６の処理は、ステップＳ５において双対補助変数yj|i,b(t+1)を受信した場合以外は行わなくてよい。すなわち、ステップＳ６の処理は、双対補助変数yj|i,b(t+1)を受信したノード部iのみが行えばよい。
【０４６７】
【数１７１】
2019198815.tif 000173
【０４６８】
ノード部1,…,Vは、t=t+1とする（ステップＳ７）。すなわち、ノード部1,…,Vは、tを１だけインクリメントする。
【０４６９】
ノード部1,…,Vは、t=Tであるか判定し（ステップＳ８）、t=Tであれば処理を終了する。t=Tでない場合には、ステップＳ２の処理に戻る。
【０４７０】
このように、それぞれ入力データが記憶されており、情報を互いに送受信しながら、教師データ及び上記入力データに基づいて主変数を用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、機械学習で用いられるコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われる。言い換えれば、複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、
複数のノード部は、機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われる。
【０４７１】
また、代理凸関数は、コスト関数の主変数に関する一次勾配の式、又は、コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている。
【０４７２】
コスト関数に代えてコスト関数の上界となる代理凸関数を用いることで、コスト関数が凸関数でない場合にも機械学習を行うことができる。また、ノード部iの間で主変数が送受信されないため、従来よりも秘密性が高い機械学習を行うことができる。
《変形例》
［変形例１］
i=1,…,Vとして、ノード部iにDi個のデータが蓄積されているが、Diは時間によって変化してもよい。オンラインの最適化にも対応可能である。このとき、コスト関数は、以下のよう書ける
【０４７３】
【数１７２】
2019198815.tif 000174
【０４７４】
［変形例２］
ステップＳ５において、ノード部iは、双対補助変数yi|j,b(t+1)ではなく、双対変数λi|j,b(t+1)を送受信してもよい。
【０４７５】
この場合、ステップＳ６の処理は行われない。ステップＳ６以外のステップの処理は上記と同様に行われる。
［変形例３］
以下では、伝送容量を圧縮するための工夫について説明する。
【０４７６】
最適化処理が収束するにつれて、更新差分が0に近づく。その性質を利用して、非可逆な圧縮処理をすれば、更に伝送容量を低く抑えられるはずである。
【０４７７】
情報圧縮の方法については様々考えられるが、更新差分を伝送しあうというアイデアを基軸に、(i) フロアリングベースの圧縮処理と、(ii) エントロピー符号化ベースの圧縮処理がある。
【０４７８】
まず、参照データがときどき更新されるとし、そのデータとの差分データを変数vとおく。ここで、vi|j,b(t+1)は、更新差分情報である。vi|j,b(t+1)は、収束するほど、0に近い数字に偏る傾向がある。vi|j,b(t+1)は、本来、ノード間で交換したい情報である。mi|j,b(export)は、既に得ている参照情報である。
【０４７９】
【数１７３】
2019198815.tif 000175
【０４８０】
そのvに圧縮処理Cを適用する。
【０４８１】
【数１７４】
2019198815.tif 000176
【０４８２】
(i) フロアリングベースの圧縮処理の場合には、vを構成するそれぞれの要素と閾値thrを比較し、閾値以下であれば0にするような処理をする。thrは、所定の0より大きな所定の数であり、例えば1×10-5等の非常に小さな数である。
【０４８３】
【数１７５】
2019198815.tif 000177
【０４８４】
(ii) エントロピー符号化ベースの圧縮処理の場合には、出現確率に応じてシンボルを割り当てるような処理をしてuを生成する。例えば、出現確率が値に対して、短いシンボルを割り当てることによりuを生成する。
【０４８５】
このとき、コスト関数を一般形式で記述した場合の合意形成アルゴリズムは以下のようになる。
【０４８６】
T回更新するとして、t∈{0,…,T-1}に対して、以下の(1)から(10)の処理を行う。
(1)双対変数更新
【０４８７】
【数１７６】
2019198815.tif 000178
【０４８８】
(2)主変数更新
【０４８９】
【数１７７】
2019198815.tif 000179
【０４９０】
(3)双対補助変数更新
【０４９１】
【数１７８】
2019198815.tif 000180
【０４９２】
mod (t, Tinterval)=0である場合には、以下の(4)から(6)の処理を行う。すなわち、たまに参照データを更新する。ここで、Tintervalは、所定の正の整数である。
【０４９３】
(4) 参照データの更新
【０４９４】
【数１７９】
2019198815.tif 000181
【０４９５】
(5) ノード間で情報交換 (エッジごとに独立（非同期）でよい。)
【０４９６】
【数１８０】
2019198815.tif 000182
【０４９７】
(6)交換して得た情報を使って双対補助変数更新
【０４９８】
【数１８１】
2019198815.tif 000183
【０４９９】
mod (t, Tinterval)=0でない場合には、以下の(7)から(10)の処理を行う。すなわち、ほとんどの時刻で更新差分を伝送しあう。
(7) 更新差分を計算
【０５００】
【数１８２】
2019198815.tif 000184
【０５０１】
(8) データを圧縮する
【０５０２】
【数１８３】
2019198815.tif 000185
【０５０３】
(9) 圧縮されたデータをノード間で交換
【０５０４】
【数１８４】
2019198815.tif 000186
【０５０５】
(10) 交換して得た情報を使って双対補助変数更新
【０５０６】
【数１８５】
2019198815.tif 000187
【０５０７】
このような伝送容量の削減を行うために、上記の実施形態において、ノード部iは、ステップＳ５からステップＳ６の処理に代えて、以下に説明するステップＳ９からステップＳ１６の処理を行えばよい。他の処理は、上記の実施形態と同様であるため、ここでは重複説明を省略する。図８に、伝送容量の削減を行った機械学習方法の例の流れ図を示す。
【０５０８】
ノード部1,…,Vは、mod (t, Tinterval)=0であるか判定する（ステップＳ９）。
【０５０９】
mod (t, Tinterval)=0である場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて参照データの更新を行う（ステップＳ１０）。
【０５１０】
【数１８６】
2019198815.tif 000188
【０５１１】
ノード部i（より詳細には、ノード部iの送受信部１１）は、mi|j,b(export)を別のノード部jに対して送信する処理と、別のノード部jが送信したmj|i,b(import)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に示すようにノード部の間で情報交換を行う（ステップＳ１１）。例えば、ノード部iは、ノード部iの学習部１０が得たmi|j,b(export)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したmj|i,b(import)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jにmi|j,b(export)を送信し、ノード部jが出力したmj|i,b(import)を受信する（ステップＳ１１）。
【０５１２】
【数１８７】
2019198815.tif 000189
【０５１３】
ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に示すように、交換して得た情報を使って双対補助変数zi|j,b(t+1)の更新を行う（ステップＳ１２）。
【０５１４】
【数１８８】
2019198815.tif 000190
【０５１５】
mod (t, Tinterval)=0でない場合には、ノード部i（より詳細には、ノード部iの学習部１０）は、以下の式に基づいて更新差分を計算する（ステップＳ１３）。すなわち、ノード部iは、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式により定義されるvi|j,b(t+1)の計算を行う。
【０５１６】
【数１８９】
2019198815.tif 000191
【０５１７】
ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、データを圧縮することにより符号をui|j,b(t+1)生成する（ステップＳ１４）。このデータの圧縮は、非可逆であってもよい。ここで、Cは、フロアリングベースの圧縮処理、エントロピー符号化ベースの圧縮処理等の所定の圧縮処理を意味する。
【０５１８】
【数１９０】
2019198815.tif 000192
【０５１９】
ノード部i（より詳細には、ノード部iの送受信部１１）は、ui|j,b(t+1)を別のノード部jに対して送信する処理と、別のノード部jが送信したuj|i,b(t+1)を受信する処理と、の少なくとも何れかを行う、すなわち、以下の式に基づいて、圧縮されたデータをノード部間で交換する（ステップＳ１５）。例えば、ノード部iは、ノード部iの学習部１０が得たui|j,b(t+1)をノード部iの送受信部１１がノード部ｊに対して送信し、ノード部iの送受信部１１がノード部ｊから受信したuj|i,b(t+1)をノード部iの学習部１０に入力するように動作する。また、全てのノード部i,jではなく、一部のノード部iのみが一部のノード部jに対してのみに以下の式に示す処理を行ってもよい。言い換えれば、i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに符号ui|j,b(t+1)を送信し、ノード部jが出力した符号uj|i,b(t+1)を受信する（ステップＳ１５）。
【０５２０】
【数１９１】
2019198815.tif 000193
【０５２１】
ノード部i（より詳細には、ノード部iの学習部１０）は、i∈~V,j∈~N(i),b∈~Bのそれぞれに対して、以下の式に基づいて、双対補助変数zi|j,b(t+1)の更新を行う（ステップＳ１６）。
【０５２２】
【数１９２】
2019198815.tif 000194
【０５２３】
なお、ステップ１２において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
【０５２４】
【数１９３】
2019198815.tif 000195
【０５２５】
また、ステップＳ１６において、ノード部iは、以下に例示するD-R分割ベースの更新を行ってもよい。通常βは1/2が使われる。
【０５２６】
【数１９４】
2019198815.tif 000196
【０５２７】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
《プログラム及び記録媒体》
機械学習システムを、１つのコンピュータによって実現してもよい。この場合、機械学習システムの各部が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、機械学習システムの処理がコンピュータ上で実現される。
【０５２８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０５２９】
また、各部の処理は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理の少なくとも一部をハードウェア的に実現することとしてもよい。
【０５３０】
以下、本発明の実施形態である第３実施形態及び第４実施形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【０５３１】
各実施形態の説明に先立って、この明細書における表記方法について説明する。
【０５３２】
_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【０５３３】
＜技術的背景＞
本願では、リゾルヴェント作用素やケーリー作用素を用いる代わりに、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いる。つまり、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づき、変数更新則を構成する。以下、詳細に説明する。
《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》
まず、ブレグマンダイバージェンスBについて説明する。ブレグマンダイバージェンスBは連続で微分可能な狭義凸関数Dを用いて以下のように定義される（以後、連続で微分可能な狭義凸関数のことを単に狭義凸関数という）。
【０５３４】
【数１９５】
2019198815.tif 000197
【０５３５】
関数Dとして任意の狭義凸関数を用いることができる。なお、ユークリッド距離もブレグマンダイバージェンスの一種である。また、ブレグマンダイバージェンスBが関数Dを用いて定義されることを明示するために、ブレグマンダイバージェンスBDと書くこともある。
【０５３６】
狭義凸関数Dは、ある種の連続性を有する関数である。具体的には、狭義凸関数Dは、強凸(SC: strong convex)とリプシッツ平滑(LS: Lipschitz smooth)という性質を有する。これらの性質は以下のように表現できる。
（性質1）2次のテーラー展開を用いると、関数Dに対して、点wの周りにおいて以下の近似式が成り立つ。
【０５３７】
【数１９６】
2019198815.tif 000198
【０５３８】
ここで、ヘシアン行列HD(w) (HD(w)∈Rm×m)は、正定値行列である。
【０５３９】
【数１９７】
2019198815.tif 000199
【０５４０】
なお、行列A,Bに対して、次式は行列B-Aが正定値であることを表す。
【０５４１】
【数１９８】
2019198815.tif 000200
【０５４２】
（性質2)関数DのLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
【０５４３】
【数１９９】
2019198815.tif 000201
【０５４４】
ここで、ヘシアン行列KD, MD (KD∈Rm×m, MD∈Rm×m)は、正定値行列である。また、ヘシアン行列HD(w)との間に以下の関係が成り立つ。
【０５４５】
【数２００】
2019198815.tif 000202
【０５４６】
次に、ブレグマンダイバージェンスを用いて、リゾルヴェント作用素、ケーリー作用素を一般化する。一般化したリゾルヴェント作用素、ケーリー作用素をそれぞれブレグマンリゾルヴェント作用素、ブレグマンケーリー作用素という。なお、ブレグマンリゾルヴェント作用素については参考非特許文献２に記載がある。
（参考非特許文献２：H. H. Bauschke, J. M. Borwein, and P. L. Combettes, “Bregman Monotone Optimization Algorithms”, SIAM Journal on Control and Optimization, Vol.42, Issue 2, pp.596-636, 2003.）
ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnは、次式で与えられる。
【０５４７】
【数２０１】
2019198815.tif 000203
【０５４８】
なお、以下のように関数Dを二乗したL2ノルムを用いて定義すると、ブレグマンダイバージェンスBはユークリッド距離に対応し、ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnはそれぞれリゾルヴェント作用素Ωn、ケーリー作用素Ψnに対応する。具体的に説明する。関数Dの劣微分は以下のようになる。
【０５４９】
【数２０２】
2019198815.tif 000204
【０５５０】
関数Dの劣微分をブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnにそれぞれ代入すると、リゾルヴェント作用素Ωn、ケーリー作用素Ψnが得られる。
【０５５１】
【数２０３】
2019198815.tif 000205
【０５５２】
《２：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の収束率》
ここでは、ブレグマンリゾルヴェント作用素、ブレグマンケーリー作用素の収束率に関して、2つのケースについて説明する。
［ケース1］：関数G1は、狭義凸関数である、すなわち、強凸(SC)かつリプシッツ平滑(LS)である。
【０５５３】
このとき、先述した通り、以下の性質が成り立つ。
（性質1）2次のテーラー展開を用いると、関数G1に対して、点wの周りにおいて以下の近似式が成り立つ。
【０５５４】
【数２０４】
2019198815.tif 000206
【０５５５】
（性質2)関数G1のLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
【０５５６】
【数２０５】
2019198815.tif 000207
【０５５７】
ここで、ヘシアン行列HG_1(w), KG_1, MG_1は、以下の関係をもつ。
【０５５８】
【数２０６】
2019198815.tif 000208
【０５５９】
この2つの性質を用いて、以下の定理1と定理2が証明できる。
（定理1）関数G1がSCかつLSである場合、ブレグマンレゾルヴェント作用素R1は以下の収束率をもつ。
【０５６０】
【数２０７】
2019198815.tif 000209
【０５６１】
式(4-8)に含まれる係数σmax,1, σmin,1は次式で与えられる。ここで、Λmaxは最大固有値、 Λminは最小固有値を表す。
【０５６２】
【数２０８】
2019198815.tif 000210
【０５６３】
なお、狭義凸関数Dとして、以下の条件を満たすものを用いる。
【０５６４】
【数２０９】
2019198815.tif 000211
【０５６５】
（定理2）関数G1がSCかつLSである場合、ブレグマンケーリー作用素C1は以下の収束率をもつ。
【０５６６】
【数２１０】
2019198815.tif 000212
【０５６７】
式(4-12)に含まれる係数η1は次式で与えられる。
【０５６８】
【数２１１】
2019198815.tif 000213
【０５６９】
係数σmax,1, σmin,1は式(4-9)、式(4-10)で与えられるものである。
［ケース2］：関数G1, G2は、いずれも狭義凸関数である、すなわち、いずれも強凸(SC)かつリプシッツ平滑(LS)である。
【０５７０】
関数G1については、式(4-5)〜(4-7)で表される性質1及び性質2が成り立つ。同様に、関数G2については、式(4-14)〜(4-16)で表される性質1及び性質2が成り立つ。
（性質1）2次のテーラー展開を用いると、関数G2に対して、点wの周りにおいて以下の近似式が成り立つ。
【０５７１】
【数２１２】
2019198815.tif 000214
【０５７２】
（性質2)関数G2のLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
【０５７３】
【数２１３】
2019198815.tif 000215
【０５７４】
ここで、ヘシアン行列HG_2(w), KG_2, MG_2は、以下の関係をもつ。
【０５７５】
【数２１４】
2019198815.tif 000216
【０５７６】
関数G1について成り立つ定理1、定理2と同様の定理が、関数G2についても成り立つ。
（定理3）関数G2がSCかつLSである場合、ブレグマンレゾルヴェント作用素R2は以下の収束率をもつ。
【０５７７】
【数２１５】
2019198815.tif 000217
【０５７８】
式(4-17)に含まれる係数σmax,2, σmin,2は次式で与えられる。
【０５７９】
【数２１６】
2019198815.tif 000218
【０５８０】
なお、狭義凸関数Dとして、以下の条件を満たすものを用いる。
【０５８１】
【数２１７】
2019198815.tif 000219
【０５８２】
（定理4）関数G2がSCかつLSである場合、ブレグマンケーリー作用素C2は以下の収束率をもつ。
【０５８３】
【数２１８】
2019198815.tif 000220
【０５８４】
式(4-20)に含まれる係数η2は次式で与えられる。
【０５８５】
【数２１９】
2019198815.tif 000221
【０５８６】
係数σmax,2, σmin,2は式(4-18)、式(4-19)で与えられるものである。
《３：一般化P-R型単調作用素分割、一般化D-R型単調作用素分割の変数更新則と収束率》
ブレグマンリゾルヴェント作用素、ブレグマンケーリー作用素を用いて、式(1-2)を変形することにより、P-R型の単調作用素分割とD-R型の単調作用素分割を導出する。ここで説明するP-R型の単調作用素分割とD-R型の単調作用素分割は、ブレグマンダイバージェンスを用いたP-R型の単調作用素分割、D-R型の単調作用素分割の一般化に相当する。以下、それぞれ一般化P-R型単調作用素分割、一般化D-R型単調作用素分割ということにする。
［一般化P-R型単調作用素分割］
式(1-2)を以下のように変形していく。
【０５８７】
【数２２０】
2019198815.tif 000222
【０５８８】
ここで、以下の関係を持つ、w(w∈Rm)の補助変数z(z∈Rm)を導入する。
【０５８９】
【数２２１】
2019198815.tif 000223
【０５９０】
変数zを用いてさらに変形していく。
【０５９１】
【数２２２】
2019198815.tif 000224
【０５９２】
これより、以下の通り、一般化P-R型単調作用素分割が得られる。
【０５９３】
【数２２３】
2019198815.tif 000225
【０５９４】
式(4-22)と式(3-1)から、式(3-1)のケーリー作用素をブレグマンケーリー作用素に置き換えたものが式(4-22)になっていることがわかる。
【０５９５】
一般化P-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-22)を分解することにより得られる。
【０５９６】
【数２２４】
2019198815.tif 000226
【０５９７】
式(4-23)の演算を具体化する。つまり、以下のように変形する。
【０５９８】
【数２２５】
2019198815.tif 000227
【０５９９】
さらに積分形にすることにより、以下を得る。
【０６００】
【数２２６】
2019198815.tif 000228
【０６０１】
式(4-25)の演算についても同様に具体化すると、以下が得られる。
【０６０２】
【数２２７】
2019198815.tif 000229
【０６０３】
次に、一般化P-R型単調作用素分割の収束率について説明する。ケース1、ケース2に場合分けして、収束率を導出する。まず、ケース1について説明する。ケース1については、ブレグマンケーリー作用素C1の非拡大性しか仮定できない（つまり、定理2は成り立つが、定理4は成り立たない）。したがって、式(4-23)〜(4-26)より、ztの収束率は以下の不等式で表される。
【０６０４】
【数２２８】
2019198815.tif 000230
【０６０５】
式(4-29)より、ztとzの停留点z*との誤差は以下のように評価できる。
【０６０６】
【数２２９】
2019198815.tif 000231
【０６０７】
同様に、zt+1とzの停留点z*との誤差は以下のように評価できる。
【０６０８】
【数２３０】
2019198815.tif 000232
【０６０９】
式(4-30)と式(4-31)より、以下の関係を得る。
【０６１０】
【数２３１】
2019198815.tif 000233
【０６１１】
よって、t回の更新を経たときの誤差（収束率）は以下で表される。
【０６１２】
【数２３２】
2019198815.tif 000234
【０６１３】
次に、ケース2について説明する。ケース2については、ブレグマンケーリー作用素C1,C2の非拡大性を担保できる（つまり、定理2、定理4のいずれも成り立つ）。したがって、式(4-23)〜(4-26)より、ztの収束率は以下の不等式で表される。
【０６１４】
【数２３３】
2019198815.tif 000235
【０６１５】
ケース1と同様にして、以下の関係を得る。
【０６１６】
【数２３４】
2019198815.tif 000236
【０６１７】
式(4-33)、式(4-36)からわかるように、ケース1、ケース2いずれの場合も、ηiを小さくすることができれば、収束率を高くすることができる。
［一般化D-R型単調作用素分割］
一般化D-R型単調作用素分割は式(4-22)に平均化作用素を加えることで得られる。
【０６１８】
【数２３５】
2019198815.tif 000237
【０６１９】
式(4-37)と式(3-2)から、式(3-2)のケーリー作用素をブレグマンケーリー作用素に置き換えたものが式(4-37)になっていることがわかる。
【０６２０】
一般化D-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-37)を分解することにより得られる。
【０６２１】
【数２３６】
2019198815.tif 000238
【０６２２】
次に、一般化D-R型単調作用素分割の収束率について説明する。ケース1、ケース2に場合分けして、収束率を導出する。まず、ケース1について説明する。ケース1については、ブレグマンケーリー作用素C1の非拡大性しか仮定できない（つまり、定理2は成り立つが、定理4は成り立たない）。したがって、式(4-38)〜(4-41)より、ztの収束率は以下の不等式で表される。
【０６２３】
【数２３７】
2019198815.tif 000239
【０６２４】
よって、t回の更新を経たときの誤差（収束率）は以下で表される。
【０６２５】
【数２３８】
2019198815.tif 000240
【０６２６】
次に、ケース2について説明する。ケース2については、ブレグマンケーリー作用素C1,C2の非拡大性を担保できる（つまり、定理2、定理4のいずれも成り立つ）。したがって、式(4-38)〜(4-41)より、ztの収束率は以下の不等式で表される。
【０６２７】
【数２３９】
2019198815.tif 000241
【０６２８】
式(4-43)及び式(4-45)からわかるように、ケース1、ケース2いずれの場合も、ηiを小さくすることができれば、αを1に近づけていくことにより、収束率を高くすることができる。なお、αを1に近づけていくということは、一般化D-R型単調作用素分割を一般化P-R型単調作用素分割に近づけていくことを意味する。
《４：高収束率を得るためのブレグマンダイバージェンス設計》
一般化P-R型単調作用素分割や一般化D-R型単調作用素分割による変数更新則を用いることにより、最適解を求めることができる。ここでは、より高速に最適解を求めることができるような、ブレグマンダイバージェンスの設計（関数Dの設計）について説明する。具体的には、2つの設計方法について説明する。
【０６２９】
まず、これまでの議論で得られた結果についてまとめる。ケース1、ケース2いずれの場合も、式(4-13)で与えられるη1、式(4-21)で与えられるη2を0に近づけることにより、一般化P-R型単調作用素分割の変数更新則、一般化D-R型単調作用素分割の変数更新則いずれであっても高い収束率で最適解に収束する。
【０６３０】
【数２４０】
2019198815.tif 000242
【０６３１】
このηiを0に近づけることは、式(4-9)、式(4-10)、式(4-18)、式(4-19)で与えられる固有値σmax,i, σmin,iを1に近づけることで実現できる。最大固有値σmax,i、最小固有値σmin,iとも1に近づけることは、固有値分布が平滑になることに対応する。
【０６３２】
【数２４１】
2019198815.tif 000243
【０６３３】
固有値を1に近づけるためには、関数Dのヘシアン行列HDの逆行列が関数Giのヘシアン行列HG_iの逆行列となるように設計するとよい。
【０６３４】
【数２４２】
2019198815.tif 000244
【０６３５】
関数Giは式(4-5)、式(4-14)の近似式により表現されることから、関数Dを次式のような2次式で表現し、ヘシアン行列HDを適切に設計することで、式(4-47)を実現できる。
【０６３６】
【数２４３】
2019198815.tif 000245
【０６３７】
式(4-48)をブレグマンダイバージェンスの定義式である式(4-1)に代入すると以下を得る。
【０６３８】
【数２４４】
2019198815.tif 000246
【０６３９】
［ニュートン法に従うブレグマンダイバージェンス設計］
式(4-49)に従いブレグマンダイバージェンスを設計する際、式(4-47)を最も忠実に満たすようにするには、ヘシアン行列HDを式(4-50)に従うように設計するとよい。なお、この設計は、二次収束性の最適化法としてよく知られているニュートン法に通じるものである。式(4-50)の代わりに、BFGS法などのヘシアン行列の近似計算法を用いてもよい。
【０６４０】
【数２４５】
2019198815.tif 000247
【０６４１】
なお、実数ε>0は学習のステップサイズを決めるパラメータに相当し、ヘシアン行列HD(2GD)の固有値が0より大きく1以下に収まるように選ぶ必要がある。
【０６４２】
また、式(4-50)では、(case2)において相加平均を用いたが、相加平均の代わりに、相乗平均を用いてもよい。
【０６４３】
【数２４６】
2019198815.tif 000248
【０６４４】
式(4-50)（式(4-50’)）は、ケース1、ケース2に分けてヘシアン行列HDを設計していることを示している。ケース2の場合、関数G1、G2の双方に対して、式(4-47)を満たすようにすることが理想的であるが、実際、このことを担保するのは難しい。そこで、ケース2について、式(4-50)（式(4-50’)）のように設計することにした。この設計が好ましい理由は、ヘシアン行列に関して、以下の数学的性質が成り立つためである。具体的に説明する。まず、ヘシアン行列HDの逆行列を計算する。
【０６４５】
【数２４７】
2019198815.tif 000249
【０６４６】
ここで、式(4-47)式のようにHD-1とHG_iを掛け合わせると、以下のようになる。
【０６４７】
【数２４８】
2019198815.tif 000250
【０６４８】
これらの2つの式は、HG_1とHG_2が近いほど、式(4-47)を満たすようになることを示している。
［加速勾配法に従うブレグマンダイバージェンス設計］
ニュートン法に従うブレグマンダイバージェンス設計を用いた場合、実際の変数更新則では、ヘシアン行列HDの逆行列を計算する必要があるが、この計算には非常に大きなコストがかかる。この計算コストの問題を克服するために、式(4-47)の再現性を多少犠牲にして、ヘシアン行列HDの逆行列の計算コストを下げることにする。このような設計として、加速勾配法に従うブレグマンダイバージェンス設計を説明する。この設計は簡単に説明すると、ヘシアン行列HDを対角行列に制約したうえで、式(4-47)をできるだけ満たすようにヘシアン行列HDを設計するものである。なお、この設計は、超一次収束として知られている加速勾配法に通じるものである。
【０６４９】
加速勾配法を実現するための方法は様々提案されている。例えば、モメンタム法、AdaGrad法、Adam法、RMSProp法などがある。ここでは、RMSProp法を用いた設計について説明する。
【０６５０】
【数２４９】
2019198815.tif 000251
【０６５１】
なお、実数ε>0は学習のステップサイズを決めるパラメータに相当し、ヘシアン行列HD(AGD)の固有値が0より大きく1以下に収まるように選ぶ必要がある。
【０６５２】
また、式(4-51)では、(case2)において相加平均を用いたが、相加平均の代わりに、相乗平均を用いてもよい。
【０６５３】
【数２５０】
2019198815.tif 000252
【０６５４】
また、LG_1とLG_2は基本的には対角行列となることを想定された行列であり、RMSProp法では以下のように設計する。
【０６５５】
【数２５１】
2019198815.tif 000253
【０６５６】
ただし、ヘシアン行列HDの逆行列の計算コストを多少犠牲にしてもよい場合、LG_1, LG_2は必ずしも対角行列である必要はない。非対角成分も用いる場合のRMSProp法では以下のように設計する。
【０６５７】
【数２５２】
2019198815.tif 000254
【０６５８】
《５：エッジコンピューティングにおける合意形成問題への適用》
ここでは、エッジコンピューティングにおける合意形成問題を例として、ブレグマンダイバージェンスを用いて一般化された単調作用素分割を用いた再帰的な変数更新則である変数更新アルゴリズムについて説明する。
【０６５９】
式(3-3)〜式(3-6)に対応する再帰的な変数更新則は以下のようになる。
【０６６０】
【数２５３】
2019198815.tif 000255
【０６６１】
式(4-54)が一般化P-R型単調作用素分割に、式(4-55)が一般化D-R型単調作用素分割に対応する。
【０６６２】
なお、変数更新則の導出に際して、ブレグマンケーリー作用素C2が以下の式を満たすことを用いた。その証明については省略するが、非特許文献４に示された証明戦略をブレグマンケーリー作用素に適用すれば得られる結果である。
【０６６３】
【数２５４】
2019198815.tif 000256
【０６６４】
また、式(4-48)を用いる際の関数Dの劣微分とその逆作用素は以下のようになる。
【０６６５】
【数２５５】
2019198815.tif 000257
【０６６６】
ここで、ヘシアン行列HD(z)とその逆行列HD-1(z)は、いずれも以下のようなブロック対角化行列となる。
【０６６７】
【数２５６】
2019198815.tif 000258
【０６６８】
以下、式(4-52)〜式(4-55)の再帰的な変数更新則をノードごとに非同期で変数を更新できるようにしたアルゴリズムについて説明する。式(4-52)には潜在変数pと双対変数wの更新が含まれており、潜在変数pと双対変数wの取り扱いに関して以下説明する2つの方法が考えられる。
［方法1］
この方法は、従来法と同様、罰則項を用いてpの最適化を行った後、wの最適化を行う。
【０６６９】
まず、罰則項を用いて、pの最適化を行う。
【０６７０】
【数２５７】
2019198815.tif 000259
【０６７１】
次にwの最適化を行う。
【０６７２】
【数２５８】
2019198815.tif 000260
【０６７３】
式(4-61’)の結果を式(4-53)に代入すると、以下の双対変数λの更新則を得る。
【０６７４】
【数２５９】
2019198815.tif 000261
【０６７５】
この式は双対変数wを用いなくても双対変数λが得られることを示している。
【０６７６】
式(4-52)〜(4-55)の変数更新則を具体的に表わすと以下のようになる。
【０６７７】
【数２６０】
2019198815.tif 000262
【０６７８】
なお、式(4-54)、式(4-55)については、式(4-63)、式(4-64)、式(4-65)に分けた。これは、ノードごとに非同期で変数を更新できるようにするためである。
【０６７９】
この更新則をノードごとに変数を更新できるようにすると、図１２に示すアルゴリズムが得られる。なお、このアルゴリズムにおけるヘシアン行列HDは、式(4-50)や式(4-51)を用いて設計するのが好ましい。
［方法2］
この方法は、双対変数wの更新を行い、必要に応じて潜在変数pの更新を行う。
【０６８０】
式(4-52)を解くため、pをwの関数として表現して最適化する。2次のテーラー展開を用いて、関数F1を以下のように近似表現する。
【０６８１】
【数２６１】
2019198815.tif 000263
【０６８２】
これを関数F1*に代入すると、以下のようにpをwの関数とした場合の最適値p(w)が得られる。
【０６８３】
【数２６２】
2019198815.tif 000264
【０６８４】
右辺の括弧内をpに関して微分し、それが0となる点（つまり、最適点）を探すと、以下のようになる。
【０６８５】
【数２６３】
2019198815.tif 000265
【０６８６】
これを式(4-52)に代入すると、wの更新式を得る。
【０６８７】
【数２６４】
2019198815.tif 000266
【０６８８】
右辺の括弧内をwに関して微分し、それが0となる点（つまり、最適点）を探すと、以下のようになる。
【０６８９】
【数２６５】
2019198815.tif 000267
【０６９０】
式(4-66)より、pはwの関数として表現されているので、pの更新式は以下のようになる。
【０６９１】
【数２６６】
2019198815.tif 000268
【０６９２】
式(4-53)に式(4-67)を代入することにより、以下の更新式を得る。
【０６９３】
【数２６７】
2019198815.tif 000269
【０６９４】
式(4-68)、式(4-69)、式(4-54)、式(4-55)より変数更新則を具体的に表わすと以下のようになる。
【０６９５】
【数２６８】
2019198815.tif 000270
【０６９６】
この更新則をノードごとに変数を更新できるようにすると、図１３に示すアルゴリズムが得られる。なお、このアルゴリズムにおけるヘシアン行列HDは、式(4-50)や式(4-51)を用いて設計するのが好ましい。
【０６９７】
図１２のアルゴリズムと図１３のアルゴリズムを比較すると、ノード間で交換される変数に違いがある。つまり、図１２のアルゴリズムでは、潜在変数と双対変数の変形を交換しているのに対して、図１３のアルゴリズムでは双対変数の変形のみ交換している。双対変数の変形のみ交換すればよくなったことにより、図１３のアルゴリズムの方が情報の秘匿化/暗号化という点において図１２のアルゴリズムよりも優れていると言える。
《６：実験及びその結果》
以上説明した変数更新則の効果について確認するため、収束率に関する実験を行った。実験では、図１４のような2種類のグラフ構成をもった分散計算器（エッジコンピューティングシステム）を用いた。分散計算器の各ノードにはランダムに生成した異なるデータセットを配置し、潜在変数の収束率を計測した。
【０６９８】
コスト関数F1には、以下のものを用いた。
【０６９９】
【数２６９】
2019198815.tif 000271
【０７００】
ここで、vi,uとsi,uはノードiにおける入力データと教師データの組、piはノードiにおける潜在変数である。
【０７０１】
また、潜在変数の誤差を測定する尺度には以下のものを用いた。
【０７０２】
【数２７０】
2019198815.tif 000272
【０７０３】
ここで、p*は潜在変数pの最適値、pitはt回の更新で得られたノードiにおける潜在変数の値、m=p’Vである。
【０７０４】
図１５に実験結果を示す。B-MOS(GD)は従来の方法（図１１のアルゴリズム）、B-MOS(AGD)は加速勾配法(AGD)によりヘシアン行列を設計した場合の本願の方法（図１３のアルゴリズム）、B-MOS(2GD)はニュートン法によりヘシアン行列を設計した場合の本願の方法（図１３のアルゴリズム）を示す。なお、D-ADMMはB-MOS(GD)とは異なる別の従来の方法を示す。この図からわかるように、いずれのグラフ構造においても、本願の方法の方が、従来の方法と比較して収束率が高くなる。特に、ニュートン法に従ってヘシアン行列を設計した場合に、最も高い収束率が得られる。
《７：微分を用いた表現》
《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》の冒頭部において、関数Dは微分可能な狭義凸関数であると仮定したことから、関数Dの劣微分を関数Dの微分としても《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》から《５：エッジコンピューティングにおける合意形成問題への適用》までの議論は成り立つ。具体的には、《1：ブレグマンレゾルヴェント作用素とブレグマンケーリー作用素の定義》から《５：エッジコンピューティングにおける合意形成問題への適用》までの説明における“関数Dの劣微分”との記載を“関数Dの微分”とした説明が成り立つ。以下、主たる式に関して劣微分を微分で置き換えた式を示す。
【０７０５】
関数Dの微分を用いた場合、ブレグマンダイバージェンスBは、以下のように定義される。
【０７０６】
【数２７１】
2019198815.tif 000273
【０７０７】
ここで、∇は関数を微分する演算を表す。
【０７０８】
また、狭義凸関数Dの（性質1）、（性質2）は、以下のように表現できる。
（性質1）2次のテーラー展開を用いると、関数Dに対して、点wの周りにおいて以下の近似式が成り立つ。
【０７０９】
【数２７２】
2019198815.tif 000274
【０７１０】
（性質2)関数DのLS（上界）とSC（下界）は、任意のベクトルh∈Rmを用いて、以下のように表現できる。
【０７１１】
【数２７３】
2019198815.tif 000275
【０７１２】
ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnは、次式で与えられる。
【０７１３】
【数２７４】
2019198815.tif 000276
【０７１４】
関数DをL2ノルムの二乗を用いて定義する場合、関数Dと関数Dの微分は以下のようになる。
【０７１５】
【数２７５】
2019198815.tif 000277
【０７１６】
この場合、ブレグマンリゾルヴェント作用素Rnとブレグマンケーリー作用素Cnは、劣微分を用いた場合と同様、リゾルヴェント作用素Ωn、ケーリー作用素Ψnとなる。
【０７１７】
【数２７６】
2019198815.tif 000278
【０７１８】
一般化P-R型単調作用素分割は、劣微分の場合と同様、次式のようになる。
【０７１９】
【数２７７】
2019198815.tif 000279
【０７２０】
そして、一般化P-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-22)*を分解することにより得られる。
【０７２１】
【数２７８】
2019198815.tif 000280
【０７２２】
また、式(4-23)*を変形すると、次式が得られる。
【０７２３】
【数２７９】
2019198815.tif 000281
【０７２４】
式(4-25)*も同様に変形すると、次式が得られる。
【０７２５】
【数２８０】
2019198815.tif 000282
【０７２６】
一般化D-R型単調作用素分割も、劣微分の場合と同様、次式のようになる。
【０７２７】
【数２８１】
2019198815.tif 000283
【０７２８】
そして、一般化D-R型単調作用素分割の変数更新則は、w(∈Rm)の補助変数x, y, z(x∈Rm, y∈Rm, z∈Rm)を用いて式(4-37)*を分解することにより得られる。
【０７２９】
【数２８２】
2019198815.tif 000284
【０７３０】
劣微分の場合と同様、関数Dを式(4-48)の2次式で表現し、ブレグマンダイバージェンスの定義式である式(4-1)*に代入することにより、以下を得る。
【０７３１】
【数２８３】
2019198815.tif 000285
【０７３２】
ただし、式(4-48)における関数Dの更新は、毎ステップ行われるわけではない。具体的には、関数Dが強凸性であることを満たすため、以下の式で表される条件を満たす場合に限り、任意のタイミングで関数Dの微分∇Dの更新が行われる。したがって、当該条件が満たされない場合には、関数Dの微分∇Dの更新は行わない。
【０７３３】
【数２８４】
2019198815.tif 000286
【０７３４】
エッジコンピューティングにおける合意形成問題へ適用した場合における、式(3-3)〜式(3-6)に対応する再帰的な変数更新則は以下のようになる。
【０７３５】
【数２８５】
2019198815.tif 000287
【０７３６】
なお、変数更新則の導出に際して、ブレグマンケーリー作用素C2が以下の式を満たすことを用いた。
【０７３７】
【数２８６】
2019198815.tif 000288
【０７３８】
また、式(4-48)を用いる際の関数Dの微分とその逆作用素は以下のようになる。
【０７３９】
【数２８７】
2019198815.tif 000289
【０７４０】
《８：高次凸性を用いたブレグマンダイバージェンス設計》
《４：高収束率を得るためのブレグマンダイバージェンス設計》で説明した２つのブレグマンダイバージェンス設計手法では、ブレグマンダイバージェンスの計量を決める関数Dを２次式に限定したときにどのように設計すればよいのかについて論じた。ここでは、２次以上の高次凸性を用いて、更なる高速収束を可能にする関数Dの設計について説明する。なお、以下では関数Dの微分∇Dの設計について説明するが、変数更新の際に使用するのは∇Dであるので、∇Dの設計に関して説明しても一般性を失うことはない。
【０７４１】
式(4-48)及び式(4-49)*において暗に仮定されていたことであるが、関数Dの設計により停留点を変更しないようにするために、関数Dは∇D(0)=0を満たすこと、かつ、関数Dは微分可能な狭義凸関数であることの２点に着目する。関数Giは微分可能であると仮定する。つまり、関数Giの微分∇Giは存在するものと仮定する。なお、関数Giそのものが微分可能でなくても、例えば平滑化などの処理により関数Giを微分可能な関数とすることができるため、関数Giは微分可能であると仮定しても問題ない。
【０７４２】
このとき、次式で表される条件のもと、∇Dを更新することにより、関数Giが２次以上の凸性を含む場合に高速収束が見込める。
【０７４３】
【数２８８】
2019198815.tif 000290
【０７４４】
ただし、∇Dの更新は、関数Dが強凸性であることを満たすため、以下の式で表される条件を満たす場合に限り、任意のタイミングで行われる。したがって、当該条件が満たされない場合には、∇Dの更新は行わない。
【０７４５】
【数２８９】
2019198815.tif 000291
【０７４６】
実用上、複数の高次（３次以上）の凸性の和として関数Giを表現する場合（例えば、高次のテーラー展開を用いて関数Giを狭義凸関数として表現する場合）には、解析的にwの最適解を得ることが難しいことが多い。このような場合には、和を用いる代わりに、単一の高次項のみを用いて関数Dを表現するのが一つの有用な実装法となる。この場合、次式により関数Dを表現すればよい。
【０７４７】
【数２９０】
2019198815.tif 000292
【０７４８】
＜第３実施形態＞
以下、図１６〜図１７を参照して潜在変数学習装置１００を説明する。図１６は、潜在変数学習装置１００の構成を示すブロック図である。図１７は、潜在変数学習装置１００の動作を示すフローチャートである。図１６に示すように潜在変数学習装置１００は、モデル学習部１２０と、記録部１９０を含む。
【０７４９】
潜在変数学習装置１００は、学習データを用いて、機械学習の対象となるモデルの潜在変数w∈Rm（mは1以上の整数）を学習する。ここで、モデルとは、入力データを入力とし、出力データを出力とする関数のことであり、学習データとは、モデルの潜在変数の学習に用いる入力データ、または、モデルの潜在変数の学習に用いる入力データと出力データの組のことをいう。なお、入力データと出力データの組を学習データとする場合、出力データのことを教師データということもある。
【０７５０】
図１７に従い潜在変数学習装置１００の動作について説明する。
【０７５１】
Ｓ１２０において、モデル学習部１２０は、学習データを用いて、所定の手順により潜在変数wを学習する。以下、その手順について、具体的に説明する。
（手順１）
ここでは、ブレグマンダイバージェンスを用いた学習手順について説明する。
【０７５２】
まず、モデル学習部１２０は、学習データを用いて、潜在変数wを学習する際に用いるセットアップデータを計算する。例えば、学習データを用いて計算される、潜在変数wを最適化するためのコスト関数G(w):Rm→R（ただし、G(w)=ΣiGi(w)、関数Gi(w)（Nを2以上の整数とし、iは1≦i≦Nを満たす整数とする（つまり、iはインデックスである））は閉真凸関数）がその一例である。
【０７５３】
次に、関数D（ただし、D:Rm→Rは狭義凸関数）を用いて定義されるブレグマンダイバージェンスBD(w1||w2)=D(w1)-D(w2)-<∂D(w2),w1- w2>（w1, w2∈Rm）を用いて、モデル学習部１２０は、コスト関数G(w)を最小化するwの停留点w*∈RmとのブレグマンダイバージェンスBD（BD(w||w*)またはBD(w*||w)）が0に近づくように、潜在変数wを学習する。なお、関数Dは、任意に設計可能な狭義凸関数である。また、停留点w*のことを不動点w*ともいう。
（手順２）
ここでは、＜技術的背景＞で説明したように、単調作用素分割を用いて構成される潜在変数の更新規則を用いた学習手順について説明する。＜技術的背景＞では、N=2の場合について詳細に説明したが、単調作用素分割を用いて潜在変数の更新規則を構成できる任意のNについて、以下説明するような学習手順を構成することができる。例えば、N=3の場合についても、N=2の場合と同様、単調作用素分割の変形が可能であることが数学的に証明できるので、同様の学習手順を構成することができる。
【０７５４】
まず、モデル学習部１２０は、学習データを用いて、潜在変数wを学習する際に用いるセットアップデータを計算する。例えば、上述のコスト関数G(w)の他、関数Dと関数Giを用いて定義されるブレグマンリゾルヴェント作用素Ri(1≦i≦N)、ブレグマンリゾルヴェント作用素Riを用いて定義されるブレグマンケーリー作用素Ci(1≦i≦N)をセットアップデータとして計算する。
【０７５５】
次に、ブレグマンリゾルヴェント作用素Ri(1≦i≦N)とブレグマンケーリー作用素Ci(1≦i≦N)を用いて、潜在変数wの値を再帰的に計算する。具体的には、更新回数のカウントに用いる変数（以下、カウンタともいう）をtとし、モデル学習部１２０は、ブレグマンリゾルヴェント作用素Ri(1≦i≦N)とブレグマンケーリー作用素Ci(1≦i≦N)を用いて、潜在変数wのt+1回目の更新結果であるwt+1を再帰的に計算する。
【０７５６】
なお、カウンタtは、0以上の整数値をとることになる。
【０７５７】
N=2の場合における、一般化P-R型単調作用素分割及び一般化D-R型単調作用素分割を用いて構成される潜在変数の更新規則を用いた学習手順を実行するモデル学習部１２０について説明する。以下、図１８〜図１９を参照してモデル学習部１２０について説明する。図１８は、モデル学習部１２０の構成を示すブロック図である。図１９は、モデル学習部１２０の動作を示すフローチャートである。図１８に示すようにモデル学習部１２０は、初期化部１２１と、潜在変数計算部１２２と、第１補助変数計算部１２３と、第２補助変数計算部１２４と、第３補助変数計算部１２５と、カウンタ更新部１２６と、終了条件判定部１２７を含む。
【０７５８】
図１９に従いモデル学習部１２０の動作について説明する。ここでは、潜在変数wの補助変数x, y, z∈Rmを用いる。
【０７５９】
Ｓ１２１において、初期化部１２１は、カウンタtを初期化する。具体的には、t=0とする。また、初期化部１２１は、セットアップデータを計算する。
【０７６０】
Ｓ１２２において、潜在変数計算部１２２は、式(5-1)により、補助変数zのt回目の更新結果であるztから潜在変数wのt+1回目の更新結果であるwt+1を計算する。
【０７６１】
Ｓ１２３において、第１補助変数計算部１２３は、式(5-2)により、Ｓ１２２で用いたztとＳ１２２で計算したwt+1から補助変数xのt+1回目の更新結果であるxt+1を計算する。
【０７６２】
Ｓ１２４において、第２補助変数計算部１２４は、式(5-3)により、Ｓ１２３で計算したxt+1から補助変数yのt+1回目の更新結果であるyt+1を計算する。
【０７６３】
Ｓ１２５において、第３補助変数計算部１２５は、補助変数zのt+1回目の更新結果であるzt+1を計算する。具体的に説明する。一般化P-R型単調作用素分割を用いる場合、第３補助変数計算部１２５は、式(5-4)により、Ｓ１２３で計算したxt+1とＳ１２４で計算したyt+1から補助変数zのt+1回目の更新結果であるzt+1を計算する。また、一般化D-R型単調作用素分割を用いる場合、第３補助変数計算部１２５は、式(5-5)により、Ｓ１２２で用いたztとＳ１２３で計算したxt+1とＳ１２４で計算したyt+1から補助変数zのt+1回目の更新結果であるzt+1を計算する（ただし、αは0<α<1を満たす実数である）。
【０７６４】
Ｓ１２６において、カウンタ更新部１２６は、カウンタtを1だけインクリメントする。具体的には、t←t+1とする。
【０７６５】
Ｓ１２７において、終了条件判定部１２７は、カウンタtが所定の更新回数τ（τは1以上の整数とする）に達した場合（つまり、t=τとなり、終了条件が満たされた場合）は、そのときの潜在変数wの値wτを出力して、処理を終了する。それ以外の場合、Ｓ１２２の処理に戻る。つまり、モデル学習部１２０は、Ｓ１２２〜Ｓ１２５の計算を繰り返す。なお、Ｓ１２５で計算したzt+1は、次の繰り返し計算におけるＳ１２２とＳ１２３で用いられる。
【０７６６】
【数２９１】
2019198815.tif 000293
【０７６７】
《高収束率を実現するための関数Dの条件》
コスト関数G(w)を最小化するwの停留点w*への収束率を高くするためには、関数Dを以下の条件を満たす関数にすればよい。
（条件）関数Dは、そのヘシアン行列が関数Gi(w)のヘシアン行列の逆行列に近くなるような関数である。
【０７６８】
なお、上記条件は、“関数Dは、そのヘシアン行列の逆行列と関数Gi(w)のヘシアン行列の積が単位行列に近くなるような関数である”ということもできる。
【０７６９】
N=2の場合、＜技術的背景＞で説明したように、ニュートン法や加速勾配法に従って、関数Dのヘシアン行列を以下のように計算すればよい。
［ケース1］：関数G1は、狭義凸関数である、すなわち、強凸(SC)かつリプシッツ平滑(LS)である場合。
【０７７０】
【数２９２】
2019198815.tif 000294
【０７７１】
（ただし、ε>0は実数）
なお、実数εは、ヘシアン行列HDの固有値が0より大きく1以下に収まるように選ばれる。
［ケース2］：関数G1, G2は、いずれも狭義凸関数である、すなわち、いずれも強凸(SC)かつリプシッツ平滑(LS)である場合。
【０７７２】
【数２９３】
2019198815.tif 000295
【０７７３】
（ただし、ε>0は実数）
なお、実数εは、ヘシアン行列HDの固有値が0より大きく1以下に収まるように選ばれる。
【０７７４】
式(5-6)及び式(5-8)がニュートン法に従った場合であり、式(5-7)及び式(5-9)が加速勾配法に従った場合である。なお、行列LG_1, LG_2は式(5-10)及び式(5-11)により与えられる行列である。
【０７７５】
【数２９４】
2019198815.tif 000296
【０７７６】
または、行列LG_1, LG_2は式(5-12)及び式(5-13)により与えられる行列である。
【０７７７】
【数２９５】
2019198815.tif 000297
【０７７８】
式(5-10)及び式(5-12)の行列LG_1は、関数G1(w)の勾配を用いて計算される行列である。また、式(5-11)及び式(5-13)の行列LG_2は、関数G2(w)の勾配を用いて計算される行列である。
【０７７９】
なお、［ケース2］における式(5-8)及び式(5-9)の代わりに、次式のような相乗平均を用いてもよい。
【０７８０】
【数２９６】
2019198815.tif 000298
【０７８１】
なお、先のケース1やケース2の説明では、関数G1(w)や関数G2(w)は狭義凸関数であるとしたが、必ずしも数学的に厳密に狭義凸関数である必要はない。つまり、関数G1(w)や関数G2(w)を狭義凸関数であるとみなして扱ってよい場合についても、式(5-6)〜式(5-9)により関数Dのヘシアン行列を計算することができる。より詳しく言えば、次のようになる。
［ケース1］：関数G1が、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）、または、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）と仮定できる場合。
【０７８２】
この場合は、式(5-6)や式(5-7)により、関数Dのヘシアン行列を計算することができる。
［ケース2］：関数G1, G2のそれぞれが、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）、または、狭義凸関数である（強凸(SC)かつリプシッツ平滑(LS)である）と仮定できる場合。
【０７８３】
この場合は、式(5-8)や式(5-9)により、関数Dのヘシアン行列を計算することができる。
【０７８４】
上記第３実施形態の説明では、劣微分を用いて説明したが、＜技術的背景＞で説明したように劣微分の代わりに微分を用いてもよい。この場合、式(5-1)〜式(5-5)の代わりに次式を用いればよい。
【０７８５】
【数２９７】
2019198815.tif 000299
【０７８６】
また、微分を用いる場合は、次式で表される条件のもと、∇Dを更新するようにしてもよい。
【０７８７】
【数２９８】
2019198815.tif 000300
【０７８８】
ただし、∇Dの更新は、以下の式で表される条件を満たす場合に限り、任意のタイミングで行うものとする。
【０７８９】
【数２９９】
2019198815.tif 000301
【０７９０】
本実施形態の発明によれば、機械学習の対象となるモデルの潜在変数を高速に学習することができる。本実施形態の発明によれば、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づき、変数更新則を構成することにより、停留点（最適解）への収束が高速になるように、潜在変数を更新することができる。また、ブレグマンダイバージェンスの定義に用いる凸関数を適切に構成することにより、停留点への収束が高速になるような、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づく変数更新則を構成することができる。
【０７９１】
＜第４実施形態＞
ここでは、＜技術的背景＞の《５：エッジコンピューティングにおける合意形成問題への適用》で説明した2つの変数更新アルゴリズム（図１２及び図１３のアルゴリズム）に対応する実施形態について説明する。
【０７９２】
以下、図２０を参照して潜在変数学習システム２０を説明する。図２０は、潜在変数学習システム２０の構成を示すブロック図である。図２０に示すように潜在変数学習システム２０は、V個（Vは1以上の整数）の潜在変数学習装置２００1, …, ２００Vを含む。潜在変数学習装置２００i(i∈v={1,…,V}）は、先のエッジコンピューティングにおける合意形成問題に関する説明におけるノードに対応するものである。
【０７９３】
また、各潜在変数学習装置２００iはネットワーク９００に接続しており、必要に応じて潜在変数学習装置２００j(j≠i)と通信する。ネットワーク９００には、例えば、インターネットを用いることができる。
【０７９４】
以下、図２１を参照して潜在変数学習装置２００を説明する。図２１は、潜在変数学習装置２００の構成を示すブロック図である。図２１に示すように潜在変数学習装置２００は、モデル学習部２２０と、通信部２８０と、記録部２９０を含む。
【０７９５】
潜在変数学習装置２００iは、学習データを用いて、機械学習の対象となるモデルの潜在変数pi∈Rp’（p’は1以上の整数）を学習する。学習データは、すべての潜在変数学習装置２００iに共通であってもよいし、潜在変数学習装置２００iごとに異なるものであってもよい。
【０７９６】
次に、図２２〜図２３を参照してモデル学習部２２０を説明する。図２２は、モデル学習部２２０の構成を示すブロック図である。図２３は、モデル学習部２２０の動作を示すフローチャートである。図２２に示すようにモデル学習部２２０は、初期化部２２１と、潜在変数計算部２２２と、第１双対変数計算部２２３と、同期用変数更新部２２４と、第２双対変数計算部２２５と、カウンタ更新部２２６と、終了条件判定部２２７を含む。
【０７９７】
図２３に従いモデル学習部２２０の動作について説明する。具体的な説明に入る前に、いくつか記号について説明する。これらの記号は、これまでの議論で用いてきたものであり、以下の説明は、そのまとめに相当するものである。
【０７９８】
v={1,…,V}は、潜在変数学習装置２００群のインデックスの集合を表す。また、N(i)は、潜在変数学習装置２００iと通信をする潜在変数学習装置２００群のインデックスの集合を表す。
【０７９９】
潜在変数pi, pj（ただし、j∈N(i)）に対して、λi|j∈Rp’を潜在変数学習装置２００iに帰属する双対変数、λj|i∈Rp’を潜在変数学習装置２００jに帰属する双対変数とする。また、同様に、潜在変数pi, pj（ただし、j∈N(i)）に対して、zi|j∈Rp’を潜在変数学習装置２００iに帰属する双対変数、zj|i∈Rp’を潜在変数学習装置２００jに帰属する双対変数とする。
【０８００】
関数F1,i(pi):Rp’→Rを、学習データを用いて計算される、潜在変数piを最適化するためのコスト関数（ただし、F1,i(pi)は閉真凸関数）とする。
【０８０１】
Ai|j∈Rp’×p’を次式により与えられるp’×p’の実数行列とする。
【０８０２】
【数３００】
2019198815.tif 000302
【０８０３】
関数Di|j:Rp’→R（ただし、j∈N(i)）を潜在変数学習装置２００iに帰属する狭義凸関数とする。
【０８０４】
なお、ξi|j, ζiを潜在変数学習装置２００j（ただし、j∈N(i)）から送信されたデータを格納するための潜在変数学習装置２００iの変数とする。以下、ξi|j, ζiのことを同期用変数ともいう。また、tを変数の更新回数をカウントするための変数（以下、カウンタともいう）、τ（τは1以上の整数）を所定の更新回数とする。このτは、後述するＳ２２２〜Ｓ２２５の繰り返し計算の回数の上限を表す。
【０８０５】
以降の説明では、Si(i∈v={1,…,V}）は、V個の潜在変数学習装置２００1, …, ２００Vを示すものとする。したがって、潜在変数学習システム２０は、潜在変数学習装置Si(i∈v）を含み、潜在変数学習装置Si(i∈v）は、学習データを用いて、所定の手順により潜在変数piを学習する。以下、図２３を参照してその手順について説明する。
【０８０６】
Ｓ２２１において、初期化部２２１は、カウンタtを初期化する。具体的には、t=0とする。また、初期化部２２１は、セットアップデータを計算する。例えば、コスト関数F1,i(pi)がその一例である。
【０８０７】
Ｓ２２２において、潜在変数計算部２２２は、次式により、双対変数zi|jのt回目の更新結果であるzi|jtと変数ζiのt回目の更新結果であるζitから潜在変数piのt+1回目の更新結果であるpit+1を計算する。
【０８０８】
【数３０１】
2019198815.tif 000303
【０８０９】
ただし、zi|j0及びζi0には適当な初期値が設定されているものとする。また、γ（γ>0）は所定の実数とする。
【０８１０】
Ｓ２２３において、第１双対変数計算部２２３は、j∈N(i)について、次式により、Ｓ２２２で用いたzi|jtとＳ２２２で計算したpit+1から双対変数λi|j（j∈N(i)）のt+1回目の更新結果であるλi|jt+1を計算する。
【０８１１】
【数３０２】
2019198815.tif 000304
【０８１２】
ここで、HD_i|jは関数Di|jのヘシアン行列を表す。つまり、HD_i|j-1はその逆行列である。
【０８１３】
Ｓ２２４において、同期用変数更新部２２４は、通信部２８０を用いて、次式により、潜在変数学習装置Sj(j∈N(i)）の学習により得られる値を変数ξi|j, ζi（j∈N(i)）のt+1回目の更新結果であるξi|jt+1, ζit+1として受信し、変数ξi|j, ζiを更新する。
【０８１４】
【数３０３】
2019198815.tif 000305
【０８１５】
Ｓ２２５において、第２双対変数計算部２２５は、j∈N(i)について、次式により、双対変数zi|j（j∈N(i)）のt+1回目の更新結果であるzi|jt+1を計算する。
【０８１６】
【数３０４】
2019198815.tif 000306
【０８１７】
ここで、αは0<α<1を満たす実数である。
【０８１８】
なお、式(6-1)は一般化P-R型単調作用素分割を用いる場合、式(6-2)は一般化D-R型単調作用素分割を用いる場合に対応する。
【０８１９】
Ｓ２２６において、カウンタ更新部２２６は、カウンタtを1だけインクリメントする。具体的には、t←t+1とする。
【０８２０】
Ｓ２２７において、終了条件判定部２２７は、カウンタtが所定の更新回数τに達した場合（つまり、t=τとなり、終了条件が満たされた場合）は、そのときの潜在変数piの値piτを出力して、処理を終了する。それ以外の場合、Ｓ２２２の処理に戻る。つまり、モデル学習部２２０は、Ｓ２２２〜Ｓ２２５の計算を繰り返す。なお、Ｓ２２５で計算したzi|jt+1は、次の繰り返し計算におけるＳ２２２とＳ２２３で用いられる。
【０８２１】
なお、ヘシアン行列HD_i|jは、式(5-6)〜式(5-9)を用いて設計するのが好ましい。
（変形例１）
上述の手順は、図１２のアルゴリズムに対応するものである。ここでは、図１３のアルゴリズムに対応する手順について説明する。当該手順では、潜在変数を交換する必要がないため、変数ζiを用いない。
【０８２２】
潜在変数学習装置２００は、図２１に示すように、モデル学習部２２０の代わりに、モデル学習部２３０を含む。以下、図２４〜図２５を参照してモデル学習部２３０を説明する。図２４は、モデル学習部２３０の構成を示すブロック図である。図２５は、モデル学習部２３０の動作を示すフローチャートである。図２４に示すようにモデル学習部２３０は、初期化部２３１と、第１双対変数計算部２３２と、潜在変数計算部２３３と、同期用変数更新部２３４と、第２双対変数計算部２３５と、カウンタ更新部２３６と、終了条件判定部２３７を含む。
【０８２３】
図２５に従いモデル学習部２３０の動作について説明する。
【０８２４】
Ｓ２３１において、初期化部２３１は、カウンタtを初期化する。具体的には、t=0とする。また、初期化部２３１は、セットアップデータを計算する。
【０８２５】
Ｓ２３２において、第１双対変数計算部２３２は、j∈N(i)について、次式により、双対変数zi|jのt回目の更新結果であるzi|jtと潜在変数piのt回目の更新結果であるpitから双対変数λi|j（j∈N(i)）のt+1回目の更新結果であるλi|jt+1を計算する。
【０８２６】
【数３０５】
2019198815.tif 000307
【０８２７】
ただし、zi|j0及びpi0には適当な初期値が設定されているものとする。また、HD_i|jは関数Di|jのヘシアン行列、HF_1,iは関数F1,iのヘシアン行列を表す。つまり、HD_i|j-1及びHF_1,i-1はそれらの逆行列である。∂F1,iは関数F1,iの劣微分を表す。
【０８２８】
Ｓ２３３において、潜在変数計算部２３３は、次式により、潜在変数piのt+1回目の更新結果であるpit+1を計算する。
【０８２９】
【数３０６】
2019198815.tif 000308
【０８３０】
ここで、wi|jtは双対変数wi|jのt回目の更新結果を表す。
【０８３１】
Ｓ２３４において、同期用変数更新部２３４は、通信部２８０を用いて、次式により、潜在変数学習装置Sj(j∈N(i)）の学習により得られる値を変数ξi|j（j∈N(i)）のt+1回目の更新結果であるξi|jt+1として受信し、変数ξi|jを更新する。
【０８３２】
【数３０７】
2019198815.tif 000309
【０８３３】
Ｓ２２５において、第２双対変数計算部２２５は、j∈N(i)について、次式により、双対変数zi|j（j∈N(i)）のt+1回目の更新結果であるzi|jt+1を計算する。
【０８３４】
【数３０８】
2019198815.tif 000310
【０８３５】
ここで、αは0<α<1を満たす実数である。
【０８３６】
なお、式(6-1)は一般化P-R型単調作用素分割を用いる場合、式(6-2)は一般化D-R型単調作用素分割を用いる場合に対応する。
【０８３７】
Ｓ２３６において、カウンタ更新部２３６は、カウンタtを1だけインクリメントする。具体的には、t←t+1とする。
【０８３８】
Ｓ２３７において、終了条件判定部２３７は、カウンタtが所定の更新回数τに達した場合（つまり、t=τとなり、終了条件が満たされた場合）は、そのときの潜在変数piの値piτを出力して、処理を終了する。それ以外の場合、Ｓ２３２の処理に戻る。つまり、モデル学習部２３０は、Ｓ２３２〜Ｓ２３５の計算を繰り返す。なお、Ｓ２３５で計算したzi|jt+1は、次の繰り返し計算におけるＳ２３２とＳ２３３で用いられる。
【０８３９】
なお、ヘシアン行列HD_i|jは、式(5-6)〜式(5-9)を用いて設計するのが好ましい。
【０８４０】
本実施形態の発明によれば、機械学習の対象となるモデルの潜在変数を高速に学習することができる。本実施形態の発明によれば、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づき、変数更新則を構成することにより、停留点（最適解）への収束が高速になるように、潜在変数を更新することができる。また、ブレグマンダイバージェンスの定義に用いる凸関数を適切に構成することにより、停留点への収束が高速になるような、ブレグマンリゾルヴェント作用素やブレグマンケーリー作用素を用いた単調作用素分割に基づく変数更新則を構成することができる。
【０８４１】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０８４２】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０８４３】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０８４４】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０８４５】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０８４６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０８４７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０８４８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０８４９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０８５０】
上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。
【図１】
2019198815.tif 000323
【図２】
2019198815.tif 000324
【図３】
2019198815.tif 000325
【図４】
2019198815.tif 000326
【図５】
2019198815.tif 000327
【図６】
2019198815.tif 000328
【図７】
2019198815.tif 000329
【図８】
2019198815.tif 000330
【図９】
2019198815.tif 000331
【図１０Ａ】
2019198815.tif 000332
【図１０Ｂ】
2019198815.tif 000333
【図１１】
2019198815.tif 000334
【図１２】
2019198815.tif 000335
【図１３】
2019198815.tif 000336
【図１４】
2019198815.tif 000337
【図１５】
2019198815.tif 000338
【図１６】
2019198815.tif 000339
【図１７】
2019198815.tif 000340
【図１８】
2019198815.tif 000341
【図１９】
2019198815.tif 000342
【図２０】
2019198815.tif 000343
【図２１】
2019198815.tif 000344
【図２２】
2019198815.tif 000345
【図２３】
2019198815.tif 000346
【図２４】
2019198815.tif 000347
【図２５】
2019198815.tif 000348
【手続補正書】
【提出日】令和1年8月5日(2019.8.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（削除）
【請求項２】
（削除）
【請求項３】
（削除）
【請求項４】
（削除）
【請求項５】
（削除）
【請求項６】
（削除）
【請求項７】
（削除）
【請求項８】
（削除）
【請求項９】
（削除）
【請求項１０】
（削除）
【請求項１１】
（削除）
【請求項１２】
（削除）
【請求項１３】
共通するある１つの主変数についての学習結果を得るための機械学習をする複数のノード部を含む機械学習システムにおいて、
上記複数のノード部のそれぞれは、
該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習部と、
上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信部と、
を含み、
上記学習部は、
上記送受信部が上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
機械学習システムであって、
Ｖを２以上の所定の正の整数とし、上記複数のノード部はノード部１，…，Ｖであるとし、〜Ｖ＝｛１，…，Ｖ｝とし、Ｂを所定の正の整数とし、ｂ＝１，…，Ｂとし、〜Ｂ＝｛１，…，Ｂ｝とし、ノード部ｉにつながっているノード部の集合を〜Ｎ（ｉ）とし、ノード部ｉにおけるノード部ｊに対する双対変数λｉ｜ｊを構成するｂ個目のベクトルをλｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対変数λｉ｜ｊ，ｂをλｉ｜ｊ，ｂ（ｔ＋１）とし、上記機械学習で用いられるノード部ｉに対応するコスト関数をｆｉとし、双対変数λｉ｜ｊの双対補助変数ｚｉ｜ｊを構成するｂ個目のベクトルをｚｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｚｉ｜ｊ，ｂをｚｉ｜ｊ，ｂ（ｔ＋１）とし、双対変数λｉ｜ｊの双対補助変数ｙｉ｜ｊを構成するｂ個目のベクトルをｙｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｙｉ｜ｊ，ｂをｙｉ｜ｊ，ｂ（ｔ＋１）とし、ノード部ｉの主変数ｗｉ，ｂのｂ個目の要素をｗｉとし、ｗｉ，ｂの最適解のｂ個目の要素をｗｉ，ｂ＊とし、Ａｉ｜ｊは以下の式により定義されるとし、Ｉを単位行列とし、０を零行列とし、σ１を所定の正の数とし、Ｔを正の整数として、
【数３２１】
2019198815.tif 000349
ｔ＝０，…，Ｔ−１に対して、（ａ）ノード部ｉが、以下の式に基づいて双対変数の更新を行う処理と、
【数３２２】
2019198815.tif 000350
（ｂ）ノード部ｉが、以下の式に基づいて、双対補助変数の更新を行う処理と、
【数３２３】
2019198815.tif 000351
が行われ、ｔ＝０，…，Ｔ−１の一部又は全部に対しては、上記（ａ）及び上記（ｂ）の処理に加えて、（ｃ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、少なくとも１つのノード部ｉが、少なくとも１つのノード部ｊに双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を送信する処理と、
（ｄ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を受信したノード部ｉが、ｚｉ｜ｊ，ｂ（ｔ＋１）＝ｙｉ｜ｊ，ｂ（ｔ＋１）とする処理と、
が行われる、
機械学習システム。
【請求項１４】
情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノート部を含む機械学習システムにおいて、
上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習が行われ、
上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
機械学習システムであって、
Ｖを２以上の所定の正の整数とし、上記複数のノード部はノード部１，…，Ｖであるとし、〜Ｖ＝｛１，…，Ｖ｝とし、Ｂを所定の正の整数とし、ｂ＝１，…，Ｂとし、〜Ｂ＝｛１，…，Ｂ｝とし、ノード部ｉにつながっているノード部の集合を〜Ｎ（ｉ）とし、ノード部ｉにおけるノード部ｊに対する双対変数λｉ｜ｊを構成するｂ個目のベクトルをλｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対変数λｉ｜ｊ，ｂをλｉ｜ｊ，ｂ（ｔ＋１）とし、双対変数λｉ｜ｊの双対補助変数ｚｉ｜ｊを構成するｂ個目のベクトルをｚｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｚｉ｜ｊ，ｂをｚｉ｜ｊ，ｂ（ｔ＋１）とし、双対変数λｉ｜ｊの双対補助変数ｙｉ｜ｊを構成するｂ個目のベクトルをｙｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｙｉ｜ｊ，ｂをｙｉ｜ｊ，ｂ（ｔ＋１）とし、ノード部ｉの主変数ｗｉのｂ個目の要素をｗｉ，ｂとし、ｔ回目の更新後の双対補助変数ｗｉ，ｂをｗｉ，ｂ（ｔ）とし、上記機械学習で用いられるノード部ｉに対応するコスト関数をｆｉとし、コスト関数ｆｉのｗｉ，ｂ（ｔ）に関する一次勾配を▽ｆｉ（ｗｉ，ｂ（ｔ））とし、Ａｉ｜ｊは以下の式により定義されるとし、Ｉを単位行列とし、０を零行列とし、σ１を所定の正の数とし、ηを正の数とし、Ｔを正の整数として、
【数３２４】
2019198815.tif 000352
ｔ＝０，…，Ｔ−１に対して、（ａ）ノード部ｉが、以下の式に基づいて双対変数の更新を行う処理と、
【数３２５】
2019198815.tif 000353
（ｂ）ノード部ｉが、以下の式に基づいて、主変数の更新を行う処理と、
【数３２６】
2019198815.tif 000354
が行われ、ｔ＝０，…，Ｔ−１の一部又は全部に対しては、上記（ａ）及び上記（ｂ）の処理に加えて、（ｃ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、少なくとも１つのノード部ｉが、少なくとも１つのノード部ｊに双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を送信する処理と、
（ｄ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を受信したノード部ｉが、ｚｉ｜ｊ，ｂ（ｔ＋１）＝ｙｉ｜ｊ，ｂ（ｔ＋１）とする処理と、
が行われる、
機械学習システム。
【請求項１５】
複数のノード部が、共通するある１つの主変数についての学習結果を得るための機械学習をする機械学習方法において、
上記機械学習方法は、
上記複数のノード部のそれぞれの学習部が、該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習ステップと、
該ノード部の送受信部が、上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信ステップと、
を含み、
上記学習ステップは、
上記送受信ステップが上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
機械学習方法であって、
Ｖを２以上の所定の正の整数とし、上記複数のノード部はノード部１，…，Ｖであるとし、〜Ｖ＝｛１，…，Ｖ｝とし、Ｂを所定の正の整数とし、ｂ＝１，…，Ｂとし、〜Ｂ＝｛１，…，Ｂ｝とし、ノード部ｉにつながっているノード部の集合を〜Ｎ（ｉ）とし、ノード部ｉにおけるノード部ｊに対する双対変数λｉ｜ｊを構成するｂ個目のベクトルをλｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対変数λｉ｜ｊ，ｂをλｉ｜ｊ，ｂ（ｔ＋１）とし、上記機械学習で用いられるノード部ｉに対応するコスト関数をｆｉとし、双対変数λｉ｜ｊの双対補助変数ｚｉ｜ｊを構成するｂ個目のベクトルをｚｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｚｉ｜ｊ，ｂをｚｉ｜ｊ，ｂ（ｔ＋１）とし、双対変数λｉ｜ｊの双対補助変数ｙｉ｜ｊを構成するｂ個目のベクトルをｙｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｙｉ｜ｊ，ｂをｙｉ｜ｊ，ｂ（ｔ＋１）とし、ノード部ｉの主変数ｗｉ，ｂのｂ個目の要素をｗｉとし、ｗｉ，ｂの最適解のｂ個目の要素ｗｉ，ｂ＊とし、Ａｉ｜ｊは以下の式により定義されるとし、Ｉを単位行列とし、０を零行列とし、σ１を所定の正の数とし、Ｔを正の整数として、
【数３２７】
2019198815.tif 000355
ｔ＝０，…，Ｔ−１に対して、（ａ）ノード部ｉが、以下の式に基づいて双対変数の更新を行うステップと、
【数３２８】
2019198815.tif 000356
（ｂ）ノード部ｉが、以下の式に基づいて、双対補助変数の更新を行うステップと、
【数３２９】
2019198815.tif 000357
が行われ、ｔ＝０，…，Ｔ−１の一部又は全部に対しては、上記（ａ）及び上記（ｂ）のステップ加えて、
（ｃ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、少なくとも１つのノード部ｉが、少なくとも１つのノード部ｊに双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を送信するステップ、
（ｄ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を受信したノード部ｉが、ｚｉ｜ｊ，ｂ（ｔ＋１）＝ｙｉ｜ｊ，ｂ（ｔ＋１）とするステップと、
が行われる、
機械学習方法。
【請求項１６】
複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、
上記複数のノード部は、上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習を行い、
上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
機械学習方法であって、
Ｖを２以上の所定の正の整数とし、上記複数のノード部はノード部１，…，Ｖであるとし、〜Ｖ＝｛１，…，Ｖ｝とし、Ｂを所定の正の整数とし、ｂ＝１，…，Ｂとし、〜Ｂ＝｛１，…，Ｂ｝とし、ノード部ｉにつながっているノード部の集合を〜Ｎ（ｉ）とし、ノード部ｉにおけるノード部ｊに対する双対変数λｉ｜ｊを構成するｂ個目のベクトルをλｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対変数λｉ｜ｊ，ｂをλｉ｜ｊ，ｂ（ｔ＋１）とし、双対変数λｉ｜ｊの双対補助変数ｚｉ｜ｊを構成するｂ個目のベクトルをｚｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｚｉ｜ｊ，ｂをｚｉ｜ｊ，ｂ（ｔ＋１）とし、双対変数λｉ｜ｊの双対補助変数ｙｉ｜ｊを構成するｂ個目のベクトルをｙｉ｜ｊ，ｂとし、ｔ＋１回目の更新後の双対補助変数ｙｉ｜ｊ，ｂをｙｉ｜ｊ，ｂ（ｔ＋１）とし、ノード部ｉの主変数ｗｉのｂ個目の要素をｗｉ，ｂとし、ｔ回目の更新後の双対補助変数ｗｉ，ｂをｗｉ，ｂ（ｔ）とし、上記機械学習で用いられるノード部ｉに対応するコスト関数をｆｉとし、コスト関数ｆｉのｗｉ，ｂ（ｔ）に関する一次勾配を▽ｆｉ（ｗｉ，ｂ（ｔ））とし、Ａｉ｜ｊは以下の式により定義されるとし、Ｉを単位行列とし、０を零行列とし、σ１を所定の正の数とし、ηを正の数とし、Ｔを正の整数として、
【数３３０】
2019198815.tif 000358
ｔ＝０，…，Ｔ−１に対して、（ａ）ノード部ｉが、以下の式に基づいて双対変数の更新を行うステップと、
【数３３１】
2019198815.tif 000359
（ｂ）ノード部ｉが、以下の式に基づいて、主変数の更新を行うステップと、
【数３３２】
2019198815.tif 000360
が行われ、ｔ＝０，…，Ｔ−１の一部又は全部に対しては、上記（ａ）及び上記（ｂ）のステップに加えて、
（ｃ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、少なくとも１つのノード部ｉが、少なくとも１つのノード部ｊに双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を送信するステップと、
（ｄ）ｉ∈〜Ｖ，ｊ∈〜Ｎ（ｉ），ｂ∈〜Ｂとして、双対補助変数ｙｉ｜ｊ，ｂ（ｔ＋１）を受信したノード部ｉが、ｚｉ｜ｊ，ｂ（ｔ＋１）＝ｙｉ｜ｊ，ｂ（ｔ＋１）とするステップと、
が行われる、
機械学習方法。
【請求項１７】
請求項１３または１４に記載の機械学習システムの各部として、コンピュータを機能させるためのプログラム。
【請求項１８】
ｗ∈Ｒｍを機械学習の対象となるモデルの潜在変数、Ｇ（ｗ）（＝ΣｉＧｉ（ｗ））：Ｒｍ→Ｒを学習データを用いて計算される、潜在変数ｗを最適化するためのコスト関数（ただし、関数Ｇｉ（ｗ）（Ｎを２以上の整数とし、ｉは１≦ｉ≦Ｎを満たす整数とする）は閉真凸関数）、Ｄ：Ｒｍ→Ｒを狭義凸関数、ＢＤ（ｗ１｜｜ｗ２）を関数Ｄを用いて定義されるブレグマンダイバージェンス（ｗ１，ｗ２∈Ｒｍ）とし、
コスト関数Ｇ（ｗ）を最小化するｗの停留点ｗ＊とのブレグマンダイバージェンスＢＤが０に近づくように、潜在変数ｗを学習するモデル学習部と
を含む潜在変数学習装置。
【請求項１９】
ｗ∈Ｒｍを機械学習の対象となるモデルの潜在変数、Ｇ（ｗ）（＝ΣｉＧｉ（ｗ））：Ｒｍ→Ｒを学習データを用いて計算される、潜在変数ｗを最適化するためのコスト関数（ただし、関数Ｇｉ（ｗ）（Ｎを２以上の整数とし、ｉは１≦ｉ≦Ｎを満たす整数とする）は閉真凸関数）、Ｄ：Ｒｍ→Ｒを狭義凸関数、Ｒｉ（１≦ｉ≦Ｎを関数Ｄと関数Ｇｉを用いて定義されるブレグマンリゾルヴェント作用素、Ｃｉ（１≦ｉ≦Ｎ）をブレグマンリゾルヴェント作用素Ｒｉを用いて定義されるブレグマンケーリー作用素とし、
ブレグマンリゾルヴェント作用素Ｒｉ（１≦ｉ≦Ｎ）とブレグマンケーリー作用素Ｃｉ（１≦ｉ≦Ｎ）を用いて、潜在変数ｗのｔ＋１回目の更新結果であるｗｔ＋１を再帰的に計算するモデル学習部と
を含む潜在変数学習装置。
【請求項２０】
請求項１９に記載の潜在変数学習装置であって、
Ｎ＝２、ｘ，ｙ，ｚ∈Ｒｍをそれぞれ潜在変数ｗの補助変数とし、
前記モデル学習部は、
次式により、補助変数ｚのｔ回目の更新結果であるｚｔから潜在変数ｗのｔ＋１回目の更新結果であるｗｔ＋１を計算する潜在変数計算部と、
【数３３３】
2019198815.tif 000361
次式により、前記ｚｔと前記ｗｔ＋１から補助変数ｘのｔ＋１回目の更新結果であるｘｔ＋１を計算する第１補助変数計算部と、
【数３３４】
2019198815.tif 000362
次式により、前記ｘｔ＋１から補助変数ｙのｔ＋１回目の更新結果であるｙｔ＋１を計算する第２補助変数計算部と、
【数３３５】
2019198815.tif 000363
次式により、前記ｘｔ＋１と前記ｙｔ＋１から補助変数ｚのｔ＋１回目の更新結果であるｚｔ＋１を計算する第３補助変数計算部とを含む
【数３３６】
2019198815.tif 000364
ことを特徴とする潜在変数学習装置。
【請求項２１】
請求項１９に記載の潜在変数学習装置であって、
Ｎ＝２、ｘ，ｙ，ｚ∈Ｒｍをそれぞれ潜在変数ｗの補助変数とし、
前記モデル学習部は、
次式により、補助変数ｚのｔ回目の更新結果であるｚｔから潜在変数ｗのｔ＋１回目の更新結果であるｗｔ＋１を計算する潜在変数計算部と、
【数３３７】
2019198815.tif 000365
次式により、前記ｚｔと前記ｗｔ＋１から補助変数ｘのｔ＋１回目の更新結果であるｘｔ＋１を計算する第１補助変数計算部と、
【数３３８】
2019198815.tif 000366
次式により、前記ｘｔ＋１から補助変数ｙのｔ＋１回目の更新結果であるｙｔ＋１を計算する第２補助変数計算部と、
【数３３９】
2019198815.tif 000367
次式により、前記ｚｔと前記ｘｔ＋１と前記ｙｔ＋１から補助変数ｚのｔ＋１回目の更新結果であるｚｔ＋１を計算する第３補助変数計算部とを含む
【数３４０】
2019198815.tif 000368
（ただし、αは０＜α＜１を満たす実数）
ことを特徴とする潜在変数学習装置。
【請求項２２】
請求項１８または１９に記載の潜在変数学習装置であって、
関数Ｄは、そのヘシアン行列が関数Ｇｉ（ｗ）のヘシアン行列の逆行列に近くなるような関数である
ことを特徴とする潜在変数学習装置。
【請求項２３】
請求項２２に記載の潜在変数学習装置であって、
Ｎ＝２とし、
関数Ｇ１（ｗ）が、強凸かつリプシッツ平滑である、または、強凸かつリプシッツ平滑であると仮定できる場合に、関数Ｄのヘシアン行列を、次式により計算する
【数３４１】
2019198815.tif 000369
（ただし、ε＞０は実数）
ことを特徴とする潜在変数学習装置。
【請求項２４】
請求項２２に記載の潜在変数学習装置であって、
Ｎ＝２とし、
関数Ｇ１，Ｇ２のそれぞれが、強凸（ＳＣ）かつリプシッツ平滑（ＬＳ）である、または、強凸（ＳＣ）かつリプシッツ平滑（ＬＳ）であると仮定できる場合に、関数Ｄのヘシアン行列を、次式により計算する
【数３４２】
2019198815.tif 000370
（ただし、ε＞０は実数）
ことを特徴とする潜在変数学習装置。
【請求項２５】
請求項２２に記載の潜在変数学習装置であって、
Ｎ＝２とし、
関数Ｇ１（ｗ）が、強凸かつリプシッツ平滑である、または、強凸かつリプシッツ平滑であると仮定できる場合に、関数Ｄのヘシアン行列を、次式により計算する
【数３４３】
2019198815.tif 000371
（ただし、ε＞０は実数、ＬＧ＿１（ｗ）は関数Ｇ１（ｗ）の勾配を用いて計算される行列）
ことを特徴とする潜在変数学習装置。
【請求項２６】
請求項２２に記載の潜在変数学習装置であって、
Ｎ＝２とし、
関数Ｇ１，Ｇ２のそれぞれが、強凸（ＳＣ）かつリプシッツ平滑（ＬＳ）である、または、強凸（ＳＣ）かつリプシッツ平滑（ＬＳ）であると仮定できる場合に、関数Ｄのヘシアン行列を、次式により計算する
【数３４４】
2019198815.tif 000372
（ただし、ε＞０は実数、ＬＧ＿１，ＬＧ＿２はそれぞれ関数Ｇ１（ｗ）、関数Ｇ２（ｗ）の勾配を用いて計算される行列）
ことを特徴とする潜在変数学習装置。
【請求項２７】
ｗ∈Ｒｍを機械学習の対象となるモデルの潜在変数、Ｇ（ｗ）（＝ΣｉＧｉ（ｗ））：Ｒｍ→Ｒを学習データを用いて計算される、潜在変数ｗを最適化するためのコスト関数（ただし、関数Ｇｉ（ｗ）（Ｎを２以上の整数とし、ｉは１≦ｉ≦Ｎを満たす整数とする）は閉真凸関数）、Ｄ：Ｒｍ→Ｒを狭義凸関数、ＢＤ（ｗ１｜｜ｗ２）を関数Ｄを用いて定義されるブレグマンダイバージェンス（ｗ１，ｗ２∈Ｒｍ）とし、
潜在変数学習装置が、コスト関数Ｇ（ｗ）を最小化するｗの停留点ｗ’とのブレグマンダイバージェンスＢＤが０に近づくように、潜在変数ｗを学習するモデル学習ステップと
を含む潜在変数学習方法。
【請求項２８】
ｗ∈Ｒｍを機械学習の対象となるモデルの潜在変数、Ｇ（ｗ）（＝ΣｉＧｉ（ｗ））：Ｒｍ→Ｒを学習データを用いて計算される、潜在変数ｗを最適化するためのコスト関数（ただし、関数Ｇｉ（ｗ）（Ｎを２以上の整数とし、ｉは１≦ｉ≦Ｎを満たす整数とする）は閉真凸関数）、Ｄ：Ｒｍ→Ｒを狭義凸関数、Ｒｉ（１≦ｉ≦Ｎ）を関数Ｄと関数Ｇｉを用いて定義されるブレグマンリゾルヴェント作用素、Ｃｉ（１≦ｉ≦Ｎ）をブレグマンリゾルヴェント作用素Ｒｉを用いて定義されるブレグマンケーリー作用素とし、
潜在変数学習装置が、ブレグマンリゾルヴェント作用素Ｒｉ（１≦ｉ≦Ｎ）とブレグマンケーリー作用素Ｃｉ（１≦ｉ≦Ｎ）を用いて、潜在変数ｗのｔ＋１回目の更新結果であるｗｔ＋１を再帰的に計算するモデル学習ステップと
を含む潜在変数学習方法。
【請求項２９】
請求項２７または２８に記載の潜在変数学習方法であって、
関数Ｄは、そのヘシアン行列が関数Ｇｉ（ｗ）のヘシアン行列の逆行列に近くなるような関数である
ことを特徴とする潜在変数学習方法。
【請求項３０】
請求項１８ないし２６のいずれか１項に記載の潜在変数学習装置としてコンピュータを機能させるためのプログラム。
【手続補正書】
【提出日】令和2年10月9日(2020.10.9)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０１９６
【補正方法】変更
【補正の内容】
【０１９６】
ノード部iの主変数wiのb個目の要素をwi,bとし、wiの最適解のb個目の要素をwi,b*とする。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０２１４
【補正方法】変更
【補正の内容】
【０２１４】
なお、３番目の式のケーリー演算子C2が順序入れ替え行列Pに対応するということについては、非特許文献２にその証明が掲載されている。一番上の式のリゾルヴェント演算子を使った双対変数の更新は、以下のように変形できる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０４７０
【補正方法】変更
【補正の内容】
【０４７０】
このように、それぞれ入力データが記憶されており、情報を互いに送受信しながら、教師データ及び上記入力データに基づいて主変数を用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、機械学習で用いられるコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われる。言い換えれば、複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、複数のノード部は、機械学習に本来対応する非凸関数のコスト関数に代えて、コスト関数の上界となる代理凸関数を最小化するように機械学習が行われる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０８３３
【補正方法】変更
【補正の内容】
【０８３３】
Ｓ２３５において、第２双対変数計算部２３５は、j∈N(i)について、次式により、双対変数zi|j（j∈N(i)）のt+1回目の更新結果であるzi|jt+1を計算する。
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
共通するある１つの主変数についての学習結果を得るための機械学習をする複数のノード部を含む機械学習システムにおいて、
上記複数のノード部のそれぞれは、
該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習部と、
上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信部と、
を含み、
上記学習部は、
上記送受信部が上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
機械学習システムであって、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、wiの最適解のb個目の要素をwi,b*とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、Tを正の整数として、
【数３２１】
2019198815.tif 000373
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行う処理と、
【数３２２】
2019198815.tif 000374
(b) ノード部iが、以下の式に基づいて、双対補助変数の更新を行う処理と、
【数３２３】
2019198815.tif 000375
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)の処理に加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信する処理と、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とする処理と、
が行われる、
機械学習システム。
【請求項２】
情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習する複数のノード部を含む機械学習システムにおいて、
上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習が行われ、
上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
機械学習システムであって、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b(t)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b(t)に関する一次勾配を∇fi(wi,b(t))とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、ηを正の数とし、Tを正の整数として、
【数３２４】
2019198815.tif 000376
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行う処理と、
【数３２５】
2019198815.tif 000377
(b) ノード部iが、以下の式に基づいて、主変数の更新を行う処理と、
【数３２６】
2019198815.tif 000378
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)の処理に加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信する処理と、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とする処理と、
が行われる、
機械学習システム。
【請求項３】
複数のノード部が、共通するある１つの主変数についての学習結果を得るための機械学習をする機械学習方法において、
上記機械学習方法は、
上記複数のノード部のそれぞれの学習部が、該ノード部に入力された入力データを用いて、該ノード部の双対変数を、双対変数を最適化すれば、主変数も最適化されるように、更新する学習ステップと、
該ノード部の送受信部が、上記主変数ではなく、該ノード部の学習部が得た上記双対変数又は上記双対変数の補助変数である双対補助変数を該ノード部以外のノード部に対して送信する送信処理と、
上記主変数ではなく、該ノード部以外のノード部が学習部で得た上記双対変数又は上記双対変数の補助変数である双対補助変数を受信する受信処理と、を行う送受信ステップと、
を含み、
上記学習ステップは、
上記送受信ステップが上記受信処理をした場合には、受信した上記双対変数又は上記双対変数の補助変数である双対補助変数を用いて上記双対変数を更新する
機械学習方法であって、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、wiの最適解のb個目の要素をwi,b*とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、Tを正の整数として、
【数３２７】
2019198815.tif 000379
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行うステップと、
【数３２８】
2019198815.tif 000380
(b) ノード部iが、以下の式に基づいて、双対補助変数の更新を行うステップと、
【数３２９】
2019198815.tif 000381
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)のステップ加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信するステップ、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とするステップと、
が行われる、
機械学習方法。
【請求項４】
複数のノード部が、情報を互いに送受信しながら、それぞれの入力データに基づいて共通するある１つの主変数を用いた写像を機械学習するステップを含む機械学習方法において、
上記複数のノード部は、上記機械学習に本来対応する非凸関数のコスト関数に代えて、上記コスト関数の上界となる代理凸関数を最小化するように上記機械学習を行い、
上記代理凸関数は、上記コスト関数の主変数に関する一次勾配の式、又は、上記コスト関数の主変数に関する一次勾配の式及び二次勾配の式で表されている、
機械学習方法であって、
Vを２以上の所定の正の整数とし、上記複数のノード部はノード部1,…,Vであるとし、~V={1,…,V}とし、Bを所定の正の整数とし、b=1,…,Bとし、~B={1,…,B}とし、ノード部iにつながっているノード部の集合を~N(i)とし、ノード部iにおけるノード部jに対する双対変数λi|jを構成するb個目のベクトルをλi|j,bとし、t+1回目の更新後の双対変数λi|j,bをλi|j,b(t+1)とし、双対変数λi|jの双対補助変数zi|jを構成するb個目のベクトルをzi|j,bとし、t+1回目の更新後の双対補助変数zi|j,bをzi|j,b(t+1)とし、双対変数λi|jの双対補助変数yi|jを構成するb個目のベクトルをyi|j,bとし、t+1回目の更新後の双対補助変数yi|j,bをyi|j,b(t+1)とし、ノード部iの主変数wiのb個目の要素をwi,bとし、t回目の更新後の双対補助変数wi,bをwi,b(t)とし、上記機械学習で用いられるノード部iに対応するコスト関数をfiとし、コスト関数fiのwi,b(t)に関する一次勾配を∇fi(wi,b(t))とし、Ai|jは以下の式により定義されるとし、Iを単位行列とし、Oを零行列とし、σ1を所定の正の数とし、ηを正の数とし、Tを正の整数として、
【数３３０】
2019198815.tif 000382
t=0,…,T-1に対して、(a) ノード部iが、以下の式に基づいて双対変数の更新を行うステップと、
【数３３１】
2019198815.tif 000383
(b) ノード部iが、以下の式に基づいて、主変数の更新を行うステップと、
【数３３２】
2019198815.tif 000384
が行われ、t=0,…,T-1の一部又は全部に対しては、上記(a)及び上記(b)のステップに加えて、
(c) i∈~V, j∈~N(i), b∈~Bとして、少なくとも１つのノード部iが、少なくとも１つのノード部jに双対補助変数yi|j,b(t+1)を送信するステップと、 
(d) i∈~V, j∈~N(i), b∈~Bとして、双対補助変数yj|i,b(t+1)を受信したノード部iが、zi|j,b(t+1)=yj|i,b(t+1)とするステップと、
が行われる、
機械学習方法。
【請求項５】
請求項１または２に記載の機械学習システムの各部として、コンピュータを機能させるためのプログラム。
【請求項６】
w∈Rmを機械学習の対象となるモデルの潜在変数、G(w)(=ΣiGi(w)):Rm→Rを学習データを用いて計算される、潜在変数wを最適化するためのコスト関数（ただし、関数Gi(w) （Nを2以上の整数とし、iは1≦i≦Nを満たす整数とする）は閉真凸関数）、D:Rm→Rを狭義凸関数、BD(w1||w2)を関数Dを用いて定義されるブレグマンダイバージェンス（w1, w2∈Rm）とし、
コスト関数G(w)を最小化するwの停留点w*とのブレグマンダイバージェンスBDが0に近づくように、潜在変数wを学習するモデル学習部と
を含む潜在変数学習装置。
【請求項７】
w∈Rmを機械学習の対象となるモデルの潜在変数、G(w)(=ΣiGi(w)):Rm→Rを学習データを用いて計算される、潜在変数wを最適化するためのコスト関数（ただし、関数Gi(w) （Nを2以上の整数とし、iは1≦i≦Nを満たす整数とする）は閉真凸関数）、D:Rm→Rを狭義凸関数、Ri(1≦i≦N)を関数Dと関数Giを用いて定義されるブレグマンリゾルヴェント作用素、Ci(1≦i≦N)をブレグマンリゾルヴェント作用素Riを用いて定義されるブレグマンケーリー作用素とし、
ブレグマンリゾルヴェント作用素Ri(1≦i≦N)とブレグマンケーリー作用素Ci(1≦i≦N)を用いて、潜在変数wのt+1回目の更新結果であるwt+1を再帰的に計算するモデル学習部と
を含む潜在変数学習装置。
【請求項８】
請求項７に記載の潜在変数学習装置であって、
N=2、x, y, z∈Rmをそれぞれ潜在変数wの補助変数とし、
前記モデル学習部は、
次式により、補助変数zのt回目の更新結果であるztから潜在変数wのt+1回目の更新結果であるwt+1を計算する潜在変数計算部と、
【数３３３】
2019198815.tif 000385
次式により、前記ztと前記wt+1から補助変数xのt+1回目の更新結果であるxt+1を計算する第１補助変数計算部と、
【数３３４】
2019198815.tif 000386
次式により、前記xt+1から補助変数yのt+1回目の更新結果であるyt+1を計算する第２補助変数計算部と、
【数３３５】
2019198815.tif 000387
次式により、前記xt+1と前記yt+1から補助変数zのt+1回目の更新結果であるzt+1を計算する第３補助変数計算部とを含む
【数３３６】
2019198815.tif 000388
ことを特徴とする潜在変数学習装置。
【請求項９】
請求項７に記載の潜在変数学習装置であって、
N=2、x, y, z∈Rmをそれぞれ潜在変数wの補助変数とし、
前記モデル学習部は、
次式により、補助変数zのt回目の更新結果であるztから潜在変数wのt+1回目の更新結果であるwt+1を計算する潜在変数計算部と、
【数３３７】
2019198815.tif 000389
次式により、前記ztと前記wt+1から補助変数xのt+1回目の更新結果であるxt+1を計算する第１補助変数計算部と、
【数３３８】
2019198815.tif 000390
次式により、前記xt+1から補助変数yのt+1回目の更新結果であるyt+1を計算する第２補助変数計算部と、
【数３３９】
2019198815.tif 000391
次式により、前記ztと前記xt+1と前記yt+1から補助変数zのt+1回目の更新結果であるzt+1を計算する第３補助変数計算部とを含む
【数３４０】
2019198815.tif 000392
（ただし、αは0<α<1を満たす実数）
ことを特徴とする潜在変数学習装置。
【請求項１０】
請求項６または７に記載の潜在変数学習装置であって、
関数Dは、そのヘシアン行列が関数Gi(w)のヘシアン行列の逆行列に近くなるような関数である
ことを特徴とする潜在変数学習装置。
【請求項１１】
請求項１０に記載の潜在変数学習装置であって、
N=2とし、
関数G1(w)が、強凸かつリプシッツ平滑である、または、強凸かつリプシッツ平滑であると仮定できる場合に、関数Dのヘシアン行列を、次式により計算する
【数３４１】
2019198815.tif 000393
（ただし、ε>0は実数）
ことを特徴とする潜在変数学習装置。
【請求項１２】
請求項１０に記載の潜在変数学習装置であって、
N=2とし、
関数G1, G2のそれぞれが、強凸(SC)かつリプシッツ平滑(LS)である、または、強凸(SC)かつリプシッツ平滑(LS)であると仮定できる場合に、関数Dのヘシアン行列を、次式により計算する
【数３４２】
2019198815.tif 000394
（ただし、ε>0は実数）
ことを特徴とする潜在変数学習装置。
【請求項１３】
請求項１０に記載の潜在変数学習装置であって、
N=2とし、
関数G1(w)が、強凸かつリプシッツ平滑である、または、強凸かつリプシッツ平滑であると仮定できる場合に、関数Dのヘシアン行列を、次式により計算する
【数３４３】
2019198815.tif 000395
（ただし、ε>0は実数、LG_1(w)は関数G1(w)の勾配を用いて計算される行列）
ことを特徴とする潜在変数学習装置。
【請求項１４】
請求項１０に記載の潜在変数学習装置であって、
N=2とし、
関数G1, G2のそれぞれが、強凸(SC)かつリプシッツ平滑(LS)である、または、強凸(SC)かつリプシッツ平滑(LS)であると仮定できる場合に、関数Dのヘシアン行列を、次式により計算する
【数３４４】
2019198815.tif 000396
（ただし、ε>0は実数、LG_1, LG_2はそれぞれ関数G1(w)、関数G2(w)の勾配を用いて計算される行列）
ことを特徴とする潜在変数学習装置。
【請求項１５】
w∈Rmを機械学習の対象となるモデルの潜在変数、G(w)(=ΣiGi(w)):Rm→Rを学習データを用いて計算される、潜在変数wを最適化するためのコスト関数（ただし、関数Gi(w) （Nを2以上の整数とし、iは1≦i≦Nを満たす整数とする）は閉真凸関数）、D:Rm→Rを狭義凸関数、BD(w1||w2)を関数Dを用いて定義されるブレグマンダイバージェンス（w1, w2∈Rm）とし、
潜在変数学習装置が、コスト関数G(w)を最小化するwの停留点w*とのブレグマンダイバージェンスBDが0に近づくように、潜在変数wを学習するモデル学習ステップと
を含む潜在変数学習方法。
【請求項１６】
w∈Rmを機械学習の対象となるモデルの潜在変数、G(w)(=ΣiGi(w)):Rm→Rを学習データを用いて計算される、潜在変数wを最適化するためのコスト関数（ただし、関数Gi(w) （Nを2以上の整数とし、iは1≦i≦Nを満たす整数とする）は閉真凸関数）、D:Rm→Rを狭義凸関数、Ri(1≦i≦N)を関数Dと関数Giを用いて定義されるブレグマンリゾルヴェント作用素、Ci(1≦i≦N)をブレグマンリゾルヴェント作用素Riを用いて定義されるブレグマンケーリー作用素とし、
潜在変数学習装置が、ブレグマンリゾルヴェント作用素Ri(1≦i≦N)とブレグマンケーリー作用素Ci(1≦i≦N)を用いて、潜在変数wのt+1回目の更新結果であるwt+1を再帰的に計算するモデル学習ステップと
を含む潜在変数学習方法。
【請求項１７】
請求項１５または１６に記載の潜在変数学習方法であって、
関数Dは、そのヘシアン行列が関数Gi(w)のヘシアン行列の逆行列に近くなるような関数である
ことを特徴とする潜在変数学習方法。
【請求項１８】
請求項６ないし１４のいずれか１項に記載の潜在変数学習装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2019198815.tif 000397
2019198815.tif 000398
2019198815.tif 000399
2019198815.tif 000400
2019198815.tif 000401
2019198815.tif 000402