昭和63（1988）年度　共同研究実施報告書

課題番号	63−共研−13			専門分類		2
研究課題名	線形及び非線形判別・近似に対する幾何的解法の開発
フリガナ 代表者氏名	イマイ　ヒロシ 今井　浩			ローマ字
所属機関	東京大学
所属部局	大学院理学系研究科
職　　名	助教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	6　人

研究目的と成果（経過）の概要

近年，点集合の線形近似・判別及びその非線形版の問題に対して，幾何的な解法によるアプローチが示され，その研究が進みつつある。本研究では，統計的に頑健な手法として注目を浴びている点集合の〓近似問題，点集合の２つのクラスへの線形判別の問題，そして点集合に対する空間の距離による分割とその最適化問題への応用について取り組み，効率的な幾何的解法を開発することを行う。


近年，点集合の線形近似・判別及びその非線形版の問題に対して，幾何的な解法によるアプローチが示され，その研究が進みつつある。本共同研究では，統計的に頑健な手法として注目を浴びている点集合の〓近似問題，点集合の２つのクラスへの線形判別の問題，そして点集合に対する空間の距離による分割とその最適化問題への応用に取り組み効率的な幾何的解法の開発を行ってきた。
点集合の〓近似問題，つまり平面上のｎ個の点集合を線形関数，直線で近似する問題は，統計や数値計算の分野では，基本的で重要な問題の一つである。点集合の近似に最もよく使われているのは最小二乗法と呼ばれる〓距離ではなく〓距離によるものである。最小二乗法が線形時間の手間で計算できることはよく知られている。
しかし，〓距離による近似は，〓の手間のナイーブなアルゴリズムは簡単に得られるものの，今まであまり研究されていなかった。今回の共同研究においては，この問題を解く線形時間の効率のよいアルゴリズムを開発することができた。研究会等で成果を発表し，論文誌にも掲載された。
点集合の２つのクラスへの線形判別の問題としては，平面上の点集合に対するクラスタリング及びハッシングに関連するいくつかの問題に対して，平面走査法や位相的走査法に基づく効率のよいアルゴリズムを開発した。
点集合に対する空間の距離による分割とその最適化問題への応用に関しては，統計，パターン認識，画像処理などでよく現われる平面上に与えられた２つの点集合の最適なあてはめを求める問題を〓，〓距離について解く効率的なアルゴリズムを開発し，研究会等で発表し，国際会議でも，その成果について発表を行う予定である。

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

発表論文
今井桂子，今井浩：点集合間の重み付きミニマックス線形近似問題に対するアルゴリズム，情報処理学会論文誌Ｖｏｌ．３０，Ｎｏ．４，ｐｐ．１−３（１９８９）．
Ｈｉｒｏｓｈｉ Ｉｍａｉ，Ｋｅｎｊｉ Ｋａｔｏ ａｎｄ Ｐｅｔｅｒ Ｙａｍａｍｏｔｏ：Ａ ｌｉｎｅａｒ−ｔｉｍｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌｉｎｅａｒ 〓 ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｆ ｐｏｉｎｔｓ，Ａｌｇｏｒｉｔｈｍｉｃａ Ｖｏｌ．４，ｐｐ．７７−９６（１９８９）．
口頭発表
今井桂子：対応の与えられた点集合間のミニマックス近似問題について
ＯＲ学会数理計画研究部会，１９８８年７月２３日
Ｈｉｒｏｓｈｉ Ｉｍａｉ，Ｋｅｉｋｏ Ｉｍａｉ ａｎｄ Ｒｅｔｅｒ Ｙａｍａｍｏｔｏ：Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｒｔｈｏｇｏｎａｌ〓，ｌｉｎｅａｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｆ ｐｏｉｎｔｓ ｉｎ ｔｗｏ ａｎｄ ｈｉｇｈｅｒ ｄｉｍｅｎｓｉｏｎｓ，Ｔｈｅ １３ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐ．ｏｎ Ｍａｔｈ．Ｐｒｏｇｒａｍｍｉｎｇ，Ｔｏｋｙｏ，Ａｕｇｕｓｔ ２９−Ｓｅｐｔｅｍｂｅｒ ２，１９８８．

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

本研究では，大きく分けて３つある研究問題について，通年に渡り地域毎に個別に研究を行うとともに，当該研究期間中に２回統計数理研究所において共同研究を行い，それぞれの成果の発表及び議論を通して基礎として共通の幾何的解法に関する情報交換や理解を深め，それらを各研究に反映させることを行なう。そのために，研究会では文献紹介等も行なうことを試み，また全体のとりまとめも行う。この研究は，全員が集まって共同研究遂行の核となる機関が必要であること，また統計に関する数理の研究での計算と最適化の分野における本研究の意義の面からも，統計数理研究所の共同研究として実施されることが望まれる。

研究参加者一覧
氏名	所属機関
浅野 孝夫	上智大学
今井 桂子	中央大学
鈴木　敦夫	南山大学
田辺　國士	統計数理研究所
土谷　隆	統計数理研究所