Software in Mathematics Demonstration Track in Hakata Workshop 2015
Hakata Workshop(博多ワークショップ)~Discrete Mathematics and its Applications
九州大学 マス・フォア・インダストリ研究所
数学理論先進ソフトウェア開発室
Software in Mathematics Demonstration Track in Hakata Workshop 2015
Hakata Workshop(博多ワークショップ)~Discrete Mathematics and its Applications
九州大学 マス・フォア・インダストリ研究所
数学理論先進ソフトウェア開発室
フィボナッチヒープは高速な優先度付きキューだが，構造が複雑であるため実用 上は計算時間が大きく，実際にはバイナリヒープが利用されることが多 いのが 現状である． 近年Kaplan，Tarjan，Zwickはフィボナッチヒープを改良したシンプルフィボ ナッチヒープを提案している．シンプルフィボナッチ ヒープの計算量はフィボ ナッチヒープと変わらないが，構造が簡単になっているため実用上での高速化が 期待される． そこで本研究では，シンプルフィボナッチヒープ，フィボナッチヒープをC言語 で実装し，藤澤・安井氏（九大IMI）から提供されたダイクストラ法 のプログ ラムに組み込み，全米道路データを用いた実験を行うことにより各データ構造の 性能を評価した．結果としてシンプルフィボナッチヒープが既存のフィ ボナッ チ ヒープよりも高速であることを確認した．
我々は今回，証明支援システムの一つであるＣｏｑを用いて，関係計算を行うためのライブラリを実装した．そもそも「関係」とは，２つの集合Ａ，Ｂの元同士の繋がりの有無を表すものである．これは直積集合Ａ×Ｂの部分集合で表現され，包含関係を定義することもできる．よく知られている「写像」もまた，関係の一種である． 集合論による計算では，集合の元に関する論理限定子（∀や∃など）や論理演算子（ＡＮＤやＯＲなど）により性質を記述し，それを証明していく．それに対して関係計算理論では，演算子として関係の「結合」（写像で言えば合成に相当する）などを用い，関係同士の包含関係によって性質を記述し，関係式の式変形によって証明を行う． 我々が実装したＴａｃｔｉｃ（自動証明手続き）を用いれば，写像をはじめとする関係が持つ様々な性質の証明を簡単に行うことができる．ここでは，それを使用した写像の性質の証明例を紹介する．
回帰モデルのパラメータを選択する際, AIC(赤池情報量基準)などの情報量基準 を できるだけ小さくするパラメータの組み合わせを選ぶことがある. このようなパ ラ メータ選択に対してステップワイズ法が代表的なアルゴリズムである. しかしな が ら, ステップワイズ法は局所的な探索しかしておらず, 得られるパラメータの選 択 が情報量基準を最小化しているかはわからない. 本研究ではAICを採用したAIC最小化を扱い, 近年盛んに研究されている混合整数 非線形計画問題と呼ばれている最適化手法を用いて, 最適性が保証されている手 法 を提案する. 提案する最適化手法を用いて実際のデータで数値実験を行い, どの 程 度の規模の問題までなら現実的な時間で求解できるか紹介する. この数値実験で は, 非商用では最も高速なソルバーの一つである SCIP (Solving Constraint Integer Programs) を用いている. SCIPは分枝限定法を実現するためのソフトウェア・ フレームワークであり, plug-inを開発することで細かな解法の制御が可能とな る. 本研究では, C言語でplug-inを開発した.
タイリング問題を整数計画問題へ定式化を行い専用のソルバーを用いて解を高速に算 出した過程を述べる。 タイリング問題は平面充填問題とも言われ、単位正方形を繋げたタイルと呼ばれる図 面を、与えられた盤面に隙間なく敷き詰める問題である タイリング問題はCGの研究において基本的なパターン構造を構築し巨大なテクスチャ 生成等に応用されている。 整数計画問題(IP)とは目的関数を線形式、制約式を線形式の等式または不等式で書き 表すことができ、かつ変数が整数の値を取る問題である。 IPはNP困難であるがIPを高速に解くソルバーが存在する。 今回、最適化ソルバーであるGurobi Optimizerを活用し一般的なタイリングとWang Tilingを定式化することで自動的に解答を出力するアプリケーションを実装した。
体 K 上のr +1 変数多項式環 S = K[X_0,⋯,X_r] を考える。このとき、射影空
間 X = P_K^r 上の連接層は、ある有限生成次数付き S 加群 M から定まる。こ
のような加群 M は、次数付き分解とよばれる、自由 S 加群による長さ有限の完
全列を持ち、M にある条件を課せば自由加群の Groebner 基底の理論とチェック
コホモロジーの理論を用いて各自由加群および各射の表現行列を完全に計算でき、
M に付随する連接層の定めるコホモロジー群の K ベクトル空間としての次元を
計算できることが知られている(cf.[1])。また、計算機代数システム Magma に
おいても、外積代数を用いた方法でその計算アルゴリズムが既に実装されている。
本講演では、[1] における証明をもとに講演者が作成した、既存のものとは別
の計算アルゴリズムを紹介する。また、そのアルゴリズムを用いて講演者が実装
した関数、および幾つかの計算例も紹介する。
参考文献:
[1] 丸山 正樹, グレブナー基底とその応用, 共立出版, 2002
Geometric Algebraとは,演算の定義された代数的な記号を幾何学の記述に用いるものである. その中でも特に我々は, 非退化のクリフォード代数の一種を用いた五次元のConformalモデル(今後CGAと呼ぶ)について扱っている. これによって, 回転, 平行移動, 拡大縮小などの幾何学的な操作を代数的に計算することが可能になる. 我々の目的は, CGAを用いて, 動きの方程式を記述することで, 様々な動きの合成を行うことである.そこで我々は, CGA の元, 演算, 可視化, 等価性判定などを扱えるMathematicaのモジュールを作成した.具体的な可視化の方法は, 与えられた元と点を表す元との外積によって現れる図形の方程式を,グレブナ基底を用いて簡約化した後, 適した関数で描画させている. 現在は, 折り紙や魚眼カメラ等の実用的なことで利用できないか模索中である.
2013年にChenらが提案した平面形状補間手法を、Wolfram Reserch社の数理処理 システムMathematica上で実装しました。初期図形と目的図形の入力に対して、 図形の歪みを大きくしないよう、その中間図形を計算して出力します。中間図形 の辺の長さを、初期図形と目的図形の辺の長さの補間として計算します。求めた 辺の長さをもった図形は平面内で実現できるとは限らないため、この図形を平面 に埋め込む手続きが必要となります。埋め込み後、辺の長さとメッシュの情報か ら中間図形の各頂点の座標を計算し、描画します。これらの手続きをまとめ、作 成した関数群をパッケージにしました。また、実装にあたり、Mathematicaでは 計算に時間のかかる関数を近似で定義し、計算時間の短縮を実現しました。
ネットワーク上のインシデント(悪質な攻撃)を早期に検知するために，統計や可視化等の技術によるインシデントの機械発見技術の開発が盛んに行われている．いずれのインシデント発見技術に対しても，既知の珍しくないマルウェアが行う大量のスキャンパケットなどが新しい攻撃を隠してしまい，本来のインシデント発見に支障を来すという共通の問題がある．この問題を解決するために，我々はグラフベースの半教師あり学習を用いたスクリーニングプログラムを開発した．本プログラムは，グラフの最大流・最小カット探索による半教師あり学習(BlumとChawla, 2001)をベースにしており，クラス分類済みデータと未分類データの両方から学習してトラヒックデータのスクリーニングを実現する．本発表では，このプログラムを展示するとともに，実際に運用中のダークネット観測網(未使用のIPアドレス空間)に到達したデータに対する実験結果を報告する．