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にログインしましょう。

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とは

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

となる。

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

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

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

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

  1. ID1はA,B,D全部が立っており、ID5もID8もそう。
  2. ID1,ID5,ID8全部で立ってるビットを集めるとA,B,Dが全てで、これは{A,B,D}にちゃんと含まれている
  3. 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の列挙ができることになる。うれしい。

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

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

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

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

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

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

(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の羃の生成する巡回部分群の位数

Ansible/Vagrantでubuntuを起動してaptするときにdpkgのlockのエラーが出るやつへの対処

Ansible/Vagrantubuntuを立ち上げて、そこにaptで必要なものをインストールしたい*1ということはあると思うのだが、起動直後だとよく、「dpkgのlockファイルがあって実行できない」というメッセージが出て失敗してしまうことがある。無視すれば当然後ろの命令がうまく行かない。

Googleで「ansible ubuntu dpkg」でぐぐると、結構「dpkgのロックファイルを削除する」とか「killallでdpkgを殺してしまう」というようなどう考えても行儀のいいとは思えない対処法が出てくる。実は私も以前はそれをやっていて、大方はうまくいくのだが沢山やっていると失敗するやつが必ずあらわれて、それらのイレギュラーへの手動の対処が大変で「Infrastrcuture as a codeとは…」という気分になりやってられない。

そもそもこの原因は、Ubuntuがデフォルトだと起動時に自動アップデートをかけるのが原因なので、アップデートが終わるまで待ってからこちらのしたいことをすればいいのである。
そういうわけで、wait_for fails on apt-get / aptitude lock-file in /var/lib/dpkg/lock · Issue #16593 · ansible/ansible · GitHubのようなものも試したのだが、ロックファイルがどうもこれだけとも限らないようで成功率が100%にはならなかった。いまのところ、「そもそもdpkgが起動してるかをみるのが直接的でよくない?」ということで、今はもっぱら

 while ps -A | grep dpkg; do sleep 1; done;

を先頭に挟むことにしていて、今のところは成功率100%である。何かもっと筋の良い方法、常識などあったら教えてください。

*1:例えばvagrant awsubuntuインスタンスを立ち上げて、そのあとVagrantで操作できるように向こう側でpythonをインストールしたいとか

Visual Studio 2017でOpenCV 2.4.3をビルドする

諸事情によりOpenCVのバージョン2.4.3を使いたくなったのだが、バイナリの配布が終了していたのでVisual Studio 2017 (Community)ビルドしたくなった。そのときにコケたことがあったので(未だに全ての問題が解決したわけではないが)メモしておく。

  1. OpenCVgithubのtags(Tags · opencv/opencv · GitHub)から2.4.3を探しzipをダウンロード(https://github.com/opencv/opencv/archive/2.4.3.zip)。
  2. ダウンロードしたファイルを展開。
  3. CMake(https://cmake.org/)のWindows版を起動し、2で展開したディレクトリ(私の場合「C:/Users/ashia/Downloads/opencv-2.4.3」)を「Where is the source code」に、「Where to build the binaries」にそのなかのbuildフォルダを指定する(私の場合「C:/Users/ashia/Downloads/opencv-2.4.3/build」)を指定する。buildディレクトリは存在しないが、あとで確認の上自動で作られるので問題ない。
  4. 「Configure」をクリックしてOKとかをポチポチする(多分VS2017を使ってコンパイルする設定にデフォルトでなっていると思うが、なっていなければ直す)。CMakeがそのコンピュータのビルド環境を検出してくれる。
  5. 真ん中のおおきい窓にコンパイルオプション赤いリストが表示されるので、必要な機能に応じてつけたりけしたりするはずだが、今回の私の用途ではそのままにしておいた。
  6. 「Generate」をクリックする。CMakeがそのコンピュータのビルド環境を見て指定したbuildフォルダに、OpenCVをVS2017を使ってコンパイルするために必要なファイルを揃えてくれる。
  7. buildフォルダのなかにOpenCV.slnができているので、VS2017で開く。
  8. そのまま「ビルド>ソリューションのビルド」を実行するが、maxやminが未定義だと怒られるので、怒られているファイルのヘッダの先頭に「#include 」を付け加える。
  9. もう一度やるとさっきのエラーは消える。正直気持ち悪いのだが、私が今回使う機能には関係ない部分だったので無視していた。これでbuildのbinフォルダには(ビルドが成功した分の機能の)dllファイルができているし、libフォルダにはlibファイルができている。

拡張ユークリッド互除法を行列で書く

拡張ユークリッド互除法で実際に不定方程式の解を求めるとき、私は行列算で書くのが好きなのですがあんまりそういう解説を見掛けないのと、実は私もそれを思い出すのにいちいち20分ぐらいかかってしまうという理由でここにメモしておきます。

拡張ユークリッド互除法での「代入」

拡張ユークリッド互除法で 11a+7b=1なるa,bを求める方法は、通常次のように「代入」を用いて説明されます:
まず、

  • 11÷7=1 あまり 4
  • 7÷4=1 あまり 3
  • 4÷3=1 あまり 1
  • 3÷1=3 あまり 0

とあまりを計算する。これらのうち、「あまり=(gcd)」となっている式までを上から「あまり=わられる数-わる数×商」の形に書き直す。

  • 4 = 11-7×1 (イ)
  • 3 = 7-4×1 (ロ)
  • 1 = 4 - 3×1 (ハ)

となる。これを下から順に代入して、

  • 1 = 4 - 3×1 (ハを持ってくる)
  • = 4 - (7-4×1)×1 (ロを代入)
  • = (-1)×7 + 2×4 (整理する)
  • = (-1)×7 + 2×(11-7×1) (イを代入)
  • = 2×11 + (-3)×7 (整理する)

これで、a=2、b=(-3)と求まった。

行列で書いてみる

が、数に数を代入というのが気持ち悪いし、「整理する」のところで何を「係数」と見做して整理していいのかよく分からなくなるので、しばらくすると簡単にやり方を忘れて困ってしまう。そこで、これを行列算で書き直してみる。

ユークリッドの互除法では、(割られる数, 割る数)というペアから(割る数, あまり)というペアを計算するという操作を繰り返す。例えば上の例では、(11, 7)→(7, 3)→(3, 1)→(1, 0)となっている。
このペアに注目して、上の4本の式を行列算で書き直してみる。すると、次のようになる。

  •  \begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}11\\7\end{pmatrix} = \begin{pmatrix}7\\4\end{pmatrix} (イ)
  •  \begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}7\\4\end{pmatrix} = \begin{pmatrix}4\\3\end{pmatrix} (ロ)
  •  \begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}4\\3\end{pmatrix} = \begin{pmatrix}3\\1\end{pmatrix} (ハ)
  •  \begin{pmatrix}0 & 1 \\\ 1 & -3\end{pmatrix}\begin{pmatrix}3\\1\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix} (ニ)

ペアの第2要素は第1要素に移るので、係数行列の1行目はかならず(0, 1)になり、2行目はあまりを求めるところなので、(1, -商)となっている。
しらべたかったのは、(11, 7)に何をかけていくと(1, 0)にできるかということなので、まず(イ)の両辺に(ロ)の係数行列をかけてみる。すると、

  •  \begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}11\\7\end{pmatrix} =\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix} \begin{pmatrix}7\\4\end{pmatrix} (イの両辺にロの行列をかける)
  •  =  \begin{pmatrix}4\\3\end{pmatrix} (ロを「代入」)

代入するにも、先の章とは違って行列の形が変な代入を防いでくれる。あとは同様のことをすればよく、少し考えると右から

  •  (ニの行列)(ハの行列)(ロの行列)(イの行列)\begin{pmatrix}11\\7\end{pmatrix} = \begin{pmatrix}1\\0\end{pmatrix}

となることがわかる。これはまさに我々がはじめ求めたかった形になっていて、答を求めるには左の行列積の連鎖を計算すればよい。

  •  (ニの行列)(ハの行列)(ロの行列)(イの行列)
  • =  \begin{pmatrix}0 & 1 \\\ 1 & -3\end{pmatrix} \begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}\begin{pmatrix}0 & 1 \\\ 1 & -1\end{pmatrix}
  • =  \begin{pmatrix}2 & -3 \\\ -7 & 11\end{pmatrix}

((ちなみにこれを手計算するときは2つずつ組にしてかけ算するとちょっと楽)あとはこの第1行をとって(あるいは両辺に(1, 0)をかけて)、a=2, b=-3がわかる。

まあこう覚えておくと、アルゴリズムにするときもちょっと思い出しやすいんじゃないかなあと思う。