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:なんかいろいろグニャったのでまちがってるかも…そのうち見直しますごめん

2019-06-01

(Z/2^nZ)*の構造(オマケに高校数学風クイズ)

これは何？

金子晃先生の「応用代数講義」の命題4.26の証明がよくわからなかったし、わかったにしても構成が具体的でなくやっぱりよくわからないので、本の証明をヒントに自分でもうちょっと具体的な証明をつけなおしてみた。
最後にこれを考えてたらできた高校数学風クイズもあるよ！

示す命題

n≧3とし、 $G=\mathbb{Z}_{2^n}^*$ とする。 $G\simeq C_{2^{n-2}}\times C_2$ となる。
ここで、 $G=\mathbb{Z}_{2^n}^*$ は $\mathbb{Z}/{2^n}\mathbb{Z}$ の乗法群である。

大事な観察

3の「2の羃」乗を2進法で表記すると、次のような法則が観察される:

$3 = \texttt{11}$ ←末尾の「1」と次の「1」との間に「0」は現れない
$3^{2^1} = 9 = \texttt{1001}$ ←末尾の「1」と次の「1」との間に「0」は2個あらわれる
$3^{2^2} = (3^{2^1})^2 = 81 = \texttt{1010001}$ ←末尾の「1」と次の「1」との間に「0」は3個あらわれる
$3^{2^3} = (3^{2^2})^2 = 6561 = \texttt{1100110100001}$ ←末尾の「1」と次の「1」との間に「0」は4個あらわれる

そういうわけで、i≧1について、 $3^{2^i}$ を2進法で表記したとき、末尾の「1」と次の「1」との間に「1」は $i+1$ 個あらわれるらしい。つまり、「1」が1つずつ左にずれていっているらしい。このことはあとでちゃんと示す。

したがって、 $3, 3^{2^1}, 3^{2^2}, \dots, 3^{2^{n-3}}$ の2進法表記を下n桁(ただしn≧3)とったものを考えるとき、そのとったものたちはすべて相異なる。例えば、

n=3なら、 $3 = \texttt{11}$ の2進法表記での下3桁は「001」で(1個しかないので当たり前だけど)相異なる。
n=4なら、 $3 = \texttt{11}$ の2進法表記での下4桁は「0001」、 $3^{2^1} = \texttt{1001}$ は「1001」でこの2つはやっぱり相異なる。
n=5なら、 $3 = \texttt{11}$ の2進法表記での下5桁は「00001」、 $3^{2^1} = \texttt{1001}$ は「01001」、 $3^{2^2} = \texttt{1010001}$ は「10001」でこの3つはやっぱり相異なる。
…

となる。

証明

まず、Gは $2^n$ 未満の奇数全体からなるので、位数は $2^{n-1}$ である。
「大事な観察」と、位数が2羃でありGの部分群の位数は2羃にならざるを得ない*1ことから3の位数*2はちょうど $2^{n-2}$ である。

ところで、 $2^{n-1}-1$ か $2^{n-1}+1$ との差は2なので、このうち少なくとも一方は3の倍数ではなく、したがって3の羃でもない。その3の羃でないほうをaとよぶことにする。aは(当然 $2^n$ のmodをとって) $a^2=1$ である。
$a\not\in \langle 3 \rangle$ であり、<3>の指数は2なので、G=<3>∪ a・<3>である。

群準同型 $\varphi\colon C_{2^{n-2}}\times C_2 \to G$ を、φ(0, 1)=a, φ(1, 0)=3で定める。これが同型であることを示そう。全射は $\phi(x, y)=3^x \cdot ya$ とG=<3>∪ a・<3>より明らかである。
単射も<3>∩a・<3>=∅に注意すれば簡単である。これで同型が示された。

これでこういうクイズが作れますね

高校数学風に、こういう問題が作れますね(多分うまく誘導作れば本当に高校数学の問題になるんですけど)。

431をn(正の自然数)乗して1024で割った余りを計算すると1になったという。そのようなnのうち最小のものを求めよ。ただし、431は511×81を1024で割った余りである。

答えは上の事実を使えばもちろん簡単で、511は512=1024/2から1を引いたものでかつ3の倍数でないので、上の証明で言うところのaとして選べる。さらに81のほうは3の4乗である。
よって、上の同型で431∈ $\mathbb{Z}_{1024}^*(=G)$ を飛ばすと、(φの逆をψと書くことにして)ψ(431)=(4,1)∈ $C_{256}\times C_2$ となる。
Gの方でn回羃をとることは、 $C_{256}\times C_2$ では両方の要素にn倍することに相当するので、n×(4,1)=(0, 0)となる最小のnを考えればよく、これは明らかに256/4=64である。よって答えは64。

*1:ラグランジュの定理

*2:3の羃の生成する巡回部分群の位数