Ctrl+K

射影と抽出

7. 射影と抽出#

7.1. 導入#

射影は多次元集合の各成分をそれぞれ高々 \(1\) つ選び出して，より小さい次元へと落とす写像のことである． 一方で我々が以下で述べるところの抽出はその限りではなく，必要な成分を望む順序で必要な数だけ選び出すことを許容する写像である． 数理最適化では抽出が基本的な演算になっており，これに慣れることで自由度の高い定式化にも慣れ親しむことができる．

7.2. 射影とは#

多次元集合 \(M\) の要素を \((a_1,\ldots,a_m)\) とするとき， 第 \(i_1\) 成分から第 \(i_n\) 成分についての次の写像を射影とよぶ． 但し \(i_1<\cdots<i_n\) とする．

(1)#\[\pi_{i_1,\ldots,i_n}\colon M \to \{(a_{i_1},\ldots,a_{i_n})\}\]

例えば \(M=\{(1,2,3),(4,5,6),(7,8,9)\}\) である場合に，次の写像は何れも射影である．

(2)#\[\begin{split}\pi_{1}(M) &= \{1,4,7\}, \\ \pi_{3}(M) &= \{3,6,9\}, \\ \pi_{2,3}(M) &= \{(2,3),(5,6),(8,9)\}\end{split}\]

上記は PySIMPLE では次のように対応している．

1from pysimple import Set
2
3M = Set(value=[(1, 2, 3), (4, 5, 6), (7, 8, 9)])
4print(M(0))    # M(0)=Set(value=[1, 4, 7])
5print(M(2))    # M(2)=Set(value=[3, 6, 9])
6print(M(1,2))  # M(1,2)=Set(value=[(2, 3), (5, 6), (8, 9)])

7.3. 抽出とは#

射影は幾何学的な事柄を背景に持っており， 高次の図形を低次の空間へと影を落としたように得られる図形に対応させる写像としての意味合いが強い． このため例えば \(M=\{(1,2,3),(4,5,6),(7,8,9)\}\) から \(M^{\prime}=\{(3,2),(6,5),(9,8)\}\) という集合を得る操作は， 射影 \(\pi_{2,3}\) と二つの成分を互換する写像 \(\sigma\) の合成になっている． というように，射影だけでない他の写像も必要になってくる．

しかし数理最適化の文脈では，幾何学的な背景を考慮してもあまり実りあるものではなく， どちらかと言えば，そのようなことを気にするあまり，正確を期すほどより煩雑な記述になってしまう．

我々はこのような徒労を避けるために，抽出 とよぶ操作を定め，より複雑な定式化を柔軟に行うために用いている．

抽出とは多次元集合の要素の組み合わせを維持しながら，各成分を任意の順序で，任意の数だけ選択する操作として定める．

(3)#\[\mathrm{extract}_{s_1,\ldots,s_k}\colon \{(a_1,\ldots,a_m)\} \to \{(a_{s_1},\ldots,a_{s_k})\}\]

ここで \(s_1<\ldots<s_k\) や \(k\leq m\) といった制約はなく，自由度の高い操作になっている．

例えば \(M=\{(1,2,3),(4,5,6),(7,8,9)\}\) である場合に，次の写像は何れも抽出である．

(4)#\[\begin{split}\mathrm{extract}_{1,1}(M) &= \{(1,1),(4,4),(7,7)\}, \\ \mathrm{extract}_{3,2}(M) &= \{(3,2),(6,5),(9,8)\}, \\ \mathrm{extract}_{1,3,2,1}(M) &= \{(1,3,2,1),(4,6,5,4),(7,9,8,7)\}\end{split}\]

上記は PySIMPLE では次のように対応しており，そもそも抽出を基礎とした記述になっている．

1from pysimple import Set
2
3M = Set(value=[(1, 2, 3), (4, 5, 6), (7, 8, 9)])
4print(M(0,0))      # M(0,0)=Set(value=[(1, 1), (4, 4), (7, 7)])
5print(M(2,1))      # M(2,1)=Set(value=[(3, 2), (6, 5), (9, 8)])
6print(M(0,2,1,0))  # M(0,2,1,0)=Set(value=[(1, 3, 2, 1), (4, 6, 5, 4), (7, 9, 8, 7)])

Tip

射影を記述する共通に普及した専用の記号は (数学の中で緩やかな合意として)， \(p\), \(\pi\) や \(\Pi\) 果ては \(\varpi\) など projection の p を意図した写像を書くことで表現されることが標準的である． 特に関係代数では \(\pi\) や \(\Pi\) が意識して記号選定される．

一方で抽出に至っては何かあるわけではない． 数理最適化の定式化では，抽出は頻出するため，できれば専用の記号が欲しいところであるが，残念ながらない． extract の e から \(\epsilon\) を選定してもよいだろう．

7.4. 要素からの参照#

射影や抽出は集合から新たな集合を導くものであったが， 多成分の要素から，射影や抽出と同様の意味で新たな要素 (の集まり) を対応させる操作も数理最適化の定式化では重要である．

この操作は \(M=\{(a_1,\ldots,a_m)\}\) に対して，次のように書かれるものである．

(5)#\[\mathrm{extract}_{s_1,\ldots,s_k}\colon (a_1,\ldots,a_m) \mapsto (a_{s_1},\ldots,a_{s_k})\]

この操作によって，例えば次の数式を記述できるようになる．

(6)#\[\sum_{m\in M}WT_{\mathrm{extract}_1(m)}\cdot x_m\]

これは \(x\) については多成分の要素 \(m\) そのものを添字としている一方で， \(WT\) については \(m\) の第 \(1\) 成分のみを参照する添字についての和であることを意図した数式である．

集合への抽出操作と同様に，要素についても PySIMPLE では次のように対応した言語になっている．

1from pysimple import Set, Element
2
3M = Set(value=[(1, 2, 3), (4, 5, 6), (7, 8, 9)])
4m = Element(set=M)
5print(m(0,0).set)      # m.set(0,0)=Set(value=[(1, 1), (4, 4), (7, 7)])
6print(m(2,1).set)      # m.set(2,1)=Set(value=[(3, 2), (6, 5), (9, 8)])
7print(m(0,2,1,0).set)  # m.set(0,2,1,0)=Set(value=[(1, 3, 2, 1), (4, 6, 5, 4), (7, 9, 8, 7)])

7.5. SIMPLE での抽出の記述#

PySIMPLE に限らずモデリング言語 SIMPLE では抽出の記述が提供されている． SIMPLE の実装言語ごとの記述方法は次の表のとおりである．

種別

集合 \(M\) の抽出

要素 \(m\) の抽出

関数表記

\(\mathrm{extract}_{1,3,2,1}(M)\)

\(\mathrm{extract}_{1,3,2,1}(m)\)

PySIMPLE

M(0,2,1,0)

m(0,2,1,0)

C++SIMPLE

M.slice(1,3,2,1)

m.at(1),m.at(3),m.at(2),m.at(1)

C++SIMPLE では slice や at があてがわれ，at については一度に at(1,3,2,1) とすることはできない． つまり at に関しては抽出よりも限定的な概念である．

プログラミング言語としてスライスは Python や JavaScript などの登場と普及から，一定の範囲を取り出す操作として定着している． 一方で英単語としての slice は部分としての意味合いがあり，同様の操作を part とよぶ言語もある． また薄く切り取るという意味もあり，C++SIMPLE では指定した成分を切り取っていることからも，この意味に近い．

関連

引用書式

BibTeX

目次