(57)【要約】      （修正有）【課題】エッジ／クラウドでの利用を想定し、広く普及した多くのアプリケーションソフトウェアが直接利用可能で、かつユーザーのプライバシーの保護を考慮したスパースコーディングの秘匿演算方法、秘匿演算装置及びプログラムを提供する。【解決手段】秘匿演算方法は、Ｍ次元の観測信号ベクトルｙがＫ個の基底の辞書行列ＤとＫ次元ベクトルのスパース係数ｘを用いて、ｙ＝Ｄｘと表せるとき、所定の辞書行列Ｄをランダムユニタリ行列を用いて秘匿化して秘匿辞書行列Ｄ＾に変換し、観測信号ベクトルｙをランダムユニタリ行列を用いて秘匿化して秘匿観測信号ｙ＾に変換し、秘匿観測信号ｙ＾と秘匿辞書行列Ｄ＾を用いて最適化問題を直交マッチング追跡法で解き、スパース係数ｘを推定する。【選択図】図１
2019207384.tif 000002
【特許請求の範囲】
【請求項１】
Ｍ次元の観測信号ベクトルｙがＫ個（Ｋ＞Ｍ）の基底を要素とするＭ×Ｋ行列である辞書行列ＤとＫ次元のベクトルであるスパース係数ｘを用いて、
ｙ＝Ｄｘ
と表せるとき、
予め与えられた又は観測信号から学習した辞書行列Ｄを鍵ｐによって生成されるＭ×Ｍ行列であるランダムユニタリ行列ＱＰを用いて秘匿化して秘匿辞書行列Ｄ＾に変換して保存する辞書行列変換手順と、
観測信号ベクトルｙを前記ランダムユニタリ行列ＱＰを用いて秘匿化して秘匿観測信号ｙ＾に変換する観測信号変換手順と、
前記秘匿観測信号ｙ＾と保存されている前記秘匿辞書行列Ｄ＾を用いて数Ｃ１で表される最適化問題を直交マッチング追跡法によって解き、前記スパース係数ｘに近似するスパース係数ｘ＾を計算する演算手順と、
を行うことを特徴とするスパースコーディングの秘匿演算方法。
【数Ｃ１】
2019207384.tif 000055
ただし、εはｘとｘ＾との誤差の目標値である。
【請求項２】
Ｍ次元の観測信号ベクトルｙがＫ個（Ｋ＞Ｍ）の基底を要素とするＭ×Ｋ行列である辞書行列ＤとＫ次元のベクトルであるスパース係数ｘを用いて、
ｙ＝Ｄｘ
と表せるとき、
予め与えられた又は観測信号から学習した辞書行列Ｄ及び観測信号ベクトルｙを鍵ｐによって生成されるＭ×Ｍ行列であるランダムユニタリ行列ＱＰを用いて秘匿化した秘匿辞書行列Ｄ＾及び秘匿観測信号ｙ＾にそれぞれ変換するローカル処理部と、
前記ローカル処理部からの前記秘匿辞書行列Ｄ＾を保存し、前記ローカル処理部から転送された前記秘匿観測信号ｙ＾と保存されている前記秘匿辞書行列Ｄ＾を用いて数Ｃ１で表される最適化問題を直交マッチング追跡法によって解き、前記スパース係数ｘに近似するスパース係数ｘ＾を計算する演算処理部と、
を備えることを特徴とするスパースコーディングの秘匿演算装置。
【請求項３】
請求項１に記載のスパースコーディングの秘匿演算方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、エッジ／クラウドでの利用可能なスパースコーディングの秘匿演算方法、秘匿演算装置及びプログラムに関する。
【背景技術】
【０００２】
スパースコーディング（Ｓｐａｒｓｅ  Ｃｏｄｉｎｇ：ＳＣ）（例えば、非特許文献１〜７を参照。）は、元々生物の一次視覚野の計算モデルとして提案されたものであり、観測信号を少数の基底ベクトルの重み付き線形和で表現する手法である。生物の一次視覚野における受容細胞は、空間周波数成分が網膜上の特定の領域に出現すると、選択的に反応する性質を持つ。Ｏｌｓｈａｕｓｅｎらはこの性質を、自然画像の統計的構造を積極的に利用することによって自然画像を効率的に符号化（コーディング）するための仕組みとして獲得した（例えば、非特許文献１を参照。）とする考えを提案し脚光を浴びた。
【０００３】
現在、スパースコーディングは画像・音響信号などのメディア信号処理、脳波・脳血流・ｆＭＲＩなど生体信号の解析、機械学習など多数の分野に応用されており、その有効性が認められている。例えば、画像処理の分野では雑音除去や画像修復、深層学習では要素技術の一つとして利用され画像識別の分野で最先端の性能を示している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｂ．  Ａ．  Ｏｌｓｈａｕｓｅｎ  ａｎｄ  Ｄ．  Ｊ．  Ｆｉｅｌｄ，  “Ｅｍｅｒｇｅｎｃｅ  ｏｆ  ｓｉｍｐｌｅ−ｃｅｌｌ  ｒｅｃｅｐｔｉｖｅ−ｆｉｅｌｄ  ｐｒｏｐｅｒｔｉｅｓ  ｂｙ  ｌｅａｒｎｉｎｇ  ａ  ｓｐａｒｓｅ  ｃｏｄｅ  ｆｏｒ  ｎａｔｕｒａｌ  ｉｍａｇｅｓ”，  Ｎａｔｕｒｅ，  ｖｏｌ．  ３８１，  ｐｐ．  ６０７−６０９  （１９９６）．
【非特許文献２】日野英逸、村田  昇、“スパース表現の数理とその応用”、信学技報  ｖｏｌ．  １１２（１９８），  ｐｐ．  １３３−１４２，  ２０１２．
【非特許文献３】笠井  裕之、“スパースコーディングの研究動向”、研究報告オーディオビジュアル複合情報処理（ＡＶＭ），  ｖｏｌ．  ２０１４−ＡＶＭ−８４（８），  ｐｐ．  １−１０，  ２０１４．
【非特許文献４】Ｋ．  Ｅｎｇａｎ，  Ｓ．  Ｏ．  Ａａｓｅ  ａｎｄ  Ｊ．  Ｈａｋｏｎ  Ｈｕｓｏｙ，  “Ｍｅｔｈｏｄ  ｏｆ  ｏｐｔｉｍａｌ  ｄｉｒｅｃｔｉｏｎｓ  ｆｏｒ  ｆｒａｍｅ  ｄｅｓｉｇｎ”，  ＩＣＡＳＳＰ１９９９，  ｐｐ．  ２４４３−２４４６  （１９９９）．
【非特許文献５】Ｍ．  Ａｈａｒｏｎ，  Ｍ．  Ｅｌａｄ，  ａｎｄ  Ａ．  Ｂｒｕｃｋｓｔｅｉｎ，  “Ｋ−ＳＶＤ：  Ａｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｏｖｅｒｃｏｍｐｌｅｔｅ  ｄｉｃｔｉｏｎａｒｉｅｓ  ｆｏｒ  ｓｐａｒｓｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｓｉｇ．  Ｐｒｏｃ．，  ５４，  １１，  ｐｐ．  ４３１１−４３２２  （２００６）．
【非特許文献６】Ｙ．  Ｃ．  Ｐａｔｉ，  Ｒ．  Ｒｅｚａｉｉｆａｒ，  Ｙ．  Ｃ．  Ｐ．  Ｒ．  Ｒｅｚａｉｉｆａｒ，  ａｎｄ  Ｐ．  Ｓ．  Ｋｒｉｓｈｎａｐｒａｓａｄ，  “Ｏｒｔｈｏｇｏｎａｌ  ｍａｔｃｈｉｎｇ  ｐｕｒｓｕｉｔ：  Ｒｅｃｕｒｓｉｖｅ  ｆｕｎｃｔｉｏｎ  ａｐｐｒｏｘｉｍａｔｉｏｎ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  ｗａｖｅｌｅｔ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ”，  Ａｓｉｌｏｍａｒ１９９３，  ｐｐ．  ４０−４４  （１９９３）．
【非特許文献７】Ｒ．  Ｃｈａｒｔｒａｎｄ  ａｎｄ  Ｗ．  Ｙｉｎ，  “Ｉｔｅｒａｔｉｖｅｌｙ  ｒｅｗｅｉｇｈｔｅｄ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｃｏｍｐｒｅｓｓｉｖｅ  ｓｅｎｓｉｎｇ”，  ＩＥＥＥ  ＩＣＡＳＳＰ２００８，  ｐｐ．  ３８６９−３８７２  （２００８）．
【非特許文献８】Ｃ．  Ｔ．  Ｈｕａｎｇ，  Ｌ．  Ｈｕａｎｇ，  Ｚ．  Ｑｉｎ，  Ｈ．  Ｙｕａｎ，  Ｌ．  Ｚｈｏｕ，  Ｖ．  Ｖａｒａｄ−ｈａｒａｊａｎ，  ａｎｄ  Ｃ−Ｃ．  Ｊ．  Ｋｕｏ，  “Ｓｕｒｖｅｙ  ｏｎ  ｓｅｃｕｒｉｎｇ  ｄａｔａ  ｓｔｏｒａｇｅ  ｉｎ  ｔｈｅ  ｃｌｏｕｄ”，  ＡＰＳＩＰＡ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｉｇｎａｌ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ，  ｖｏｌ．  ３，  ｅ７，  ２０１４．
【非特許文献９】Ｒ．  Ｌ．  Ｌａｇｅｎｄｉｊｋ，  Ｚ．  Ｅｒｋｉｎ，  ａｎｄ  Ｍ．  Ｂａｒｎｉ，  “Ｅｎｃｒｙｐｔｅｄ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｆｏｒ  ｐｒｉｖａｃｙ  ｐｒｏｔｅｃｔｉｏｎ：  Ｃｏｎｖｅｙｉｎｇ  ｔｈｅ  ｕｔｉｌｉｔｙ  ｏｆ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｍｕｌｔｉｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ”，  ＩＥＥＥ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｍａｇａｚｉｎｅ，  ｖｏｌ．  ３０，  ｎｏ．  １，  ｐｐ．  ８２−１０５，  Ｊａｎ．  ２０１３．
【非特許文献１０】電子情報通信学会誌、“小特集  完全準同形暗号の研究動向”、ｖｏｌ．  ９９，  ｎｏ．１２，  ｐｐ．  １１５０−１１８３，  ２０１６．
【非特許文献１１】Ｉ．  Ｎａｋａｍｕｒａ，  Ｙ．  Ｔｏｎｏｍｕｒａ，  ａｎｄ  Ｈ．  Ｋｉｙａ，  “Ｕｎｉｔａｒｙ  Ｔｒａｎｓｆｏｒｍ−Ｂａｓｅｄ  Ｔｅｍｐｌａｔｅ  Ｐｒｏｔｅｃｔｉｏｎ  ａｎｄ  Ｉｔｓ  Ｐｒｏｐｅｒｔｉｅｓ”，  Ｐｒｏｃ．  Ｅｕｒｏｐｅａｎ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ，  ｖｏｌ．  ＳＩＰＡ−Ｐ３．４，  ｐｐ．  ２４６６−２４７０，  ２０１５．
【非特許文献１２】Ｉ．  Ｎａｋａｍｕｒａ，  Ｙ．  Ｔｏｎｏｍｕｒａ，  ａｎｄ  Ｈ．  Ｋｉｙａ，  “Ｕｎｉｔａｒｙ  Ｔｒａｎｓｆｏｒｍ−Ｂａｓｅｄ  Ｔｅｍｐｌａｔｅ  Ｐｒｏｔｅｃｔｉｏｎ  ａｎｄ  Ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｌ２−ｎｏｒｍ  Ｍｉｎｉｍｉｚａｔｉｏｎ  Ｐｒｏｂｌｅｍｓ”，  ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｉｎｆ．  ＆  Ｓｙｓ．，  ｖｏｌ．  Ｅ９９−Ｄ，  ｎｏ．  １，  ｐｐ．  ６０−６８，  Ｊａｎ．  ２０１６．
【非特許文献１３】Ｙ．  Ｓａｉｔｏ，  Ｉ．  Ｎａｋａｍｕｒａ，  Ｓ．  Ｓｈｉｏｔａ，  ａｎｄ  Ｈ．  Ｋｉｙａ，  “Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｒａｎｄｏｍ  Ｕｎｉｔａｒｙ  Ｍａｔｒｉｘ  ｆｏｒ  Ｂｉｏｍｅｔｒｉｃ  Ｔｅｍｐｌａｔｅ  Ｐｒｏｔｅｃｔｉｏｎ”，  ２０１６  Ｊｏｉｎｔ  ８ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｏｆｔ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｓｙｓｔｅｍｓ  （ＳＣＩＳ）  ａｎｄ  １７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ａｄｖａｎｃｅｄ  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｓｙｓｔｅｍｓ  （ＩＳＩＳ），  Ｓａｐｐｏｒｏ，  ２０１６，  ｐｐ．  ３６６−３７０，  ２０１６．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一方、近年様々な分野においてエッジ／クラウドコンピューティングが急速に普及してきている。そのアプリケーションの領域はスパースコーディングの有効性が確認されているメディア信号処理、生体信号の解析、機械学習などを含め多岐にわたる。しかしエッジ／クラウドコンピューティングの利用は、サービス提供者の信頼性を前提にしており、その信頼性の欠如や事故によって、データの不正利用や流失、プライバシーの侵害といった問題の発生が危惧されている（例えば、非特許文献８を参照。）。今後のクラウドコンピューティングの普及にとって、データの不正利用や流失、エンドユーザーのプライバシーの問題をいかに解決するかが重要な課題となっている。
【０００６】
このため、データを公開することなく、暗号化したデータを第三者に渡し計算を依頼する方法、いわゆる秘密計算が盛んに研究されている（例えば、非特許文献９、１０を参照。）。秘密計算は一般にマルチパーティプロトコルや準同型暗号に基づき実行される。
【０００７】
しかし、除算の困難性、計算効率及び計算精度などに課題があり、ソーティング処理や幾つかの統計解析に限定されるなど、十分な普及には至っていないという課題がある。さらに秘密計算では、暗号化領域での計算実行のために特別な手順を必要とし、広く普及した多くのアプリケーションソフトウェアを直接利用することは一般に困難であるという課題もある。
【０００８】
本発明は、上記課題に鑑みなされたもので、エッジ／クラウドでの利用を想定し、広く普及した多くのアプリケーションソフトウェアが直接利用可能で、かつユーザーのプライバシーの保護を考慮したスパースコーディングの秘匿演算方法、秘匿演算装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明に係るスパースコーディングの秘匿演算方法は、ランダムユニタリ行列を用いた変換によって観測信号および辞書行列を秘匿化し、該秘匿化された観測信号および辞書行列が与えられた時の数Ｃ１で表される最適化問題を直交マッチング追跡法によって解くことにより、スパース係数を求めることとした。
【００１０】
具体的には、本発明に係るスパースコーディングの秘匿演算方法は、
Ｍ次元の観測信号ベクトルｙがＫ個（Ｋ＞Ｍ）の基底を要素とするＭ×Ｋ行列である辞書行列ＤとＫ次元のベクトルであるスパース係数ｘを用いて、
ｙ＝Ｄｘ
と表せるとき、
予め与えられた又は観測信号から学習した辞書行列Ｄを鍵ｐによって生成されるＭ×Ｍ行列であるランダムユニタリ行列ＱＰを用いて秘匿化して秘匿辞書行列Ｄ＾に変換して保存する辞書行列変換手順と、
観測信号ベクトルｙを前記ランダムユニタリ行列ＱＰを用いて秘匿化して秘匿観測信号ｙ＾に変換する観測信号変換手順と、
前記秘匿観測信号ｙ＾と保存されている前記秘匿辞書行列Ｄ＾を用いて数Ｃ１で表される最適化問題を直交マッチング追跡法によって解き、前記スパース係数ｘに近似するスパース係数ｘ＾を計算する演算手順と、
を行うことを特徴とする。
【数Ｃ１】
2019207384.tif 000003
【００１１】
また、本発明に係るスパースコーディングの秘匿演算装置は、
Ｍ次元の観測信号ベクトルｙがＫ個（Ｋ＞Ｍ）の基底を要素とするＭ×Ｋ行列である辞書行列ＤとＫ次元のベクトルであるスパース係数ｘを用いて、
ｙ＝Ｄｘ
と表せるとき、
予め与えられた又は観測信号から学習した辞書行列Ｄ及び観測信号ベクトルｙを鍵ｐによって生成されるＭ×Ｍ行列であるランダムユニタリ行列ＱＰを用いて秘匿化した秘匿辞書行列Ｄ＾及び秘匿観測信号ｙ＾にそれぞれ変換する変換処理部と、
前記ローカル処理部からの前記秘匿辞書行列Ｄ＾を保存し、前記ローカル処理部から転送された前記秘匿観測信号ｙ＾と保存されている前記秘匿辞書行列Ｄ＾を用いて数Ｃ１で表される最適化問題を直交マッチング追跡法によって解き、前記スパース係数ｘに近似するスパース係数ｘ＾を計算する演算処理部と、
を備えることを特徴とする。
【００１２】
本発明は、ランダムユニタリ行列を用いた変換によって観測信号および辞書行列を秘匿化することでユーザーのプライバシーの保護を実現する。そして、エッジ／クラウドの計算資源を利用して秘匿化された観測信号および辞書行列に関する最適化問題を直交マッチング追跡法によって解くため広く普及した多くのアプリケーションソフトウェアが直接利用可能である。
【００１３】
従って、本発明は、エッジ／クラウドでの利用を想定し、広く普及した多くのアプリケーションソフトウェアが直接利用可能で、かつユーザーのプライバシーの保護を考慮したスパースコーディングの秘匿演算方法、及び秘匿演算装置を提供することができる。
【００１４】
本発明に係るプログラムは、前記スパースコーディングの秘匿演算方法をコンピュータに実行させるためのプログラムである。本発明に係るスパースコーディングの秘匿演算装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【発明の効果】
【００１５】
本発明は、エッジ／クラウドでの利用を想定し、広く普及した多くのアプリケーションソフトウェアが直接利用可能で、かつユーザーのプライバシーの保護を考慮したスパースコーディングの秘匿演算方法、秘匿演算装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】スパースコーディングを説明する図である。スパースコーディングは、少数の基底ベクトルの重み付き線形和で表現する線形システムである。
【図２】本発明に係るスパースコーディングの秘匿演算方法で行う事前準備を説明する図である。ローカル処理部で辞書学習とその秘匿を行う。
【図３】本発明に係るスパースコーディングの秘匿演算方法を説明する図である。エッジ／クラウド部でスパースコーディングの秘匿演算を行う。
【図４】本発明に係るスパースコーディングの秘匿演算方法の効果（平均Ｌ２誤差）を説明する図である。
【図５】本発明に係るスパースコーディングの秘匿演算方法の効果（平均サポート間距離）を説明する図である。
【図６】本発明に係るスパースコーディングの秘匿演算方法の効果（スパース係数推定値）を説明する図である。
【図７】本発明に係るスパースコーディングの秘匿演算装置を説明する図である。
【図８】本発明に係るスパースコーディングの秘匿演算装置を説明する図である。
【図９】本発明に係るスパースコーディングの秘匿演算方法を説明するフローチャートである。
【発明を実施するための形態】
【００１７】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１８】
本発明は、プライバシー保護を目的として、スパースコーディングの秘匿演算の方法ならびに装置の発明に関する。
【００１９】
本発明は、エッジ／クラウドでの利用を想定し広く普及した多くのアプリケーションソフトウェアが直接利用可能で、かつユーザーのプライバシーの保護を考慮したスパースコーディングの秘匿演算法である。以下の順で説明していく。
【００２０】
（１）スパースコーディングの定式化
（２）スパースコーディングの秘匿演算をエッジ／クラウドで実行する際のシステム構成
（３）係数選択のアルゴリズムとして広く用いられている直交マッチング追跡法（Ｏｒｔｈｏｇｏｎａｌ  Ｍａｔｃｈｉｎｇ  Ｐｕｒｓｕｉｔ：ＯＭＰ）の秘匿演算法
【００２１】
１．スパースコーディングの定式化
スパースコーディングでは、図１に示すように、Ｍ次元の観測信号ベクトル
【数０】
2019207384.tif 000004
が、Ｋ個の基底の線形結合で表せると仮定する。
【数１】
2019207384.tif 000005
ただし、
【数１−１】
2019207384.tif 000006
は列ベクトルである基底ｄｉ（１≦ｉ≦K）を要素とするＭ×Ｋの辞書行列であり、
【数１−２】
2019207384.tif 000007
はスパース係数である。なお、「Ｋ」は式（１）の線形結合に用いる基底の個数を表している。
【００２２】
スパース係数は少数の係数のみが非ゼロの値を取り、残りの大部分の係数はゼロの値を取る。このように、非ゼロ要素が全体に対して少数である状態をスパース（Ｓｐａｒｓｅ：疎）と呼ぶ。辞書行列Ｄは事前に与えられるか、または観測データに基づき学習により適応的に推定される。
【００２３】
一般的にＫ＞Ｍ（基底の数が、観測信号の次元よりも大きい）であり、過完備な辞書行列を用いる。信号の次元より多い基底による表現ｙ＝Ｄｘではｘの一意性を保証することができないため、通常は観測信号ｙの表現に利用される基底をＤのうちの一部に制限する。つまり、
【数１−３】
2019207384.tif 000008
でｘのｌ０ノルム、すなわちベクトルｘの非ゼロ成分の数を表すとして、スパースコーディングは典型的には最適化問題
【数２】
2019207384.tif 000009
として定式化される。
【００２４】
しかしながら、この問題は全ての基底の組み合わせを試さないと最適解が得られない組合せ最適化問題であり、ＮＰ困難であることが知られている。そこで、ｌ１ノルムへの緩和問題
【数３】
2019207384.tif 000010
を考えることが多い。このｌ１ノルム正則化問題は線型計画問題として表現することが可能である。
【００２５】
なお、スパースコーディングは「辞書設計の問題（Ｄの設計）」と「スパース係数の選択（ｘ）」の２つに分けて考えることができる。
【００２６】
辞書設計の問題では、辞書行列は離散コサイン変換やフーリエ変換、ウェーブレット変換あるいはカーブレット変換のように予め基底を用意しておく方法と、信号から基底を学習する方法がある。スパースコーディングのための辞書学習の代表的な手法がＭＯＤ（Ｍｅｔｈｏｄ  ｏｆ  Ｏｐｔｉｍａｌ  Ｄｉｒｅｃｔｉｏｎ）（非特許文献４）とＫ−ＳＶＤ（Ｋ−Ｓｉｎｇｕｌａｒ  Ｖａｌｕｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）（非特許文献５）である。ＭＯＤはｙとＤｘの間の二乗誤差の最小化に疑似逆行列を使用する。Ｋ−ＳＶＤはｋ−ｍｅａｎｓ法を一般化したものと位置づけられ、ＭＯＤより高速な反復的アルゴリズムとして提案された。
【００２７】
スパース係数の選択アルゴリズムとして直交マッチング追跡法（ＯＭＰ）（非特許文献６）と反復再重み付け最小二乗法（Ｉｔｅｒａｔｉｖｅ．  Ｒｅｗｅｉｇｈｔｅｄ  Ｌｅａｓｔ  Ｓｑｕａｒｅｓ：ＩＲＬＳ）（非特許文献７）はよく知られている。
【００２８】
２．スパースコーディングの秘匿演算のシステム構成
エッジ／クラウド処理部１２でスパースコーディングの秘匿演算を行うアーキテクチャを図２ならびに図３に示す。
【００２９】
図２の事前準備では、ローカル処理部１１において辞書行列Ｄを予め用意またはＫ−ＳＶＤ法（非特許文献５）などを用い学習して生成する。その後、辞書行列Ｄを秘匿辞書行列
【数３−１】
2019207384.tif 000011
へ変換しエッジ／クラウド処理部１２へ伝送する。なお、本明細書では秘匿辞書行列を「D＾」と記載することがある。
つまり、事前準備では、ローカル処理部１１が予め与えられた又は観測信号から学習した辞書行列Ｄを鍵ｐによって生成されるＭ×Ｍ行列であるランダムユニタリ行列ＱＰを用いて秘匿化して秘匿辞書行列Ｄ＾に変換して保存する辞書行列変換手順を行う。
【００３０】
図３のスパースコーディングの秘匿演算の実行では、最初にローカル処理部１１において観測信号ｙを秘匿観測信号
【数３−２】
2019207384.tif 000012
へ変換しクラウドへ伝送する。なお、本明細書では秘匿観測信号「ｙ＾」と記載することがある。
つまり、スパースコーディングの秘匿演算の実行では、ローカル処理部１１が観測信号ベクトルｙを前記ランダムユニタリ行列ＱＰを用いて秘匿化して秘匿観測信号ｙ＾に変換する観測信号変換手順を行う。
次に、エッジ／クラウド処理部１２で、事前に転送された秘匿辞書行列D＾と秘匿観測信号ｙ＾を用いてＯＭＰのアルゴリズムを実行してスパース係数が推定される。つまり、スパースコーディングの秘匿演算の実行では、エッジ／クラウド処理部１２が前記秘匿観測信号ｙ＾と保存されている前記秘匿辞書行列Ｄ＾を用いて数Ｃ１で表される最適化問題を直交マッチング追跡法によって解き、前記スパース係数ｘに近似するスパース係数ｘ＾を計算する演算手順を行う。
【００３１】
なお、エッジ／クラウド処理部１２ではポスト処理を行ってもよい。ポスト処理は、推定したスパース係数を用いて、画像・音響信号などのメディア信号処理、脳波・脳血流・ｆＭＲＩなどの生体信号の解析、機械学習などアプリケーションごとに必要な処理である。
【００３２】
３．直交マッチング追跡法（ＯＭＰ）の秘匿演算法
〔直交マッチング追跡法（ＯＭＰ）〕
観測信号ｙと辞書Ｄが与えられた時、ｙをＤｘで近似するような係数ｘを求める問題を（狭義の）スパースコーディング問題と呼ぶ。ここでは式（２）の最適化問題を再構成誤差を一定の閾値以下に抑えた上でできるだけ少ない数の基底の線型結合で信号を近似する問題
【数４】
2019207384.tif 000013
として考える。ここで、εは辞書行列Ｄとスパース係数ｘの積とサンプル信号ｙとの誤差の目標値である。
この問題に対する解法として、貪欲法に基づく方法やｌ０ノルム制約をｌ１ノルム制約で緩和した上で解く方法など、数多くのアルゴリズムが提案されている。
【００３３】
本発明では、スパース係数の選択アルゴリズムとして、広く用いられている直交マッチング追跡法（ＯＭＰ）（非特許文献６）の秘匿演算について提案する。直交マッチング追跡法は、観測信号の近似に利用する係数の添字集合の中から「サポート」、すなわち非ゼロ係数の添字集合Ｓを見つけ出すアルゴリズムである。初めはサポートは空集合であるとして、観測信号ｙを基底の線型結合で近似した時の残差を最小にするように新たな基底をサポート集合に一つ一つ追加していき、サポートに含まれる基底のみで信号を近似した時の残差がε以下になったら停止する。残差の低減に寄与する基底を順次選択していく貪欲法であり、解の最適性は保証されないが、多くの場合優れた近似を与えることが知られている。
【００３４】
図９は、直交マッチング追跡法の演算アルゴリズムを説明する図である。本演算アルゴリズムは、初期化ステップＳ０１とメインループ（ステップＳ０２〜Ｓ０７）からなる。
（ステップＳ０１）
各パラメータを初期化する。
【数４−１】
2019207384.tif 000014
ここで、ｋについて説明する。スパースコーディングでは、式（１）のように観測信号yを基底ｄｉの線形結合で近似する。ＯＭＰアルゴリズムでは、K個の基底ｄｉ（ｉ＝１，２，．．，Ｋ）の中から、最もよく近似できる基底から順次サポートＳに追加していく。その時の基底の個数を表す変数が「k」である。
例えば、ｋ＝１は一つの基底を使って観測信号ｙを表すことを意味し、そのときのｄｉはｄ１の場合、あるいはそれ以外のｄ３の場合などもある。また、ｋ＝２のときは２つの基底を使って観測信号ｙを表すことを意味し、そのときのｄｉはｄ１とｄ５の場合、あるいはそれ以外のｄ１とｄ３の場合などもある。
ステップＳ０１は初期化なので、ｋ＝０、スパース係数ｘをゼロベクトル、残差ｒを観測信号ｙ、サポートＳを空集合とする。
【００３５】
（ステップＳ０２）
ｋをｋ＋１とする。
（ステップＳ０３）
ｋ個目の基底ｄｉをサポートＳに追加した時の誤差を算出する。
【数５】
2019207384.tif 000015
（ステップＳ０４）
サポートＳを更新する。
【数６】
2019207384.tif 000016
（ステップＳ０５）
サポートＳ内での最良解ｘ−ｋを探索する。
【数７】
2019207384.tif 000017
（ステップＳ０６）
残差ｒを更新する。
【数８】
2019207384.tif 000018
（ステップＳ０７）
更新した残差ｒが目標値ε内であるかを確認する。
【数９】
2019207384.tif 000019
更新した残差ｒが目標値内であれば、ステップＳ０５で探索した結果を解とする。
【００３６】
引き続く解析を容易にするために、ここで基底ベクトルｄｉを
【数１０】
2019207384.tif 000020
で定義する。但しδｉは
【数１０−１】
2019207384.tif 000021
のｉ番目の要素が１でそれ以外の要素はゼロの列ベクトルである。δｉを用いて、式（５）の近似誤差を以下のように表現する。
【数５Ａ】
2019207384.tif 000022
【００３７】
本発明のランダムユニタリ行列に基づいた直交マッチング追跡法（ＯＭＰ）の秘匿演算について説明する前に、ランダムユニタリ行列を説明する。
【００３８】
〔ランダムユニタリ行列〕
ランダムユニタリ行列に基づいた秘匿演算の基本性質について述べる。先行研究において、キャンセラブルバイオメトリクスのための一方法として、ランダムユニタリ変換に基づくテンプレート保護法が研究されている（非特許文献１１、１３）。一般的にランダムユニタリ行列に基づく秘匿演算では、鍵ｐによって生成されるランダムユニタリ行列Ｑｐを用いた変換Ｔ（・）により、N次元の信号ｆｚ（ｚ＝１、・・・、Ｌ）がN次元の秘匿信号
【数１１】
2019207384.tif 000023
へ変換される。なお、本明細書では秘匿信号「ｆｚ＾」と記載することがある。
但し、ＱｐはＮ×Ｎ行列
【数１１−１】
2019207384.tif 000024
であり、
【数１２】
2019207384.tif 000025
を満たす。ここで［・］＊はエルミート転置、Ｉは単位行列を表す。Ｎは任意の自然数であるが、本実施形態ではＮ＝Ｍである。また、「Ｌ」は信号数（サンプル数）である。例えば、音声信号の場合にはｚは時刻に相当し、信号ｆｚ（要素数はN個）は時刻ｚ＝１〜ＬまでのＬ個のサンプル信号となる（N個の要素を持つ信号ｆｚが、L個存在する。）。また、画像の場合には、例えばｚは画像ごとのインデックスと定義でき、ｆ１からｆＬまでのＬ個の画像信号となる。また、１枚の画像を小ブロックに分けて、それぞれの小ブロックごとにインデックスを割り当ててもよい。
【００３９】
ランダムユニタリ行列Ｑｐの生成は、グラムシュミットの直交化を用いる方法や、複数のユニタリ行列を組み合わせることでＱｐを生成する方法が検証されている。２つの観測信号ｆｚとｆｗをベクトルａとｂと考えると、ランダムユニタリ行列Ｑｐで変換したベクトルａ＾とｂ＾との間に次の関係が成り立つ。
特徴１：ユークリッド距離の保存
【数１３】
2019207384.tif 000026
特徴２：内積の保存
【数１４】
2019207384.tif 000027
特徴３：相関係数の保存
【数１５】
2019207384.tif 000028
特徴4：ノルム不変
【数１５−１】
2019207384.tif 000029
【００４０】
〔直交マッチング追跡法（ＯＭＰ）の秘匿演算〕
本実施形態のスパースコーディングの秘匿演算では、次式のように秘匿された観測信号ｙ＾ならびに辞書行列Ｄ＾を生成する。
【数１６】
2019207384.tif 000030
【数１７】
2019207384.tif 000031
【００４１】
ｙ＾とＤ＾が与えられたとき、式（４）に代わり、次式の最適化問題を考える。
【数１８】
2019207384.tif 000032
上式を直交マッチング追跡法によって解き、スパース係数
【数１８−１】
2019207384.tif 000033
を得る。なお、本明細書では式（１８−１）のスパース係数を「ｘ＾」と記載することがある。
【００４２】
ここで、スパース係数ｘ＾が、観測信号ｙと辞書行列Ｄを秘匿しない場合に得られたスパース係数ｘと等しくなることを証明する。直交マッチング追跡法の秘匿演算アルゴリズムは、図９の通りである。
（ステップＳ０１）
各パラメータを初期化する。
【数１８−２】
2019207384.tif 000034
ステップＳ０１は初期化なので、ｋ＝０、スパース係数ｘをゼロベクトル、残差ｒ＾を秘匿された観測信号ｙ＾、サポートＳを空集合とする。
【００４３】
（ステップＳ０２）
ｋをｋ＋１とする。
（ステップＳ０３）
ｋ個目の基底ｄｉをサポートＳに追加した時の誤差を算出する。ここで、式（５Ａ）で辞書行列Ｄと残差ｒｋ−１を秘匿したＤ＾とｒ＾ｋ−１で置き換え、式（１６）と式（１７）の関係式を用いると、近似誤差は次式で表される。
【数１９】
2019207384.tif 000035
前述したランダムユニタリ行列の性質より、ノルム不変であるから
【数１９−１】
2019207384.tif 000036
、内積保存であるから
【数１９−２】
2019207384.tif 000037
【数１９−３】
2019207384.tif 000038
が成立する。
このため、式（１９）は次のように書き換えることができる。
【数２０】
2019207384.tif 000039
式（２０）は、式（５Ａ）と等しい。つまり、秘匿信号ｙ＾やＤ＾を用いて計算される近似誤差ε＾（ｉ）は原信号（ｙ及びＤ）を用いて計算される近似誤差ε（ｉ）と等しくなる。
【００４４】
（ステップＳ０４）
サポートＳを更新する。ε＾（ｉ）＝ε（ｉ）より、次式が成立する。
【数２１】
2019207384.tif 000040
【００４５】
（ステップＳ０５）
サポートＳ内での最良解ｘ＾ｋを探索する。
【数２２】
2019207384.tif 000041
【数２２−１】
2019207384.tif 000042
式（２２）内の式（２２−１）に関する最小化
【数２２−２】
2019207384.tif 000043
を解くことにより、次式が得られる。
【数２３】
2019207384.tif 000044
式（１４）の内積の保存の関係より
【数２３−１】
2019207384.tif 000045
が成立することから、式（２３）は次式のように書き換えることができる。
【数２４】
2019207384.tif 000046
式（２４）は式（７）と等しい。つまり、秘匿信号ｙ＾やＤ＾を用いて得られるサポート内での最良解ｘ＾ｋは原信号（ｙ及びＤ）を用いた場合の最良解ｘ−ｋと等しくなる。
【００４６】
（ステップＳ０６）
残差ｒ＾を更新する。式（８）を秘匿信号に置き換えると次式となる。
【数２４−１】
2019207384.tif 000047
式（１６）及び式（１７）の定義式及びサポート内での最良解ｘ＾ｋ＝ｘ−ｋより、次式が得られる。
【数２５】
2019207384.tif 000048
ここで、式（８）が成立することから、式（２５）は原信号を用いた場合の誤差ｒｋを用いて次式のように表すことができる。
【数２５−１】
2019207384.tif 000049
【００４７】
（ステップＳ０７）
更新した残差ｒ＾が目標値ε内であるかを確認する。
【数２５−２】
2019207384.tif 000050
式（２５−２）を満たすとき終了となるが、式（２５−１）及びノルム不変の性質より、
【数２６】
2019207384.tif 000051
が成立する。つまり、秘匿信号ｙ＾やＤ＾での停止条件は原信号（ｙ及びＤ）での停止条件と等しくなる。
【００４８】
以上より、秘匿信号を用いて計算されるスパース係数ｘ＾は、原信号を用いて計算されるスパース係数ｘと等しいことが証明された。
【００４９】
４．スパースコーディングの秘匿演算のシステムの具体的構成
図７及び図８は、スパースコーディングの秘匿演算のシステムを説明する具体的構成図である。スパースコーディングの秘匿演算のシステムは、ローカル処理部１１とエッジ／クラウド処理部１２で構成される。
【００５０】
図７は、前述した辞書行列変換手順時の図である。
ローカル処理部１１は、辞書学習部２１、ランダムユニタリ変換部２２、キャッシュ部２３、送信部２４を備える。辞書学習部２１は、学習用の観測信号ｙを受信し、Ｋ−ＳＶＤ法（非特許文献５）などを用い学習して辞書行列Ｄを生成する。なお、辞書行列Ｄが予め与えられている場合は、辞書学習部２１は不要である。ランダムユニタリ変換部２２は、辞書行列Ｄを鍵ｐによって生成されるＭ×Ｍ行列であるランダムユニタリ行列ＱＰを用いて秘匿化して秘匿辞書行列Ｄ＾に変換する。キャッシュ部２３は、ランダムユニタリ変換部２２で生成された秘匿辞書行列Ｄ＾を一時保管する。送信部２４は、当該秘匿辞書行列Ｄ＾をエッジ／クラウド処理部１２へ送信する。
【００５１】
エッジ／クラウド処理部１２は、受信部２５及びデータベース部２６を備える。送信部２５は、ローカル処理部１１から送信されてきた秘匿辞書行列Ｄ＾を受信する。データベース部２６は、当該秘匿辞書行列Ｄ＾を保存する。
【００５２】
図８は、前述した観測信号変換手順及び演算手順時の図である。
これらの手順では、ローカル処理部１１において辞書学習部２１は不要である。ランダムユニタリ変換部２２は、観測信号ベクトルｙを前記ランダムユニタリ行列ＱＰを用いて秘匿化して秘匿観測信号ｙ＾に変換する。キャッシュ部２３は、ランダムユニタリ変換部２２で生成された秘匿観測信号ｙ＾を一時保管する。送信部２４は、当該秘匿観測信号ｙ＾をエッジ／クラウド処理部１２へ送信する。
【００５３】
エッジ／クラウド処理部１２は、受信部２５及びデータベース部２６の他に、メインループ部１３、初期化部３１、及びスパース係数出力部３７を備える。送信部２５は、ローカル処理部１１から送信されてきた秘匿観測信号ｙ＾を受信する。送信部２５は、初めて秘匿観測信号ｙ＾を受信したときに、初期化部３１へ転送し、図９の直交マッチング追跡法において秘匿演算アルゴリズムのステップＳ０１をさせる。以降送信部２５は、受信した秘匿観測信号ｙ＾をメインループ部１３へ転送する。
【００５４】
メインループ部１３は、秘匿観測信号ｙ＾とデータベース部２６が保存する秘匿辞書行列Ｄ＾を用いて、スパース係数ｘ＾を演算する。メインループ部１３は、近似誤差算出部３２、サポート更新部３３、最良解探索部３４、残差更新部３５及び演算停止部３６を有する。
【００５５】
近似誤差算出部３２は、データベース部２６が保存する秘匿辞書行列Ｄ＾と、秘匿観測信号ｙ＾（初期化された残差）、初期解ｘ０、及び解の初期サポートＳ０、もしくは秘匿観測信号ｙ＾、直前に演算された解ｘｋ−１、残差ｒ＾ｋ−１、解のサポートＳｋ−１を用いて、近似誤差ε＾（ｉ）を演算する（図９のステップＳ０３）。サポート更新部３３は、近似誤差算出部３２が演算した近似誤差ε＾（ｉ）を用いてサポートＳを更新する（図９のステップＳ０４）。
【００５６】
最良解探索部３４は、サポート更新部３３が更新したサポートＳとデータベース部２６が保存する秘匿辞書行列Ｄ＾を用いてサポートＳ内での最良解ｘ＾ｋを探索する（図９のステップＳ０５）。残差更新部３５は、最良解探索部３４が探索した最良解ｘ＾ｋとデータベース部２６が保存する秘匿辞書行列Ｄ＾を用いて残差ｒ＾ｋを更新する（図９のステップＳ０６）。演算停止部３６は、残差更新部３５が更新した残差ｒ＾ｋが目標値εに収まっているか否かを判断し、収まっていれば、最良解探索部３４が探索した最良解ｘ＾ｋをスパース係数出力部３７に出力させる。一方、収まっていなければ、演算停止部３６は、残差ｒ＾ｋ及び最良解ｘ＾ｋを近似誤差算出部３２に引き渡し、再度演算を繰り返させる。
【００５７】
５．実施例
図７及び図８で説明したスパースコーディングの秘匿演算のシステムの有効性を検証するために、当該システムにおいて秘匿前の観測信号（原信号）と秘匿観測信号（秘匿信号）に対してスパース係数の推定を行った。
【００５８】
〔データの生成〕
過完備なランダム辞書行列Ｄにスパースベクトルｘを入力して、ｙ＝Ｄｘにより観測データｙを生成した。以下に、具体的な設定条件を示す。
・辞書行列Ｄ：３０×５０のランダム行列（Ｍ＝３０，Ｋ＝５０）
・スパース係数ｘ：非ゼロの係数が正規分布に従うランダム変数。５０次元（Ｋ＝５０）のベクトルで、その内で非ゼロの係数の個数はｋ＝（１、２，・・・、１０）の１０種類。
・サンプル数：それぞれのkについて１０００（Ｌ＝１０００）
【００５９】
〔評価〕
以下の３つの方法により、スパース係数の推定を行った。
・手法１：直交マッチング追跡法
・手法２：本発明に係る秘匿演算方法
・手法３：ランダム行列による変換
【００６０】
手法１は、原信号に対する直交マッチング追跡法、手法３では、秘匿信号を生成する際にランダムユニタリ行列Ｑｐに代わってユニタリ性を有しないランダム行列により観測信号と辞書行列を生成し、直交マッチング追跡法を適用した。
【００６１】
図４にスパース係数の真値と推定値のＬ２誤差
【数２６−１】
2019207384.tif 000052
の平均を示す。横軸は真値の非ゼロ要素の個数ｋを表す。図４より、本発明に係る秘匿演算方法により推定されるスパース係数（ＯＭＰ（Ｕｎｉｔａｒｙ）：手法２）は原信号に対して推定したスパース係数（ＯＭＰ（Ｔｒｕｅ）：手法１）と一致していることが確認できる。また、ランダムユニタリ行列に代わりランダム行列を用いた場合（ＯＭＰ（Ｒａｎｄｏｍ）：手法３）にはkが大きくなるについて誤差が拡大していることがわかる。
【００６２】
図５に真値Ｓと推定値
【数２６−２】
2019207384.tif 000053
のサポート間距離
【数２７】
2019207384.tif 000054
を示す。横軸は真値の非ゼロ要素の個数kを表す。図５より、本発明に係る秘匿演算方法により推定されるサポート間距離（ＯＭＰ（Ｕｎｉｔａｒｙ）：手法２）は原信号に対して推定したサポート間距離（ＯＭＰ（Ｔｒｕｅ）：手法１）と一致していることが確認できる。ランダム行列を用いた場合（ＯＭＰ（Ｒａｎｄｏｍ）：手法３）には、kが小さい場合でも推定誤差が発生している。
【００６３】
図６には、k＝６の場合の任意の１サンプルについて、スパース係数ｘの真値と３つの手法による推定値を示した。図６より、本発明に係る秘匿演算方法は原信号に対する直交マッチング追跡法と同じスパース係数を推定できていることが確認できる。一方、ランダム行列で変換した場合には推定誤差が発生しており、秘匿信号の生成にユニタリ性は重要な性質であることがわかる。
【００６４】
６．発明の効果
本発明に係るスパースコーディングの秘匿演算方法は、プライバシーを保護しつつエッジ／クラウドの計算資源を利用したスパースコーディングの実行が可能である。本発明に係るスパースコーディングの秘匿演算方法は、プライバシー保護のため観測信号と辞書行列を秘匿した状態でスパース係数を推定でき、かつ普及したアプリケーションでの利用が可能である。
【符号の説明】
【００６５】
１１：ローカル処理部
１２：エッジ／クラウド処理部
１３：メインループ部
２１：辞書学習部
２２：ランダムユニタリ変換部
２３：キャッシュ部
２４：送信部
２５：受信部
２６：データベース部
３１：初期化部
３２：近似誤差算出部
３３：サポート更新部
３４：最良解探索部
３５：残差更新部
３６：演算停止部
３７：スパース係数出力部
【図１】
2019207384.tif 000056
【図２】
2019207384.tif 000057
【図３】
2019207384.tif 000058
【図４】
2019207384.tif 000059
【図５】
2019207384.tif 000060
【図６】
2019207384.tif 000061
【図７】
2019207384.tif 000062
【図８】
2019207384.tif 000063
【図９】
2019207384.tif 000064