著者

藤原 直紀 徳山 豪

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2023-AL-191, no.2, pp.1-8, 2023-01-12

---

d 次元の n 個のベクトル列が与えられたとき,列ベクトルを並べ替えて d×n の行列として考える.行列の様子は列ベクトルの順序によるが,これを目的関数を最大/最小にするような列ベクトルの順列を見つける問題として定式化する.目的関数は,行列の各行に対するファーストフィット非減少部分列の要素の効用の和で定義することで,最大化問題をソーティング問題の自然な一般化として考えることができる.本論文では,d が定数の場合には,多項式時間アルゴリズムが構成できることを示し,d が一般である場合に対しては,集合被覆問題や劣モジュラ最適化との関係を調査し,計算複雑度を考察する.

著者

定兼 邦彦 稲葉 真理 今井 浩 徳山 豪

出版者

東北大学

雑誌

特定領域研究

巻号頁・発行日

2002

---

ゲノムデータベースからの知識発見のためのアルゴリズムとデータ構造に関する研究を行った.まず,ゲノム配列データベースからの高速パタン検索のアルゴリズムとデータ構造を開発した.索引としては既存の圧縮接尾辞配列を用いたが,新しいアルゴリズムにより従来の30倍の速度での検索が可能になった.次に,2つの長いゲノム配列のアラインメントを計算するための手法である,MUM(Maximal Unique Match)を列挙する省スペースなアルゴリズムを開発した.配列の長さをnとすると,既存手法ではO(n log n)ビットのスペースが必要であったが,本研究ではこれをO(n)ビットに圧縮した.これにより,ヒトの全DNA配列2つのMUMの計算がメモリ4GBのPC1台を用いて約6時間で計算できた.また,ヒトとマウスの間の共通部分については約24時間で計算できた.データベースからの知識発見のために,データベース中の複数の属性間の最適相関ルールを求める高速アルゴリズムを開発した.最適とは,支持率を固定した場合の最大確信度ルールまたは確信度を固定したときの最大支持率ルールを表す.従来手法では2値属性のみしか効率良く扱えなかったが,本研究の手法では数値属性に対して効率良く動作する.また,数値属性間の最適相関ルールを拡張し,様々な確信度に対する最適領域をピラミッド型の図形で表現する方法を提案し,その効率の良い計算法を提案した.これを最適ピラミッドによる相関ルール表現と呼ぶ.これを用いることでデータベースから抽出した知識を簡潔に表現することができ,過学習の回避もできる.また,ピラミッドを用いてデータの可視化を行うこともできる.

著者

浅野 孝平 全 眞嬉 徳山 豪

出版者

人工知能学会

雑誌

2019年度 人工知能学会全国大会(第33回)

巻号頁・発行日

2019-04-08

---

近年,深層学習をはじめとする高い識別性能をもつ機械学習モデルが様々な分野に応用されている.それらのモデルの多くはブラックボックスであり,ユーザがモデルの挙動や予測の原因について知ることが困難になっており,モデルや予測結果に解釈性に関する研究が活発に行われている.予測の原因となる特徴を特定する手法としてLocal Interpretable Model-agnostic Explanations (LIME) がある.しかしながらLIMEでは,個々の特徴の重要性を測ることはできるが,重要な特徴の組み合わせを特定することはできない.そこで,本研究では予測に影響を与えた特徴の組み合わせに着目した,新たなモデル依存性のない説明手法を提案する.提案手法では,特徴の組み合わせの中から,対象となる予測結果を得るために必要な特徴の組み合わせを探索アルゴリズムによって発見する.計算機実験によって従来のLIMEよりも高い予測能力を持つことが示された.また,画像分類への応用を行い,提案手法の有用性を検証した.

著者

バルバ ルイス 鄭 地園 カルフェル ジャン・ルー・ド ドビンズ マイケル フライシャー ルードルフ 河村 彰星 コルマン マティアス 岡本 吉央 パハ ヤーノシュ 唐 淵 徳山 豪 バードンスホト サンダー 王 天豪

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

no.1894, pp.45-52, 2014-05

著者

塩浦 昭義 徳山 豪

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2004, no.76, pp.43-50, 2004-07-27

---

本稿では、二項木モデル上でのヨーロピアンアジアンオプションの価格付けに対する効率的かつ正確な乱択近似アルゴリズムを提案する。nステップの二項木上での行使価格Xのオプションと任意の正整数kが与えられたとき、我々のアルゴリズムはnに依存しない誤差O(X/k)の範囲の近似値をO(kn^2)時間で求める。我々のアルゴリズムはAingworth Motwani および Oldham (2000) による近似アルゴリズムを乱択アルゴリズムへ修正したものであり、近似精度を理論的にも実用的にも改善している。We propose an efficient and accurate randomized approximation algorithm for computing the price of a European-Asian option on the binomial tree model. For an option with the strike price X on an n-step binomial tree and any positive integer k, we give an O(k n^2) time algorithm with the error bound O(X/k) which is independent of n. Our algorithm can be seen as a modification of the approximation algorithm developed by Aingworth, Motwani, and Oldham (2000) into a randomized algorithm, which improves the accuracy theoretically as well as practically.

著者

今井 桂子 河村 彰星 徳山 豪 マトウシェク イルジ レエム ダニエル

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.109, no.391, pp.17-22, 2010-01-18

---

距離空間内の空でない二集合P,Qから等距離にある点の全体をP,Q間の距離二等分という.列 C_1,…,C_<k-1>であって各C_iがC_<i-1>とC_<i+1>との距離二等分であるもの(但しC_0=P,C_k=Qと考える)をP,Q間の距離k等分という.この概念は回路設計についての村田の問をもとに浅野,マトウシェク,徳山が導入し,PとQとがユークリッド平面内の点でありkが3であるときに限りその存在と唯一とを既に示した.本稿ではより一般に固有測地空間内の空でなく交らない二閉集合間に距離k等分が存在することを示す(一意性は不明).証明においては,二集合間のk階層という概念を定義し,その存在をタルスキ不動点定理によって示す.これはレエム,ライクが似た問題に対して用いた手法である.

著者

結城 匡人 徳山 豪

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.53, pp.9-16, 2003-05-23

---

地図製作やコンピュータグラフィックスの分野では、曲線を表現するのに、その上のサンプル点の列を使用するが、データ量を圧縮するために、曲線の単純化が必要となる。多角形曲線を単純化する近似アルゴリズムとして、Frechet distanceを利用したFrechetSimp法を使用し、二分探索法を用いて、O(nlog n)で計算できる。FrechetSimp法を実装し、複雑に折れ曲がった曲線でも、その特徴を残したまま単純化できることを紹介する。FrechetSimp is an approximation algorithm for that applies the concept of Frechet distance. The algorithm is based on binary search and its complexing is O(n log n). We implement this algorithm and report some experimental results.

著者

福田 剛志 森下真一 森本康彦 徳山 豪

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.72, pp.1-8, 1996-07-26

---

データベースからの決定木の構成において、数値属性の取り扱いは非常に難しいとされていた。実際、有名なエントロピーを用いた決定木構成法について、発案者のQuinlan自身、多くの数値属性があるデータに対しては効率を保証できないことを指摘している。この問題に対する解決法として、最適化問題として数理モデル化した二次元関連ルールを分岐法則に使う方法を提案し、効率的な決定本の構成法を、プロトタイプシステムをデータマイニングシステムSONAR(ystem for Optimized Numeric Association Rule)のサブシステムとして実現した。ここでは、数理的側面からの理論的裏付けと実験結果を報告する。We propose an extension of an entropy-based heuristic of Quinlan [Q93] for constructing a decision tree from a large database with many numeric attributes. Quinlan pointed out that his original method (as well as other existing methods) may be inefficient if any numeric attributes are strongly correlated. Our approach offers one solution to this problem. For each pair of numeric attributes with strong correlation, we compute a two-dimensional association rule with respect to these attributes and the objective attribute of the decision tree. In particular, we consider a family R of grid-regions in the plane associated with the pair of attributes For R ∈ R, the data can be split into two classes: data inside R and data outside R. We compute the region R_<opt> ∈ R that minimizes the entropy of the splitting, and add the splitting associated with R_<opt> (for each pair of strongly correlated attributes) to the set of candidate tests in Quinlan's entropy-based heuristic. We give efficient algorithms for cases in which R is (1) x-monotone connected regions, (2) based-monotone regions, (3) rectangles, and (4) rectilinear convex regions. The algorithm for the first case has been implemented as a subsystem of SONAR(System for Optimized Numeric Association Rules) developed by the authors. Tests show that our approach can create small-sized decision trees.