「Visitorパターン無くても普通に構造と処理の分離ってできるのでは？」と思ったのでTwitterのみなさんに教えてもらいました

これは何？

GoFのデザインパターンのVisitorパターンを勉強していたんですがよく分からなかったので、利点をTwitterのみなさんに聞いたところ解決したというお話です。

Visitorパターンを使わなくても「構造と処理の分離」ってできるのでは？

私はデザインパターンの勉強のために、結城浩さんの「Java言語で学ぶデザインパターン入門」を読んでいて、そのうちVisitorパターンのところを読んでいました。

増補改訂版 Java言語で学ぶデザインパターン入門

作者:結城浩
発売日: 2014/03/12
メディア: Kindle版

そこでは、

Visitorパターンでは、データ構造と処理を分離します。そして、データ構造の中をめぐり歩く主体である「訪問者」を表すクラスを用意し、そのクラスに処理をまかせます。

とあり、Visitorパターンの主な目的はデータ構造と処理との分離であると言及されています。この点に関してはWikipedia等他のウェブサイトを見ても大体一緒だと思います:
Visitor パターン - Wikipedia

この章では、ファイルシステムを模したクラスたちFileとDirectoryを走査して列挙するという目的のプログラムが書かれており、若干簡略化すると次のようなプログラムが紹介されています
visitor_test/visitor at main · ashiato45/visitor_test · GitHub:

f:id:sle:20210318180136p:plain — Visitorパターンを使ったJavaプログラム

これで確かに構造(FileとDirectory)とそれらに対する処理(ConcreteVisitor)は分離されているのですが、他方OCamlのようなADTのある言語でどう書くかということを想像すると、パターンマッチと再帰関数で次のように書かれることが多い気がします:

これをJavaで模して書くとinstanceofを使うことになり、次のようになります
visitor_test/functional at main · ashiato45/visitor_test · GitHub:

f:id:sle:20210318180645p:plain — instanceofを使ったJavaプログラム

これでも構造(FileとDirectory)とそれらに対する処理(walk)が分離できているように見えます。こちらのほうが余計な(？)クラスが減って、より素直に目的が達せられているように見えるので、Visitorパターンはなぜ使われるのだろうというのがよく分からなくなりました。そこで、Twitterでみなさんに聞いてみることにしました:

[おしえてください] デザインパターンの勉強中で、Visitorパターンを勉強しているのですが、右のようなコードでもVisitorの利点でよく言われる「構造と処理の分離」はできているような気がします。左のコードの右に対する利点はなんでしょうか。 #Java #駆け出しエンジニアと繋がりたい pic.twitter.com/s9QHPatxeg
— 足跡45(マストドンにいるかも) (@ashiato45) 2021年3月17日

いただいたコメントを参考にして書きなおしてみた

すると、以下のようなコメントをいただきました(他にもいただいていますが後で紹介します)

多分どちらも構造と処理の分離はできてるんですがVisitorの方が処理の抽象度が高い(処理が関数かクラスか)という点で有利なのだと思います。例えばVisitorの方だとVisitorインスタンスに何らかのパラメーターを設定してから使ったり別の構造に再利用したりが自然にできると思います
— 水鳥 (@mizuooon) 2021年3月17日

と思ったんですが instanceof が基本的に行儀悪いので確かにそれを避けてダブルディスパッチ的な事したいだけな気もしてきましたね
— 水鳥 (@mizuooon) 2021年3月17日

instanceof で場合分けだと、
1.クラスが増えた時にメソッドが肥大化する
2.テストする時に特定のクラスだけ挙動り差し替えたいに不便

そのため結局クラスごとにメソッドに切り出すことになります。そうした時に、１つのクラスにメソッドをまとめるより各クラスに分散させる方がJavaらしいです。
— autotaker (@autotaker1984) 2021年3月17日

確かに1つのEntryのサブクラス(今の場合はFileとDirectory)に対する処理はテストの観点やメソッドのサイズの問題から1つのメソッドになっていた方がいいなと思い、しかしながら「別にVisitorを使ったダブルディスパッチの形にすることなくない？」と思って私は次のようなコードを書いてみました
visitor_test/walker at main · ashiato45/visitor_test · GitHub:

f:id:sle:20210318183136p:plain — Visitorパターンを頑なに使おうとしなかったJavaプログラム

これは、先程のwalkをWalkerというクラスに包み、そのなかでFileとDirectoryを引数としてオーバーロードでwalkを定義するものです。

なるほど、やっぱりVisitor(ダブルディスパッチというべきかも)は必要だわ

が、先程のプログラムはコンパイルが通りません。問題は以下の16行目で、

Directoryの中身はEntry型ということしか分からず、Entry型そのものに対するwalkは定義されていないのでコンパイルが通りません*1。
ご指摘いただきいましたが、オーバーロードの呼出はコンパイル時に解決できる必要があります:

メソッドのオーバーロードはコンパイル時に決定されなきゃいけないのでダメなやつでふね。
— autotaker (@autotaker1984) 2021年3月18日

シンボリックリンクを【意識】（つまり、例えばフラグ次第でディレクトリへのリンクは再帰walk()したりしなかったりする）したwalk()を【追加】（置き換えではなく）するにはどの部分が変更されるか、とか考えてみたらいいんじゃ
コンパイル通らないのはwalk(Entry e)がないんだから当たり前ですよね
— NODA Kai (@nodakai) 2021年3月18日

そういうわけで、walkをオーバーロードで定義する以上はどのwalkが呼び出されるかをちゃんと指定する必要があり、そのためにはvisitされる各クラスにちゃんとacceptを用意して「visitor.accept(this)」することになり、自ずとVisitorパターンが導かれるということが分かりました。

まとめ

「構造と処理の分離」というだけならVisitorパターンはいらなそうですが、その分離をした上でさらにメソッド分割やオーバーロードといったオブジェクト指向的に好ましいスタイルで記述するためにはVisitorパターンを使う必要があるようです。

コメントをいただいて教えてくださったみなさま本当にありがとうございました。

その他にいただいたコメント

他にも教えてくださった方が沢山いらっしゃったのでご紹介します:

使ってない版だと walk の中の分岐がダサいし、将来的に巡回する要素のタイプが増えたときにバグり易そうな気はします。
— 🦅あえとす⛩️ (@aetos382) 2021年3月17日

Entryの実装クラスが100個くらいある場合を考えると利点がはっきりしてくると思います。典型的なユースケースはコンパイラの構文木に対する処理の実装で、どんなEntryに何をしてどんな結果を蓄積するのか、構文木の側では意識せずにVisitorの実装に集約でき、別のVisitorの追加も簡単です。
— 異国カラス (@outlandkarasu) 2021年3月17日

コレじゃ駄目ですか？（…と関数型に持って行こうとするコードを全力で非効率なオブジェクト指向に引き戻してぶち壊しにする^^;）→https://t.co/cb3oMoOlzN https://t.co/ZVid6rmzI6
— sumim (@sumim) 2021年3月18日

*1:一応この継承関係だと、どのwalkが呼び出されるかに曖昧性はなく実行時型情報で解決されるものと思っていました…

2020-07-25

Solving the issue that "VK_LAYER_KHRONOS_validation" does not appear in the enumerated InstanceLayer

Issue

Though the latest graphics driver is installed, vkEnumerateInstanceLayerProperties does not return "VK_LAYER_KHRONOS_validation", and the layer is not available.
Instead, "VK_LAYER_LUNARG_standard_validation" is available, but it should be already deprecated in Vulkan 1.2.

My environment

Legion Y520-15IKBN Laptop (Lenovo)
GeForce GTX 1050 Ti
Windows 10 Home 1909
GLFW 3.3.2 WIN64
VulkanSDK 1.2.141.2 for Win64
- Installed at "E:/Lib"

Solution

1. Start "(VulkanSDK Path)/VulkanSDK/1.2.141.2/Tools/vkconfig.exe"
2. Open "Layer Manager" tab. This pane shows the available layers. It would look like this:

f:id:sle:20200725151218p:plain — vulkan layer manager

3. Tick "Use custom layer paths" in "Layer Locations" (It enables the custom setting of layers by a json file, probably.)
4. Click "Add" in "Layer Locaations".
5. Select "(VulkanSDK Path)/VulkanSDK/1.2.141.2/Bin" by the dialog. (This makes Vulkan recognize "VkLayer_khronos_validation.json" in the directory.) Layers are added and it would look like this:
f:id:sle:20200725152423p:plain
6. Move "Khronos: validation" from "Unset Explicit Layers" to "Application Side".
7. Click "Save"
8. Done. You can check that the layer became available by "Vulkan Info" (in the start menu):

Layers: count = 10
==================
VK_LAYER_KHRONOS_validation (Khronos Validation Layer) Vulkan version 1.2.141, layer version 1:
        Layer Extensions: count = 3
                VK_EXT_debug_report        : extension revision 9
                VK_EXT_debug_utils         : extension revision 1
                VK_EXT_validation_features : extension revision 2
        Devices: count = 2
                GPU id = 0 (GeForce GTX 1050 Ti)
                Layer-Device Extensions: count = 3
                        VK_EXT_debug_marker     : extension revision 4
                        VK_EXT_tooling_info     : extension revision 1
                        VK_EXT_validation_cache : extension revision 1

                GPU id = 1 (Intel(R) HD Graphics 630)
                Layer-Device Extensions: count = 3
                        VK_EXT_debug_marker     : extension revision 4
                        VK_EXT_tooling_info     : extension revision 1
                        VK_EXT_validation_cache : extension revision 1

VK_LAYER_LUNARG_api_dump (LunarG API dump layer) Vulkan version 1.2.141, layer version 2:
        Layer Extensions: count = 0
        Devices: count = 2
                GPU id = 0 (GeForce GTX 1050 Ti)
                Layer-Device Extensions: count = 1
                        VK_EXT_tooling_info : extension revision 1

                GPU id = 1 (Intel(R) HD Graphics 630)
                Layer-Device Extensions: count = 1
                        VK_EXT_tooling_info : extension revision 1

References

2020-07-23

Enabling the touchpad scrolling in VSCode (or electron apps) on Lenovo laptops

Issue

The touchpad scrolling on VSCode behaves like arrow keys:

When I scroll, the caret moves up or down instead of the scrollbar.
When I scroll with Ctrl key pressed, the scrollbar moves. Probably its because Ctrl+(Up|Down) is assigned to the scrolling in the default setting of VSCode.

Moreover, the scrolling on the tooltip does not work, so I had to drag&drop the scrollbar (troublesome!)

A hacky solution is suggested here:
github.com
It works, but the renaming can cause the problem in the automatic update, so I wanted a natural solution to this issue. And this situation of the task manager is terrible

これはひどい pic.twitter.com/bOeQMcbZ16
— 足跡45(マストドンにいるかも) (@ashiato45) 2020年7月21日

My environment

Lenovo Legion Y520-15IKBN
Windows 10 Home 1909
Visual Studio Code 1.47.2 installed on Windows
Touchpad driver: Synaptics_19.4.18.30_WHQL_ELAN11.4.109.3.B from Touchpad Driver (Synaptics, Elan) for Windows 10 (64-bit) - Legion Y520-15IKBN - JP

Solution

Rewrite the registry and make the touchpad driver recognize that Code.exe has to be treated as an electron app.
Of course, it is strongly recommended to make a restoring point of System Restore, get the bitlocker key, and take the backup of the registry entry.

1. Open regedit.exe
2. Find "APOptimize" by searching, and go to "Google Chrome Browser" below. In my environment, it is at

HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Control\Elantech\APOptimize\Google Chrome Browser

3. Export the entry of "Google Chrome Browser", and save it.
4. Open the exported registry file by an editor and rewrite it like this (do not change "Option" and "Scroll":

Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Control\Elantech\APOptimize\VSCode]
"Text"="VSCode"
"Class"="VSCode_WidgetWin_1"
"FocusText"=""
"FocusClass"=""
"FileName"="Code.exe"
"Option"=hex:01,00,00,00,00,00,00,00,00,00,01,00,00,00,00,00,00,00,00,00
"Scroll"=hex:01,01,01,01,b9,9b,7d,5f,41,32,28,1e,a0,84,6c,58,48,3c,34,30,01,02,\
  05,07,0a,11,23,4b,02,5d,02,02,5d,02
"Zoom"=hex:58,28,18,10,0c,08,02,02,58,28,18,10,0c,08,02,02,01,02,05,07,0a,11,\
  4b,4b

5. Apply the modified registry file to the system.
6. Reboot. It should work.

How I solved it

According to the hacky solution above, the driver changes the behavior depending on the filename, so I run "ag chrome" in the driver directory, then I found it is writing about chrome things in the registry.

2020-04-05

AtCoder ABC149F「Surrounded Nodes」で木DPに落とすまでってそんなに簡単じゃないよねっていう話

はじめに

多分はじめて競技プログラミングの記事をかきます。ashiato45です。気にする方のために始めに申しますと、私はAtCoder水色ですので「黄未満のやつの書いた記事なんか読むだけ時間の無駄。」という方はお引き取りください。

追記(4/5)

コメントでid:sugarknri さんが解説1の解説をしてくださいました！

これは何？

F - Surrounded Nodesは「期待値の線形性」を使って最終的に木DPに落ちるのですが、そこに到達するまでの期待値の考察は、確率の独立性に関する落とし穴があるよねと思っています。参加記や公式解説を読んでも誰もそのことに言及してないのであれこれ僕がおかしいんですか誰か教えてくださいっていう記事です。

あと、公式解説や他の方の説明を読んでも木DPに落とすまでがピンと来てないという方の役に立つかもしれません。

経緯

e869120さんの力作記事に
qiita.com
というのがありこれを解いていたのですが、どうしても上記ABC149Fの解説2がよくわからなくて困ってしまいました。
2、3日ぐらい考えたらわかった気がしたしACもしたので共有します。
解説1は余計わかんないです。

偽証明

AtCoderの解説2は初っ端からこのようになっています:

期待値の線形性から、各頂点vについて、vがSに属しかつ白く塗られているような確率を計算し、その合計を求めればよいです。

というのですが、この後「vがSに属し」の話しかせず、白の条件の話をしないのです。これは白の条件が明らかだと皆思っているからなのだと思われますし、解説放送を見てもそんな感じがします。
ちなみに、解説1のスタートはこうなっています:

求めるものは「Sの頂点の個数-黒く塗られた頂点の個数」と等しいです。期待値の線形性から、それぞれの項の期待値が求まればよいです。黒く塗られた頂点の個数の期待値は明らかにN/2です。Sの頂点の個数の期待値を考えます。

これでもいきなりSが出てくるのが結局わからないのですが、つまるところ、問題にある「Tの各頂点を、それぞれ独立に確率 1/2 で黒く、確率 1/2 で白く塗り、」というところから1/2で割って、そこからスタートしているように見えます。この考え方を数式的に表わしてみるとこんな感じになります。ここで、どの要素が何に依存しているかをはっきりされるために、次のような記号をもちいます。

$x\in 2^T$ : Tの塗り分け方。いま考えている確率空間の根源事象ですね。問題文の独立性の仮定よりどのxも出方は同様に確からしいです。
$S_x \subset T$ : Tをxで塗ったときに定まるSを、xが決まってはじめて定まるものだということを強調してこう書きます。
$w_x(v) \in \{0, 1\}$ : $v\in S_x$ を頂点とし、xを塗り分け方としたとき、頂点vが白く塗られているなら1、そうでないなら0を返す関数。
χ(P): 命題Pが成立しているときに1、そうでないときに0をとります。指示関数といいます。

すると、求めたかったのは $S_x$ の穴開き度の期待値だったので、
$\begin{align} &E_{x} [S_xの穴開き度] \\ &= E_{x} [\sum_{v\in S_x} \chi(vは塗り分けxで白) ]\quad (←穴開き度の定義)\\ &= E_{x} [\sum_{v\in T} \chi(v\in S_x 、かつ、 vは塗り分けxで白) ]\quad (←総和の条件を値の側に持ってきた)\\ &= \sum_{v\in T} E_{x} [\chi(v\in S_x 、かつ、vは塗り分けxで白) ]\quad (←期待値の線形性)\\ &= \sum_{v\in T} E_{x} [\chi(v\in S_x )]E_{x} [\chi(vは塗り分けxで白) ]\quad (←「かつ」をかけ算に直す？)\\ &= \frac{1}{2}\sum_{v\in T} E_{x} [\chi(v\in S_x )]\quad (←1/2の確率で白く塗られる)\\ &= \frac{1}{2}\sum_{v\in T} p_{x} [\chi(v\in S_x )]\quad (←指示関数の期待値は結局確率)\\ \end{align}$
さあこれで各頂点について $p_x[v\in S_x]$ 、すなわちvが $S_x$ に入っている確率を求めればよく、そのためには解説にあるように「vがSに含まれるための必要十分条件は…」を考えはじめればよい、ように見えます。

が、上の変形はいろいろ間違っています。

「かつ」をかけ算に直す

上の「「かつ」をかけ算に直す？」でやっているのは結局のところ確率変数X,YについてE[XY]=E[X]E[Y]なのですが、これは一般には成り立ちません。
例えばロシアンルーレットをやっていて、Xが「一人目で死亡のとき1、そうでないとき0」、Yが「二人目で死亡のとき1、そうでないとき0」という確率変数だと思いましょう。
するとXとY両方が1となることはないのですからE[XY]=0ですが、他方E[X]=E[Y]=1/6ですから*1、確かに成り立っていません。

E[XY]=E[X]E[Y]は、確率変数XとYが独立である、という仮定があるなら成立することが知られています。フォーマルにはp(X=x, Y=y)=p(X=x)p(Y=y)という条件で、直感的には「片方の確率変数が取る値を知ったとしても、もう片方の確率変数の出方が偏ったりしない」ということを意味します。例えば、先のロシアンルーレットなら「一人目が死んだ」とわかった、つまりX=1ならば二人目は絶対に安全でY=0が100%と、元のY=1が1/6、Y=0が5/6という確率分布から「偏って」しまいます。反対に「一人目が死ななかった」、つまりX=0だとわかったならば、二人目が死ぬ確率は1/5になりましたから何も知らなかったときより緊張感が増すことになります。

今回、「 $v\in S_x$ 」と「vは塗り分けxで白」は独立でしょうか*2。
これは実は独立ではありません。なぜなら、今回の問題のSの「黒く塗られた頂点を全て含む」という定義からvが塗り分けxで黒だと分かったときは、 $v\in S_x$ が100%成立してしまうからです。
ですから、当然このかけ算をわけることはできず、またそこを1/2と切り分けて先に進んでしまうことはできないのです。

ちなみに、ランダムにSを取ってきたときに(まずそれが意味不明ですが)、そこにあらわれる白黒も平均|S|/2ぐらいでしょうと仰るかたもいるかもしれませんが、それも同様の理由で意味不明です。

でもこれ結局正しいじゃん

確かに最後に得られる式は正しいのですが過程が間違っています。推論を正しく進めるには、解説2にある次の考察がカギになります:

頂点vについて、Tからvを取り除いてできる部分木たちを $T_{v1}, T_{v2}$ とします。このとき、vがSに含まれるための必要十分条件は、 $T_{vi}$ たちのうち少なくとも2つが黒く塗られた頂点を含むこと

と言っているのですが、これは大変玄人向けで正確には次のようになります:
「vが白く塗られている条件のもので、vがSに含まれるための必要十分条件は、 $T_{vi}$ たちのうち少なくとも2つが黒く塗られた頂点を含むこと」です。論理の講義を思いだしてみて、かつxを強調すればこれはこうなります:
$\begin{align} &(vは塗りかたxで白)∧(v∈S_x)\\ & \iff \\ &(vは塗りかたxで白)∧(T_{vi}たちのうち少なくとも2つが黒く塗られた頂点を含む) \end{align}$
すると、 $T_{vi}$ たちはvを含まないのでvとは関係なく、これら2つの事象は独立になります！この変形をしてはじめて先の推論を正しく進めることができます:
$\begin{align} &E_{x} [S_xの穴開き度] \\ &= \dots (←同様)\\ &= \sum_{v\in T} E_{x} [\chi(v\in S_x 、かつ、vは塗り分けxで白) ]\quad (←期待値の線形性)\\ &= \sum_{v\in T} E_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む、 \\ & \quad かつ、vは塗り分けxで白) ]\quad (←先の同値！)\\ &= \sum_{v\in T} E_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む)] E[χ(vはxで白)]\\ &\quad (↑独立性！)\\ &= \frac{1}{2}\sum_{v\in T} E_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む)]\\ & \quad (↑1/2の確率で白く塗られる)\\ &= \frac{1}{2}\sum_{v\in T} p_{x} [\chi(T_{vi}たちのうち少なくとも2つが黒い頂点を含む)]\\ & \quad (↑指示関数の期待値は結局確率)\\ \end{align}$
これではじめて、木に集中してものを考えることができるはずで、あとは解説どおりです(ここからはここからで木DPになれてないと苦しいのですが)。

おわりに

そういうわけで、解説のギャップ埋めみたいなことをしてみました。多分強い人はこのあたりのことが直感的にわかるのだと思うのですが、私ぐらいだと面くらいましたしひょっとしたら自力で解けた人でも「まあ大体1/2だし1/2で割っとけばいいっしょ～」という方もいたのではないかなと思います。こういうのを考えるのが競技に強くなるのに重要かどうかは知りませんが、納得いかないので考えてみました。

*1:弾倉が6発分ならですが

*2:いつのまにか確率変数の独立から事象の独立になっていますが、「その命題が成立したら1、そうでないとき0」という確率変数と同一視してください

2019-12-26

AngluinのL*アルゴリズムと機械学習(特にRNN)への応用

qiitaのほうにかきました

qiita.com

2019-12-06

ACMアカウントを使ってのO'Reilly Learning Centerへのログインができなくなったときには

ここ(https://learning.acm.org/e-learning/oreilly)にあるとおり、ACM(Association for Computational Machinery、計算機系の学会です)の会員はO'Reilly Learning Centerにアクセスする権利が特典としてあって、英語版のオライリーの本への電子アクセスの権利があります。

しかし、ある日読みたい本ができたのでアクセスしてみようとしたところ
https://twitter.com/ashiato45/status/1201797380116365312/
こんなバーが出てアクセスすることができませんでした。はじめはオライリーのほうに問いあわせたのですが「団体会員の場合はその団体のほうがあまり使ってない会員のアカウントを無効化することがあるからACMのほうに聞いて」と言われました。そこでACMのほうにreactivateをおねがいしたら無事にアクセスできるようになりました。どうも3ヶ月ログインがないアカウントは停止しているようです。

結論としては、

ACMアカウントを使ってのログインに問題が生じたら、オライリーの窓口ではなくてACMのほうに問い合わせましょう。
3ヶ月以内ぐらいの間隔でマメにO'Reillyにログインしましょう。

2019-10-25

concept latticeについて

杉山麿人先生のデータマイニングについての講義を受けていて、concept latticeのところ~~が講義の最後のほうTwitterしてたら分からなくなったので~~の理解を深めるためにぽちぽち調べたり考えたりした記録です。とはいえそんなにちゃんとは調べていないので定義とか間違ってたらごめんなさい。

定義は曖昧さがないように真面目にやっていますが、まあ例だけ拾っていけば読めると思います。

やりたいこと

データがこんな感じで(いまは8つ)与えられたとき、
f:id:sle:20191025172146p:plain:w100
X⊂{A,B,C,D}*1を含む行がいくつあるかを{A,B,C,D}の(包含で順序を入れた)ハッセ図に書き込むことにする。この数をfrequencyとよぶことにする。例えば、ABDのfrequencyは3*2。こんなかんじ:
f:id:sle:20191025172325p:plain:w300
あたりまえだが、書き込まれた数はハッセ図の上にいくにつれ小さくなっていくことになる(順序に関する反対向きの準同型)。この書き込まれた数の情報を保つようなコンパクトな表現がほしいし、またそれにまつわる数学的な構造を知りたい。

closed pattern

[定義: closed pattern]集合S(上の例だと{A,B,C,D}に関する部分集合全体のなすハッセ図とその上に書きこまれた頻度が与えられたときに、P(S)の部分集合Xが頻度nのclosed patternであるとは、Xが頻度nを持つハッセ図上のノード(その頻度が与えられたSの部分集合)の極大元集合のこと((これ別に講義で言われたことではないのだけれど定義が簡単になるので…)。適当な頻度nがあり、Xが頻度nのclosed patternのとき、単にXをclosed patternとよぶ。

例えば、頻度3を持つノードは上図でABD,AB,BD,B,Cがあるが、このうち上限をあつめると{ABD,C}になるので、頻度3のclosed patternは{ABD, C}である。上図ではclosed patternの元たちすべてが赤く記されている。

どの2つのclosed patternを取ってもそれらがdisjointであることは定義より明らか。

このclosed pattern全体とその頻度だけ覚えておけば、(closed patternに載っていないものを含む)どのノードについてもそこに書かれていた頻度を復元することができる。これは、大きい頻度nのclosed patternからすでに数が書き込まれているノードに出会うまで下がっていって、途中で出会ったすべてのノードにnを書き込んでいけばよいからである。例えば:
f:id:sle:20191025173917p:plain:w300
頻度7,5,4はすべて書き込まれているとして頻度3のノードを復元したいとする。Cから下がるともう{}なのでCに3を書き込んでCについては終了。ABDからスタートすると、AB,AD,BDが子となるが、ADには4が書き込まれているのでAB,BDが残りとなり、この2つに3を書き込む。AB,BDから同様に続ける…となる。

そういうわけで、closed patternの性質を調べてみたい。

contextとその演算

唐突に関係ない数学っぽい話になる。

[定義: context, object, attribute] 集合G,Mとその2項関係I⊂G×Mについて、(G,M,I)のことをcontextとよび、Gのことをobject、Mのことをattributeとよぶ。

例えば、*3 *4Gを男性の集合、Mを女性の集合とし、Iを「カップルになれる男性と女性とのペア全体のなす集合」とすれば、これはcontextになっている。

今回重要な例は、Gをデータのなす集合{ID1,…,ID8}とし、Mを{A,B,C,D}とし、Iを「ID gではmのビットが立っている」で定まる関係としたcontextである。例えば、ID3はAのビットが立っているので(ID3, A)∈Iである。

[定義: derivation] (G,M,I)をcontextとしたとき、A⊂Gのderivationとは{m∈M; 任意のa∈Aについて、(a,m)∈I}となるもののこと。B⊂Mのderivationとは{g∈G; 任意のb∈Bについて、(g, b)∈I}となるもののこと。
A⊂Gのderivation A'はMのsubsetだし、B⊂Mのderivation B'はGのsubsetなことに注意。反対側に行く感じ。

例えば上の男女の例で、A⊂Gを「男子サッカー部員全員」とするなら、A'⊂Gは「男子サッカー部の人なら誰とでもカップルになれる女子全体」となる。「男子サッカー部のカップルになれる人がいる女子全体」ではないことに注意する。

上のハッセ図の例なら、X={A,B}⊂G*5とするならX'は「AもBも1が立っているようなデータ全体」となり、X'={ID1, ID5, ID8}となる。反対に、Y={ID1, ID2}とするならY'は「ID1でもID2でもビットが立っているような要素全体」となり、これはAのみなのでY'={A}となる。

concept

[定義: concept] (G,M,I)をcontextとする。A⊂GとB⊂Mについて、A'=BとB'=Aがなりたつとき、(A,B)をconecptという。

まず定義についてだが、A'=BのA'⊃Bのほうは「任意のb∈Bについて、さらに任意のa∈Aについて(a,b)∈I」となり、A'⊂Bのほうは「任意のa∈Aについて(a, m)∈Iとなるようなどんなm∈Mについても、m∈Bとなる」である。反対側のB'=Aもまとめると、(A,B)がconceptとは

任意のa∈A,b∈Bについて(a,b)∈I
任意のa∈Aについて(a, m)∈Iとなるようなどんなm∈Mについても、m∈Bとなる
任意のb∈Bについて(g, b)∈Iとなるようなどんなg∈Gについても、g∈Aとなる

となる。

例えば上の男女の例なら、({男子サッカー部員全員}, {女子バレー部員全員})がconceptであるとする。上の条件を順に確認するなら

どの男子サッカー部員とどの女子バレー部員もカップルになれる
どの男子サッカー部員ともカップルになれるような女子は全員女子バレー部にいる
どの女子バレー部員ともカップルになれるような男子は全員男子サッカー部にいる

ということになる。(2)を反対向きに読んでみるなら「『こいつとカップルになれ』と言われたら絶対嫌だ、というような男子サッカー部員が一人でもいるような女子は女子バレー部員ではない」ということになる。単に男子サッカー部と女子バレー部はどのペアでもカップルになれて相性が良い(1の意味)というだけではなく、男子サッカー部も女子バレー部もそういう人たちを全員漏れ無く集めたような組織になっているという点ですごく相性が良くぴったりということになる。

上のハッセ図では、({ID1, ID5, ID8}, {A, B, D})はconceptになっている。確認すると

ID1はA,B,D全部が立っており、ID5もID8もそう。
ID1,ID5,ID8全部で立ってるビットを集めるとA,B,Dが全てで、これは{A,B,D}にちゃんと含まれている
A,B,D全部が立っているようなデータを集めるとID1,ID5,ID8が全てで、これは{ID1, ID5, ID8}にちゃんと含まれている

となり、ぴったりである。

性質として、定義からほぼあたり前だが次の一意性を確認する: (A1,B)がconceptで、(A2,B)もconceptなら、A1=A2である。(証明)(A1,B)がconceptなのでA1=B'であり、(A2,B)がconceptなのでA2=B'である。よって、A1=A2。(証明おわり)

ただし、「じゃあderivationとればいつでもconcept作れるじゃん、(B', B)はいつでもconceptじゃん」というのは嘘である。{B}'={ID1, ID5, ID8}だが、ID1,ID5,ID8で立っているビットを全部集めると{A,B,D}となり3番の性質に反する。ぴったりな相方組織が作れないような組織もあるのである。

conceptとclosed patternの関係

直前の例で出た{A,B,D}はたまたまclosed patternになっているが、実はこれは偶然ではない。また「ぴったりな相方組織が作れる」ということがclosed patternと関係している。次の関係がなりたつ:
[性質] (G,M,I)を(有限)ハッセ図のcontextとし、B⊂Mとする。(A,B)がconceptとなるA⊂Gが存在する<==>Bがclosed patternとなる。
(略証)(→)存在するとすれば上の性質からA=B'なので、(B',B)がconceptであるという意味になる。Bがclosed patternでないとしよう。Bより真に大きいビットの集合B2で、B2すべてが立っているようなデータの集合の大きさが|B'|であるものがあることになる。B2のビット全てが立っているようなデータはBのビットも全て立っているのだから、結局B2=B'ということになるが、これはB2がBより真に大きいということに矛盾する。(←)*6Bはclosed patternとする。この頻度はderivationの定義より|B'|である。(B',B)がconceptであることを示そう。片方は自明なので、B''=Bであることを示せばよい。つまり、「Bのビットが全て立っているようなデータ全てで立っているビット全体」がBと等しいことを言えばよい。このカギカッコ内の記述から、B⊂B''は明らかである。仮に等号がなりたたないとすると、B''はBより真に大きいことになる。B'''は「Bのビットが全て立っているようなデータ全てで立っているビット全体が立っているようなデータ全体」なので結局B'で、(B', B'')=(B''',B'')はconceptなのでこの証明の前半よりB''は頻度|B'|のclosed patternである。B''はBより真に大きく、頻度は同じ|B'|なのだから、これはclosed patternの極大性に反する。(証明おわり)

conecptとderivationでclosed patternを作る

concept (A,B)のBについて、B''はBより膨らみ、さらにB''''、B''''''とやってもB''と等しくなることが先の証明をヒントにするとわかり、つまりderivationを2回あてることでBを含む最小のconcept(の片割れ)、即ちclosed patternを計算することができる。これを使えば、下から順にclosed patternを作っていくことができ、closed patternの列挙ができることになる。うれしい。

参考にしたもの

杉山先生の講義:

https://mahito.nii.ac.jp/083d966012dc68108d44de2930dabbe9/Sugiyama_NII_datamining_2019_02.pdf

英語版WikipediaのFormal concept analysis:

Formal concept analysis - Wikipedia

*1:A,B,C,Dは単に名前の意味で使うかもしれないし、変数名の意味で使うかもしれないので適当に文脈で読んでください

*2:本当はデータの総数で割った値なんだけど、この記事で話をするときには特にいらない情報なので単に出現数ということにする。

*3:objectとattributeという名付けからして適当な例ではないのだろうけど数学的には

*4:そして現代的にはpoliticallyにあれなのだろうけれど、二部グラフの話をするときの定番なので…

*5:文字がかぶるのでかえました

*6:なんかいろいろグニャったのでまちがってるかも…そのうち見直しますごめん