pandasについて
(概要)
pandasは、Rのデータフレームのようなものを
python上で、動かすライブラリ。
(詳細)
Rの場合、さらに進化しているので
それに比べると、pandasは
少し洗練されていない感がある。
例えば、下記等。
(1)dplyrライブラリの様には、メソッドチェーンを実行できないこと。
(2)関数型言語で言う所の、flatmapが無く、追加要望のプルリクエストは否決されている。
(なんとなく、この部分は作成者の後進性にも見える。)
しかしながら、pythonの前処理では
現状デファクトスタンダードであるので
無視することはできない。
より良いライブラリが登場するまでは
工夫して使用していくしかない。
また、pythonでは、daskという並列処理に得化した
データフレームのライブラリがある。
使用できるapiが少なくなるので
そのままポーティングできる訳ではないが
チューニング時の逃げ道にはなる。
以下、工夫した点について書いていく。
(工夫点)
(1)欠損値について
数値で、欠損値が出た場合に、「nampy.nan」が当てられてしまう欠点がある。
「日にち」や「実行回数」など、浮動小数点数では本質的に表せない数値があり
後続の処理によっては、「nampy.nan」は不都合である。
まずいことに、「nampy.nan」が当てられると、その列の他の有効値が整数でも
すべて、floatに変換されてしまう。
(例えば、「5」→「5.0」となるが、これが後続処理で、繰り返し5回の意味だとすると、ループ構文でエラーとなる。)
この欠損値が発生するパターンは、２通りある。
・入力レコードリストに、元々欠損値がある場合。
・margeで外部結合した場合に、マスターに結合キーに当たるレコードが存在しない場合。
欠損値は、デフォルト値で埋める等するが
この場合の回避策として考えられることを以下に上げる
(a)pythonの言語機能で処理する
速度を落とさないように、pythonの内包表記などを使用して
前処理の前処理を作成する。
その場合に辞書を使用すると、外部結合相当の処理の
1レコード分の結合の計算量はO(1)となる。
つまり、ハッシュ計算だけで直接アドレスから値取得可能となる。
逐次処理となるが、daskを使用した場合と遜色ない速度がでると予想される。
(実験で確かめるべきだが、次の課題とする。)
(b)作業用の列を作成し、あくまでもpandasで処理する。
(あ)すべてのキーを作成して、それから作業用データフレームを作る
(い)作業用データフレームで、デフォルト値を対象列にセットする
(う)作業用データフレームを駆動表として、入力値のデータフレームを結合する
(え)入力値のデータフレームの値がある列値のみ、対象列にコピーする
上記(b)の方法は、少し難しい点がある。
上記(b)の方法は、少し煩雑であることがネックである。
人によっては、「floatに変換されてしまう」問題自体に対し
腹落ちするまでの理解が、中々得られないこともある。
(データサイエンスを志向する人たちの、集団で問題提起しても
大部分の人は、何が問題なの ? というふうである。
まあ、本処理が統計処理ならば問題にならないので
そう思ってしまうのも無理はないですが。)
あまりレベルが高くない人の場合
実装者中途半端な理解で実装してしまい
(b)の実装法は面倒くさい、あるいは汚い実装に思えてしまい。
注意指摘したとしても、ノーガードで
margeをしてしまう実装に改悪してしまいう
誘惑があるようです。
(人は、分からないものは、見えないものと考え
見えないものは、存在しないものと考え
結果無視することが多々あります。)
ノーガードの実装は、後続処理が
整数を求めているならばバグ実装なので
間違いであるが、事は簡単ではない。
他人の視野の狭さを矯正するのは
中々難しいので、自分を変えるしか
方法はないと思われます。
(結論)
上記理由で、(a)の前処理中の前処理を実装するのが得策と見える。
(おわり)
(実装例を挟みながら、レポートを書いたほうが良いが
今回 ~~は~~も、時間がないので省略する。追記するかもしれない。)
ところで、黒川先生訳本が出版される予定。
https://www.amazon.co.jp/dp/425412242X
黒川先生だから、よさげに見える。
下記のような本も出るみたい。
原題が「Pandas for Everyone」だから
直訳すると、「みんなのPandas」になるけど
https://www.amazon.co.jp/Pythonデータ分析／機械学習のための基本コーディング！-pandasライブラリ活用入門-impress-top-gear/dp/4295005657/ref=sr_1_5?s=books&ie=UTF8&qid=1546782535&sr=1-5&keywords=pandas
AIの定義について
この半年の中で、AIについての知識を
INPUTしていく中で、自分の中での
AIの定義に対する認識に変化ありました。
具体的に言うと、半年前までは
現在仕事で行っている数理最適化などは
AIとは呼べない。
また、AIはディープラーニングなどを
言うのであって、機械学習の中でも
統計学よりの多変量解析や単に平均値をとる様な
回帰などはAIでは無いと考えていました。
こう考えていた理由は、下記に出てくる
(定義その１)が有ったからかもしれません。
こんな風に考えるのは、視野を狭くするだけで
つまらない考え方に思えてきたので
以下、考察したいと思います。
ところで、人工知能の定義は
世の中にいろいろとあります。
ここでは、面倒なので、
哲学的な考察には立ち寄らずに
ものづくり寄りの話をします。
(定義その１)
人工知能とは
まだ、確立できていないもので
人間の知能を模倣できる、人工物をいう。
これは、研究者には、良いだろうが
実際にモノづくりをする人間からすると
意味の薄い定義である。
この定義では、例えば
数式処理や定理の自動証明、あるいは
ルールに基づいて質疑応答するプログラム
(人工無能という)は人工知能でないことになる。
しかも実際そういう扱いを受けている。
数式処理や定理の自動証明は、十分に知的な
行いであり、小中学生では、まだ十分にできない
思考であるので、これを知能のふるまいではないと
するのは、すこし了見が狭いと思う。
この定義を採用してしまうと、例えば
最近はやりのディープラーニングも
確立されていまうと人工知能ではなくなってしまう。
(3年くらい先か ?)
囲碁ソフトも、将棋ソフトも、もちろん
人工知能でないということになる。
これでは、永遠の逃げ水である。
人工知能の領域が、いつも空っぽの
洞窟になってしまう。
研究者なら良いが、研究者以外の立場では
この定義では、あまりにもヒドく
使えない言葉になっしまう。
実務者にとっては、この定義の
「人工知能」は、存在価値がない。
ただし、この定義にも利点がある。
たとえば、電卓や事務処理計算が
人間の能力を遥かに超えていたとしても
これらを人工知能とは呼ばない。
この点に関しては、理に適っている。
もう少し、単語の字面上で意味を考えると
単に機能面から、捉えた方が実務者にとって
意味がある定義になる。
(定義その２)
人工知能とは
人間の行う思考を、機械上で再現したものである。
この定義なら、そこまで難しく考える必要がなくなるが
さらに「思考」とは何かを考える必要がある。
ここで、現状では人の感情を再現するのは
難しそうなので、感情についての議論は無視して
定義の詳細をさらに考えてみる。
(定義その２の更に詳細)
思考には、以下の３つの要素があると言われている。
(A)演繹
(B)帰納
(C)アブダクション
ABCの具体例を挙げていく
(A)
演繹とは、例えば、下記のようなものが挙げられる。
大前提、小前提 ⇒ 結論
「人は死ぬ存在である」、「ソクラテスは人である」 ⇒「ソクラテスは死ぬ」
大前提：人は死ぬ存在である
小前提：ソクラテスは人である
(「デカルトは人である」でも良い)
結果 ：ソクラテスは死ぬ
演繹推論は、正しい前提からは、常に正しい結果が得られる。
間違う事が、無い推論である。
これに対して、帰納やアブダクションは、いつも正しいとは限らない。
(B)
帰納とは、例えば、下記のようなものが挙げられる。
{小前提 ⇒ 結論}のリスト ⇒ 大前提
「ハトは空を飛ぶ」「アヒルは空を飛ぶ」「カモメは空を飛ぶ」 ⇒ 「鳥は空を飛ぶ」
小前提 ⇒ 結論：「ハトならば空を飛ぶ」「アヒルならば空を飛ぶ」「カモメならば空を飛ぶ」
結果 ：「鳥は空を飛ぶ」
これは必ずしも正しくない。
なぜなら、ペンギン、キウイ、ダチョウあたりは、飛べない鳥だからである。
(C)
アブダクションとは、例えば、下記のようなものが挙げられる。
大前提、結論 ⇒ 小前提
「すべての鳥は空を飛ぶ」、「ツバメは空を飛ぶ」 ⇒ 「ツバメは鳥はである」
大前提：人は死ぬ存在である
結果 ：ツバメは空を飛ぶ
小前提：ツバメは鳥はである
これも必ずしも正しくない。
例として次が挙げる
「すべての鳥は空を飛ぶ」、「トンボは空を飛ぶ」 ⇒ 「トンボは鳥はである」
また、この推論は、デバッグ時によく行う推論である。
演繹推論なら
「アリバイがある容疑者は犯人ではない」「Aにはアリバイがある」 ⇒ 「Aは犯人である」
だが、いつも使える前提がそろっているとは限らない。
たとえば、次のような場合である。
「アリバイがある容疑者は犯人ではない」「Aにはアリバイがない」 ⇒ 「Aは犯人であるか不明」
ここから、アブダクションなら、状況証拠を積み上げて推論していく
(アブダクション推論その1)
「犯人のものとおもわれる血痕の血液型とAの血液型が一致する」 ⇒ 「Aは犯人である」
これで、犯人にされたら溜まったもんではない。
だが、Aが犯人である確信度は少し上がった。
(アブダクション推論その2)
「凶器に付着した指紋とAの指紋が一致した」 ⇒ 「Aは犯人である」
Aが犯人であることは、うごかしがたくなった、本当に犯行時に付いた指紋なのだろうか ?
(デバッグ時も、この様な状況証拠から
バグの原因を割り出している。
デバッグの場合、まちがって推論しても
大したことではないので、いくぶん雑に推論している。)
(上記ABCに対して)
AIブームの1期目は、この演繹のみが、AIの対象と考えられていたようである。
AIブームの2期目は、演繹と帰納と、ニューラルネットワークなどの
統計的、近似的な方法論が入ってくる。
(今回の)AIブームの3期目は、論理ベースの演繹はAI範疇に入れない
かつ、帰納の部分でも論理ベースの物もAIではないとされ
ニューラルネットワークや、統計的機械学習がAIなんだと喧伝されている。
この3期目の態度は、おかしいことに見える。
人間は、論理的に考えていないと言う話も
よく聞くが、その意味は人間は常に論理のみで考えて
いる訳ではないという意味で、論理的に考えることも
人間の思考の内であるのは間違いない。
この意味で、ルールベースのAIを
すべて外すのは間違いだと考えられる。
何度も例に出しますが、定理証明系で
出た定理の証明結果に本当に
知性を感じられませんか ?
チェスプログラムの出した、名人を負かす
手を見ても、知性を感じられませんか ?
何も、電卓に知性を感じろと言う
話ではありません。
その意味で、やはり(定義その1)は
極端すぎる定義だと考えなおしました。
(上記とは別次元の抽象化の話)
単に、帰納やアブダクションの区分けでは
捉えきれない重要な観点がある。
ここで、例を考えてみる
偉大な位、頭の良い人の特徴は、何かと考えると
抽象化・一般化の能力が高い人が、そうだと考えられる
例えば、ニュートン大先生は、なにも無い所から
f = ma
を思いついた。
fは力で、mは重さ、aは加速度であり
mの重量の物体に、力fを加えた時には、力の方向に
aの分だけ加速する。
さらに、加速度などを定義するのに必要な
微分の考え方を、発明しているのである。
これで、森羅万象のモノの動きを記述する
言葉(力学)が誕生し、森羅万象のモノの動きを
管理し、予測できるようになった。
(細かいことを言うと
原子半径以下の微細な世界や光速に
近い世界は記述できないが
今回の議論とは無関係なので省略)
ニュートン大先生は、無から有を生んでいる天才である。
このニュートンの行為は、思考の内
帰納に属し、一般化・抽象化(捨象)といわれる。
一般化・抽象化は、上記の通り重要だが
帰納ならば、一般化・抽象化だとは言えない。
それに対して、帰納に属するものとして
別にディープラーニング等の統計を用いた機会学習がある。
大まかに考えると、ディープラーニングなどは
抽象化・一般化とは言えない。
なぜならCNNの結果を、ルールとして演繹の前提条件に
使用することなど、到底無理で考えられないことである。
つまり、ディープラーニングは何も一般化していない。
ただ単に、光によって青写真に風景が写しこまれるのと同じで
青写真での光の役割を、学習データが担っているだけである。
ディープラーニングで得られた事実を
演繹の前提条件に使用することは不可能である。
ディープラーニングは、現実をそのままコピーしているだけである。
ディープラーニングで、特定の因果律内の予測はできるが
何も一般化していないので、特定の目的にしか使用できない
上で挙げた「f = ma」とは大違いである。
一方、抽象化・一般化されたルールならば
それを使用して、さらに思考を深化させることが可能となる。
いわゆるニュートンの巨人の肩に乗ると言う話である。
そうだとしたら、抽象化・一般化を
機械上に実現する方法はないのだろうか ?
調べた範囲では、全く無い訳ではないものの
現在、抽象化・一般化の方向の人工知能研究は
行われてはいるが、初歩的なもの以外
あまり成果が出ているとはいえない。
演繹に使用できる、前提となりうる
ルールを抽出する処理を作る方法は
今後の課題と見られる。
この「抽象化・一般化」は難しいとすると
帰納と演繹を組み合わせて
シームレスに実行可能なAIプログラムを
考られないだろうか ?
ここで話を脱線させる。
帰納のディープラーニングの使用例で考える。
人間は、ディープラーニングのような
当てずっぽう、山勘のみで行動している訳では無い。
ディープラーニングでは、どうなっているのか見てみる。
(あえて、ダメな部分に着目する。
ダメダメだと言うつもりは無い。)
現状の機械学習で言うと、google翻訳のように
RNNを使用した機械翻訳では次のようなことが起こる。
(a)訳せない部分を何も言わずに、すっ飛ばすことがある。
(たぶん、学習データにヒットするパターンが無い。)
(b)一見正しそうな流暢な日本語だが、文章を読んでみると意味不明。
(たぶん、翻訳対象の分野がニッチで、学習データに現れない分野。)
(c)中学生でも間違えようがないisとisn'tを混同して
文意を逆の意味で訳す
(たぶん、「is=isn't」とすると、学習データにヒットするから
それで近似した。
ただし、簡単な構造の文で、この現象が起きる事は無い。
だから、「中学生でも出来る」は、少しウソがあります。)
まだ、このレベルでは知能と呼べない。
十分な学習データと計算量が有るならば
上記問題は起きないかもしれない。
しかし、そんな誰が用意できるのか分からない理想のデータと
有り余る計算パワーが有る理想世界は、空想上、机上の
世界であり要求する方が無理である。
(そもそも、人間の歴代の大学受験生を
含む英語学習者は極わずかな
学習データで機械学習を上回る訳を出力する。)
さらに、ディープラーニングでは
itとかhe、she、theyなどの
照応関係を捉えられない。
仕組み上、根本的に無理があると思われる。
たとえば、単語の数個前までしか見ない
RNNのアテンションでそれを捉えろという
方が無理である。
しかし照応関係は、部分的には
小学生の国語でも出るレベルの問題である。
それが、RNNのようなディープラーニングでは
根本的にできない課題になる。
以上から考えると
googleの人が言っているように
現状の仕組みだけでシンギュラリティが
可能になるとは、到底考えられない。
(個人の意見なので、絶対正しいとは言えないです。
googleの人と、この部分の意見は一致します。
ただ、その対策では見方が違います。)
上記を踏まえて話を戻すと
現状では、下記(X)(Y)(Z)のように考えられる。
(X)今流行の人工知能といわれる、機械学習(ディープラーラング等)は
人間の思考の一部のみしかシミュレートしていない。
(Y)機械学習(ディープラーラング等)は、特定目的でしか
人間を超える存在になっていない。
⇒いわゆる、弱いAIと言うやつで、足の代わりをする
車や自転車の別用途版になるので、どうということは無い。
電卓のように、人間の機能の一部を補助するものである。
上記(定義その1)を採用すれば、そのうちAIでなくなる分野に見える。
(Z)高度な思考は、統計データで予測するだけの
山勘シミュレータでは、無理があるとおもわれるが
現在のコンピューターも、人間を超える能力で補佐してくれているのと同様に
今流行の人工知能も、新たな便利な機能を提供してくれるばずである。
(経験と勘の、職人芸は、すべて模倣可能かもしれない。)
話を戻し、上記を踏まえて
以下の問題を考える。
帰納と演繹を組み合わせて
シームレスに実行可能な
AIプログラムの具体策を考える。
その場合、下記の性質を利用したい。
(1)演繹には、正しい前提があれば
間違いの無い推論が出来る。
(2)機械学習には、近似を行い桁を落とすことにより
計算量を落として、大雑把な解を出すことができる。
この時、(1)の演繹は、大体において
木探索問題になり、計算量の爆発に結びつき易い。
いわゆる、np問題になってしまう。
AIでの典型例で言うと、フレーム問題になる。
それに対し、機械学習系の数値計算では
例えば、単精度に落とす、データ量を絞り込む等をして
計算量は端折り、とりあえずの予測値を、時間内に出せる。
これを利用し、演繹時の木探索問題の枝刈りをする等の
方法が考えられる。
今は、具体例を挙げられないが
これから工夫して、事例を挙げていく
予定である。
Haskellでラマヌジャン数
見た目がきれいなバージョンがあります。
https://qiita.com/zeal1483/private/69689dd8a68903932170
第4回『Haskellによる関数プログラミングの思考法』読書会に参加してきました。
https://sampou.connpass.com/event/66242/
そこで、ラマヌジャン数をhaskellで求める方法として以下が上がりました。
http://takeichi.ipl-lab.org/~onoue/pub/jssst01.pdf
10 -- Finding Ramanujan numbers
11
12 ramanujan :: [((Int,Int), (Int,Int))]
13 ramanujan = [(x,y)|(x,y)<-zip s (tail s),
14 sumcubes x == sumcubes y]
15 where s = fsort sumcubes 1
16
17 sumcubes :: (Int,Int) -> Int
18 sumcubes (a,b) = a^3 + b^3
20
21 fsort :: ((Int,Int) -> Int) -> Int
22 -> [(Int,Int)]
23 fsort r k
24 = (k,k) : fmerge r [(k,b)|b<-[k+1..]]
25 (fsort r (k+1))
26
27 {-
28 Two argument lists should be infinite,
29 so there is no definition for null list.
30 -}
31
32 fmerge :: (a->Int) -> [a] -> [a] -> [a]
33 fmerge r (x:xs) (y:ys)
34 | r x <= r y = x : fmerge r xs (y:ys)
35 | otherwise = y : fmerge r (x:xs) ysしかし、下の様なナイーブな方法よりは、早いですが
1000個のラマヌジャン数を求めるなどすると、遅いことがわかります。
rmNum n = [(e,a,b,c,d)|e<-[28..2*n^3]
,a<-[1..n]
,b<-[a+1..n]
,e == a^3 + b^3
,c<-[a+1..n]
,d<-[c..n]
,e == c^3 + d^3]遅い理由は、下記のフィボナッチ数列の求め方が遅い理由と同じように思えます。
fib n = fibs !! n fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Haskellの神話
http://d.hatena.ne.jp/kazu-yamamoto/20100624/1277348961
フィボナッチ数列の遅い理由は、上記リンクによると
計算(サンク?、算術木?)が消せないこととあります。
(この遅い理由が、計算が消せないとなっていることについては
自分には、なぜそうなのかが、明瞭には分からないです。
空間計算量や、時間計算量ならば、直感的に分かります。
例えば、メモリの専有領域の問題なら、限界を超えると
スワップが発生し、ディスクIOが保存と取込で2重に発生するから
速いメモリとのやり取りから、遅いディスクとのやり取りが加わり
そのスピード差から、圧倒的に速度が違うことは、明らかです。
また、時間計算量の話は、計算に物理的に時間がかかるので
これも、明らか。
最初のナイーブな書き方で遅い理由だと思われる。
計算が消せないと、なぜ遅くなるのかのメカニズムが見えない。)
これとは別に問題点として
a^2+b^3=c^3+d^3=e^3+f^3=kとなるような
要件を満たす(a,b),(c,d),(e,f)とkが存在することがあります。
例えば、k=87539319,(167,436),(228,423),(255,414)
連続する2つの組で捉える方法では、これを捉えられません。
(これは、groupByやgroupを使用することで、簡単に対応できます。)
読書会の時に、山下さんが、言われた
x+y=kをk=[1..]として進めていく方法の方が
実装してみると明らかに速く
1000個のラマヌジャン数を求めても
苦にはならないくらい十分にスピードがあります。
ここで、実装に入る前に、実装方針の説明をしてみます。
単に、x+y=kをk=[1..]で進めていくと、大小関係がわからない。
(読書会中に、議論になっていたとおもう)
そこで、区間を(1,2]、(2,4]、(4,8]、(8,16]、(16,32]...と区切っていく
その内の(n,2n]と(2n,4n]を考える。
そうすると、下図のように大小関係がはっきりする。
図の(n,2n]上のラマヌジャン数を考えると
点線x^3+y^3=n〜x^3+y^3=2nの範囲を考えれば良い
A:∫(x,y)dk, x+y=k、ただし積分範囲( n,2n]
B:∫(x,y)dk, x+y=k、ただし積分範囲(2n,4n]
f(x,y)=x^3+y^3
とおく
{(x,y)|(x,y)∈A∪B} <= MAX( {f(x,y)|(x,y)∈A} )
となる(x,y)を取れば、図の②を上限とする領域がとれる。
下限の④については、Aの1つ下の階層O(オー)を考えればよい。
O:∫(x,y)dk, x+y=k、ただし積分範囲(n/2,n] (nが偶数の場合)
O:x+y=0、x^3+y^3=0として、下限値0をとる (nが奇数、すなわち1の場合)
これに対して、下記のように取れば、下限を押さえられる
{(x,y)|(x,y)∈A∪B} > MAX( {f(x,y)|(x,y)∈O} )
以上から、上図の斜線部を1単位として
n = [2^k| k<-[1..]]
を展開して、足し合わせることによって
ラマヌジャン数の探索範囲を敷き詰めることができる。
実装は、以下の通り。
makeSearchAreaで、上図の斜線部を求めている。
import Data.List
-----------------------------------------
-- x + y = n 上の正数値列挙
-- > line 8
-- > [(1,7),(2,6),(3,5),(4,4)]
-----------------------------------------
line n = [(a,n-a)|a<-[1..n-1],a<=n-a]
------------------------------------------------------------------
-- 高さ(a^3 + b^3)付与
-- > estLine 8
-- > [(344,1,7),(224,2,6),(152,3,5),(128,4,4)]
------------------------------------------------------------------
estLine n = map cubeNumNum (line n)
where cubeNumNum (a,b) = (sumCubes (a,b), a, b)
------------------------------------------------------------------
-- 2n〜4nの区間の等高線を束ねて面にする
-- (これを等高線の層と言う事にする)
-- > sekibun (2, 4)
-- > [(9,1,2),(16,2,2),(28,1,3)]
-- s: 2^n (2の指数乗)
-- e: 2*s
------------------------------------------------------------------
sekibun (s, e) = sort (concatMap estLine [s+1..e])
------------------------------------------------------------------
-- 探索領域をつくる
-- > makeSearchArea 1
-- > [(9,1,2),(16,2,2),(28,1,3)]
-- > makeSearchArea 2
-- > [(35,2,3),(54,3,3),(65,1,4),(72,2,4),(91,3,4),(126,1,5),(128,4,4),(133,2,5),(152,3,5),(189,4,5),(217,1,6),(224,2,6),(243,3,6),(250,5,5),(280,4,6),(341,5,6),(344,1,7)]
------------------------------------------------------------------
makeSearchArea n = filter (\(x,y,z) -> min < x && x <= max) concat2Part
where -- 上層・中層・下層
fstPart = sekibun (n, 2*n)
mdlPart = sekibun (2*n, 4*n)
lstPart = sekibun (4*n, 8*n)
-- 上界・下界
min = fst3 (last fstPart)
max = fst3 (last mdlPart)
-- 連続した上位2つの等高線の層を束ね、整列する
concat2Part = sort (mdlPart ++ lstPart)
------------------------------------------------------------------
-- ラマニュジャン数(等高線の層の指定)
-- > rmNumRange 2
-- > []
-- > rmNumRange 4
-- > [[(1729,1,12),(1729,9,10)]]
-- > rmNumRange 8
-- > [[(4104,2,16),(4104,9,15)],[(13832,2,24),(13832,18,20)],[(20683,10,27),(20683,19,24)]]
------------------------------------------------------------------
rmNumRange n = getRmNums (makeSearchArea n)
------------------------------------------------------------------
-- searchArea上のラマヌジャン数取得
------------------------------------------------------------------
getRmNums searchArea = filter isDuplicate (groupBy eq searchArea)
where -- 等高線上の点か ?
eq p q = fst3 p == fst3 q
-- 複数要素があるか ?
isDuplicate xs = length xs > 1
------------------------------------------------------------------
-- ラマニュジャン数
-- > take 1 rmNums
-- > [[(1729,1,12),(1729,9,10)]]
-- > take 2 rmNums
-- > [[(1729,1,12),(1729,9,10)],[(4104,2,16),(4104,9,15)]]
-- > take 3 rmNums
-- > [[(1729,1,12),(1729,9,10)],[(4104,2,16),(4104,9,15)],[(13832,2,24),(13832,18,20)]]
------------------------------------------------------------------
rmNums = concatMap rmNumRange ninoshisu
------------------------------------------------------------------
-- 補助関数
-- 2の指数の系列を生成
-- > ninoshisu 8
-- > [2,4,8,16,32,64,128,256...]
------------------------------------------------------------------
ninoshisu = map (\m -> 2^m) [1..]
------------------------------------------------------------------
-- 補助関数
------------------------------------------------------------------
fst3 (x,y,z) = x
sumCubes (a,b) = a^3 + b^3上層・中層・下層の3つを、それぞれで求めているので
無駄に見えるかもしれない。
where -- 上層・中層・下層
fstPart = sekibun (n, 2*n)
mdlPart = sekibun (2*n, 4*n)
lstPart = sekibun (4*n, 8*n)iterateを使えば、上層を、それぞれで求めることになるが
体感的には、速度は上がらないようです。
import Data.List
-----------------------------------------
-- x + y = n 上の正数値列挙
-- > line 8
-- > [(1,7),(2,6),(3,5),(4,4)]
-----------------------------------------
line n = [(a,n-a)|a<-[1..n-1],a<=n-a]
------------------------------------------------------------------
-- 高さ(a^3 + b^3)付与
-- > estLine 8
-- > [(344,1,7),(224,2,6),(152,3,5),(128,4,4)]
------------------------------------------------------------------
estLine n = map cubeNumNum (line n)
where cubeNumNum (a,b) = (sumCubes (a,b), a, b)
------------------------------------------------------------------
-- 等高線を束ねて、面にする(これを等高線の層と言う事にする)
-- > sekibun (2, 4)
-- > [(9,1,2),(16,2,2),(28,1,3)]
------------------------------------------------------------------
sekibun (s, e) = sort (concatMap estLine [s+1..e])
------------------------------------------------------------------
-- 次のラマヌジャン数取得
-- > get6th $ next (1, 0, 0, [], [], [])
-- > []
-- > get6th $ next $ next (1, 0, 0, [], [], [])
-- > []
-- > get6th $ next $ next $ next (1, 0, 0, [], [], [])
-- > [[(1729,1,12),(1729,9,10)]]
-- > get6th $ next $ next $ next $ next (1, 0, 0, [], [], [])
-- > [[(4104,2,16),(4104,9,15)],[(13832,2,24),(13832,18,20)],[(20683,10,27),(20683,19,24)]]
------------------------------------------------------------------
next (n, min, max, fstPnl, mdlPnl, _) = (2*n, max, nextMax, mdlPnl, lstPnl, rmNums)
where lstPnl = sekibun (4*n, 8*n)
-- 次の上界
nextMax = fst3 (last lstPnl)
-- x^3 + y^3の上下の、上界の等高線を考慮して検索エリア作成
searchArea = makeSearchArea (min, max) mdlPnl lstPnl
-- searchArea上のラマヌジャン数
rmNums = getRmNums searchArea
------------------------------------------------------------------
-- 補助関数
-- 上位2層を結合して、区間で絞り込む
------------------------------------------------------------------
makeSearchArea (min, max) mdlPnl lstPnl = filter p (sort (mdlPnl ++ lstPnl))
where p (x,y,z) = min < x && x <= max
------------------------------------------------------------------
-- 補助関数
-- searchArea上のラマヌジャン数取得
------------------------------------------------------------------
getRmNums searchArea = filter isDuplicate (groupBy eq searchArea)
where -- 等高線上の点か ?
eq p q = fst3 p == fst3 q
-- 複数要素があるか ?
isDuplicate xs = length xs > 1
------------------------------------------------------------------
-- ラマニュジャン数
-- > take 1 rmNums
-- > [[(1729,1,12),(1729,9,10)]]
-- > take 2 rmNums
-- > [[(1729,1,12),(1729,9,10)],[(4104,2,16),(4104,9,15)]]
-- > take 3 rmNums
-- > [[(1729,1,12),(1729,9,10)],[(4104,2,16),(4104,9,15)],[(13832,2,24),(13832,18,20)]]
------------------------------------------------------------------
rmNums = concatMap get6th $ drop 3 $ iterate next (1, 0, 0, [], [], [])
get6th (n, min, max, fstPnl, mdlPnl, rmNums) = rmNums
------------------------------------------------------------------
-- 補助関数
------------------------------------------------------------------
fst3 (x,y,z) = x
sumCubes (a,b) = a^3 + b^3
『ゼロから作るDeep Learning』読書会＠高円寺(4)その3
(7shiさんに聞きたいこと)
下記のリンクで、あの時間に見えてきたことは
http://playground.tensorflow.org/
内容的には下リンク内の下記文言のことと
同じと思うけど、あってますか ?
https://rekken.g.hatena.ne.jp/murawaki/20161017/p1
>>引用開始
システムの中身を直感的に説明するのは難しい。LeCun 御大の例えをもじって、ノブを使った説明を試みる。機械翻訳というブラックボックスには、上部と下部に大量の穴があいていて、それぞれ入力と出力に対応する。上部の適切な穴に水を注ぐと、下部の適切な穴から水が出てくる。上部と下部の穴の間には複雑にからまったパイプがあり、途中で分岐 (というより分身) したり合流したりするし、途中に水を貯めている箇所があったりもする。そういう箇所にはノブがあって、水の流れを制御する。実際には、量が増幅されたり、負の値をとったりするので、水で例えるのは微妙だけど。
(中略)
学習とはノブを調整すること。ノブを適切に調整していないと、別の穴からちょろちょろと水が漏れたりする。正しい穴だけから水が出るようにノブを調整する。こういった階層の深いシステムであっても、充分な教師データを与えれば適切にノブを調整できることがわかった。それが深層学習とよばれているもの。とはいえ、途中を流れている水を見ても、何が起きているのか人間には (システム設計者ですら) さっぱりわからない。
そろそろノブの例えが厳しくなってきたのでここでやめにするが、最後に一つ付け加える。システム内部は、水の流れが多いか少ないかという数量で制御されている。確かに入り口と出口は離散的だけど、中は連続値で支配されている。記号の出る幕はない。
引用終了<<
この例えの文の内容以上のことは
具体に見えるという点以外は
自分には、同じに見えてしまいます。
playground.tensorflow.orgのリンクは
面白いと思います。
ですので、価値云々の話ではなく
自分が話が見えていないのではないかということに
関して、なにが違うかを聞きたいのです。
話は変わります。
上記の機械学習の水での例えの文で
自分が気になる点を抜き出すと
>途中を流れている水を見ても、何が起きているのか人間には
>(システム設計者ですら) さっぱりわからない。
ここの部分が、機械学習の重要な性質というか
限界に思えます。
昔、ninetiesさんの数学講座のあとで
7shiさん、「ハンドル名を覚えていない」さん、alumicanさん、自分
の懇親会で、ninetiesさんが
学習した内容は、誰にもわからない。
引き継いで応用していくことはできないから
人間世界のように、単純に理論を発展展開さ
せることはできない ?
というようなニュアンスの話を聞いた記憶があります。
自分のフィーリング解釈では、ざっくり
「機械学習は、人間世界でいうところの
暗黙知しか獲得できない。」
ということなんじゃないかと思いました。
人間なら、暗黙知を形式知に変換して
抽象化し、例えば数式などにしてから
書物の形にして、引継ぎ、発展していけます。
ニュートンの「巨人の肩の上に乗る」
といわれるやつです。
更に妄想すると、定理の自動証明なども
暗黙知だけでは、どうしようもできなくて
なにか、ブレークスルーが必要なんじゃないかと?
機械翻訳についても、文脈理解が必要なので
(機械学習で、画像と同じパターン認識で
文法の様なものも、見えてくるようですが)
文法をとばして、文脈まで見えるように
ならないんじゃないかと思います。
googleは、少なくとも、日本語文法は無視する
と宣言していて、アルゴリズムの力と火力で
単語列のパターンを対応付けて
google翻訳している模様。
ブレークスルーを見つければ
彼らを、出し抜けるかも !?
『ゼロから作るDeep Learning』読書会＠高円寺(4)その2
⇒発言しなかったが、思ったこと
ニューロンというと、言葉の意味が文脈でかなり
変わるので、掲題のような説明に使われるのは
なんとなく嫌な感じがした。
神経学者や、認知科学者のような
実用的観点ではなく、人間の現実的モデルに関心を
持っている層は、ニューラルネットワークと(脳細胞という
意味での)ニューロンとは、マッタク違うというのが
共通認識(常識的)になっていると、何かで見たことがあります。
ニューラルネットワークでは、どうも人間の神経系のモデル
としては、役にたたないとのこと。
昔は、同じと思って研究していたことは確かなようですが。
直感的に、人の思考と機会学習では動きが違うし
機械学習は、学習効率がかなり悪いと思います。
機械翻訳などについて言えば、最低100万コーパス位の
教師データが無いと、まともな結果が得られないとありますが
中学・高校の英語で習うテキストで100万コーパスは無いです。
学生用の英語辞書でさえ、100万コーパス無いのではないでしょうか?
これで、一昔前の学生は、受験英語でラッセルなどの難解な文章
を読まされ、テストに回答させられたんです。
人間の方が、相当凄くないですか?
また、囲碁の世界チャンピオンに勝った話ありますが
(裏付けのある確かな情報ではないですが
たぶん電気代だけで)2億円(ドルだったかな?)を溶かして
半年とか1年とかをかけてgoogleの火力のすごさで
やっと到達したと聞きました。
ニューロンとニューラルネットワークは別ものという話は
直感的に十分納得できる話だと思います。
実用的な人工知能を作りたいという機械学習系の話位でしか
ニューラルネットワークが登場しないので
文脈依存にならなく、一意に意味がとれるので
ニューロンという言葉を重要な説明の箇所に
使ってほしくないと個人的に思いました。
『ゼロから作るDeep Learning』読書会＠高円寺(4)
『ゼロから作るDeep Learning』読書会＠高円寺(4)
https://koenjidl.connpass.com/event/56139/
に参加してきた。
参加者で、気になった発言を列記してみる。
以下、概ね時系列で列挙する
(1)なぜ、線形領域しか扱えない線形分離器を重ね合わせると
非線形領域を扱えるようになるのか ?
⇒自分の不規則発言で、答えのつもりで(2)を発言
(2)行列で線形分離をする決定面(y = ax + b)を変換かけるのだから
非線形にできるのは不思議ではない。
(「例はたくさんあるから不思議におもわなくても
良いんじゃなかな?」という話
他のジャンルでも変換で複雑な式に変換する例は
あると思う。
例えば
線形ではないが、地動説流の惑星の楕円起動から
天動説流の時間tを含むtの6次式だったか
8次式だったか定かでないが
複雑な方程式に座標変換できたと思う。
その変換がガリレイ変換だったかローレンツ
変換だったか覚えてないです。
天動説が間違っているかについては
相対論とのからみで下リンクに説明がある
http://fj.sci.physics.narkive.com/tR5DC096/4-009
要するに、どの慣性系をえらんでもよい。
だけど、太陽を中心に計算する座標系を選んだ方が
「計算が楽だから、みんな当然そうするよね。」
という話。
天動説 vs 地動説の話は、相対論のある現代に
おいては死んだ話題。
細かく見ると、上記変換には
時間tがパラメータに含まれているので
ただ線形和をとってる訳ではない
線形和だけでは、非線形には
ならないと思われます。
例えば、ABCD...を行列として
行列の積の結果Eを
E = ABCD...
の様に考える
Eとベクトル(x,y)の積は
Eの要素がE11,E12,E21,E22で
あると考えると
(E11*x + E12*y,E21*x + E22*y)になり
変換後も、線形であることには、
変わりがないことになる。
線形和のみではなく、活性化関数hが含まれるため
この状況が変わると思われます。
h関数は、x、yをとるので、h(x,y)と考えても
良いと思います。
また、この話の流れとは直接関係ないですが
重みの行列をWとすると
hとW(x y)の積でhとWは交換可能でない
つまり、hW-Wh≠0(hW≠Wh)です。
話は変わりますが、もっと俯瞰した話として
ニューラルネットワークには、任意の関数を表現できる話もあります。
http://yuki-sato.com/wordpress/2014/09/03/performingfunction/
もっと、正確な議論は下リンク内にある論文など
見ることになるんですかね?
http://qiita.com/HirofumiYashima/items/774f8b41489e2622e1db
(3)パーセプトロンとニューラルネットワークと
言っているが、なぜパーセプトロンに
対してニューラルネットワークでなく
ニューロンを使わないのはなぜ ?
⇒回答として結論はでていて
この本では、ニューロンは、グラフのノードと同じ意味
で使用しているので、その流儀では、ニューラルネットワーク
が正しい。
⇒発言しなかったが、思ったこと
ニューロンという言葉は、意味が文脈でかなり
変わるので、掲題のような説明に使われるのは
なんとなく嫌な感じがした。
⇒いなや理由
http://d.hatena.ne.jp/krxross/20170517/1495032611
(4)ローカルミニマムに落ちない保証は ?
⇒初っ端に思ったこと、上手く説明できないので
発言しなかったが、端的に言うと
「あるワケ無い」とフィーリングで思った。
任意性の高い関数超曲面の最小値をどうやって
求められるだろうか ?
話が違いますが、数理最適化問題で
巡回セールス問題を遺伝的アルゴリズムで
探す手法があるが、最適解でないばかりか
最悪どこまで、最適解とかけ離れているかも
保証できなかったとおもいます。
上記の問題よりも、離散値でなく
連続値であることや、線形でなく
任意のグラフが書けてしまうことを
考えると、問題はさらに難しいと
フィーリングでは思ってしまいます。
(質問者は、数式で論理的に分かりたいのだと
思うので、質問者にとって上記はただの
ポエムでしかなく、なんの価値もないですが。)
ところで、問題が解けると言う時に
嬉しい順は、次の順のように思う。
(a)代数的に解ける。
(b)近似で解け、最適解に限りなく
近づくことができる。
(c)近似で解け、最適解から
かけ離れている率が、高々決まる。
(d)近似で解け、最適解から
どれだけ、かけ離れているのか
推定すらできない。
アルゴリズムの性能上(d)を選択するしか
ない問題が、最適化問題には
多くあると思います。
それと、ニューラルネットワークの
ローカルミニマム問題は
変わらないと思いますがどうでしょうか?
(所詮近似でしかないですし)
■自分が7shiさんに聞きたいこと。
http://d.hatena.ne.jp/krxross/20170520/1495250231
SQLで組合せ最適化(メモ2)
あまり、整理できていないので
あとで整理する予定だが、列記する
以下SQLServerで確認
■素因数分解
nullやゴミを取り除いていない
WITH Input(iStart, iEnd) AS (
SELECT 1, 10
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
prime_factorization (num, value, prime, success) AS (
SELECT CAST(num AS INTEGER)
,CAST(num AS INTEGER)
,CAST(2 AS INTEGER)
,NULL
FROM NaturalNumber
UNION ALL
SELECT
num,
CASE WHEN (value % prime) = 0
THEN value/prime ELSE value
END,
CASE WHEN (value % prime) = 0
THEN prime ELSE prime + 1
END,
CASE WHEN (value % prime) = 0
THEN 1 ELSE 0
END
FROM prime_factorization
WHERE value > 1 OR (value = prime)
)
SELECT
num,
(SELECT ',' + CAST(prime AS VARCHAR(MAX))
FROM prime_factorization PF
WHERE success = 1
AND PF.num = NN.num
FOR XML PATH('')
) AS primes
FROM NaturalNumber NN
ごみを取り除くと
WITH Input(iStart, iEnd) AS (
SELECT 1, 50
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
primes (num, value, prime, success) AS (
SELECT CAST(num AS INTEGER)
,CAST(num AS INTEGER)
,CAST(2 AS INTEGER)
,NULL
FROM NaturalNumber
UNION ALL
SELECT
num,
CASE WHEN (value % prime) = 0
THEN value/prime ELSE value
END,
CASE WHEN (value % prime) = 0
THEN prime ELSE prime + 1
END,
CASE WHEN (value % prime) = 0
THEN 1 ELSE 0
END
FROM primes
WHERE value > 1 OR (value = prime)
),
primes2 AS (
SELECT
num,
(SELECT ',' + CAST(prime AS VARCHAR(MAX))
FROM primes PF
WHERE success = 1
AND PF.num = NN.num
FOR XML PATH('')
) AS primes,
(SELECT count(prime)
FROM primes PF
WHERE success = 1
AND PF.num = NN.num
) AS cnt
FROM NaturalNumber NN
)
SELECT num, SUBSTRING(primes, 2, LEN(primes))
FROM primes2
WHERE cnt > 0
■完全数
WITH Input(iStart, iEnd) AS (
SELECT 1, 100
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber
INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND (A.num % B.num) = 0
)
SELECT NN.num "完全数",
(SELECT '+' + CAST(PF.prime AS VARCHAR(MAX))
FROM Primes PF
WHERE PF.num = NN.num
FOR XML PATH('')
) AS "計算式"
FROM Primes NN
GROUP BY num
HAVING SUM(prime) = num
WITH Input(iStart, iEnd) AS (
SELECT 1, 100
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber
INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND (A.num % B.num) = 0
)
SELECT NN.num "不足数",
(SELECT '+' + CAST(PF.prime AS VARCHAR(MAX))
FROM Primes PF
WHERE PF.num = NN.num
FOR XML PATH('')
) AS "計算式"
FROM Primes NN
GROUP BY num
HAVING SUM(prime) < num
■過剰数
完全数と条件の符号が異なるだけである
WITH Input(iStart, iEnd) AS (
SELECT 1, 100
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber
INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND (A.num % B.num) = 0
)
SELECT NN.num "過剰数",
(SELECT '+' + CAST(PF.prime AS VARCHAR(MAX))
FROM Primes PF
WHERE PF.num = NN.num
FOR XML PATH('')
) AS "計算式"
FROM Primes NN
GROUP BY num
HAVING SUM(prime) > num
■完全数でない擬似完全数
擬似完全数の前に、完全数をのぞいたもの
WITH Input(iStart, iEnd) AS (
SELECT 1, 100
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber
INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND (A.num % B.num) = 0
),
Abundants AS (
SELECT NN.num,
SUM(prime) - num AS abundant
FROM Primes NN
GROUP BY num
HAVING SUM(prime) > num
),
Goods AS (
SELECT P.num, prime, A.abundant
FROM Abundants A
JOIN Primes P
ON P.num = A.num
)
,Knapsack(num, prime, pLst, sumVal) AS (
SELECT num, prime
, CAST(prime AS varchar(max))
, prime
FROM Goods
UNION ALL
SELECT a.num
, b.prime
, CAST(a.pLst + ','
+ CAST(b.prime AS varchar(max))
AS varchar(max))
, a.sumVal+b.prime
FROM Knapsack a JOIN goods b
ON a.num = b.num
AND a.prime < b.prime
AND a.prime <= b.abundant
)
SELECT num "擬似完全数", MAX(pLst) "式"
FROM Knapsack
WHERE num = sumVal
GROUP BY num
ORDER BY num
最後のグループ化は無駄に
重複計算してしまうので
なんとかしたい
■擬似完全数
WITH Input(iStart, iEnd) AS (
SELECT 1, 100
),
NaturalNumber(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM NaturalNumber
INNER JOIN Input
ON NaturalNumber.num + 1 <= Input.iEnd
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND (A.num % B.num) = 0
),
Parfects AS (
SELECT NN.num
FROM Primes NN
GROUP BY num
HAVING SUM(prime) = num
),
Abundants AS (
SELECT num, SUM(prime) - num AS abundant
FROM Primes
GROUP BY num
HAVING SUM(prime) > num
),
Goods AS (
SELECT P.num, prime, A.abundant
FROM Abundants A
JOIN Primes P
ON P.num = A.num
),
Knapsack(num, prime, pLst, sumVal) AS (
SELECT num, prime
, CAST(prime AS varchar(max))
, prime
FROM Goods
UNION ALL
SELECT a.num
, b.prime
, CAST(a.pLst + '+'
+ CAST(b.prime AS varchar(max))
AS varchar(max))
, a.sumVal+b.prime
FROM Knapsack a JOIN goods b
ON a.num = b.num
AND a.prime < b.prime
AND a.prime <= b.abundant
)
SELECT num "擬似完全数", MAX(pLst) "式"
FROM Knapsack
WHERE num = sumVal
GROUP BY num
UNION
SELECT PF.num,
(SELECT '+' + CAST(PR.prime AS VARCHAR(MAX))
FROM Primes PR
WHERE PF.num = PR.num
FOR XML PATH('')
) AS "計算式"
FROM Parfects PF
ORDER BY num
■ORACLEでは、上がそのまま動かない
テーブルを作成しながら作成を試みる
create table natural_numbers as
WITH Input(iStart, iEnd) AS (
SELECT 0, 9 FROM DUAL
),
numb(num) AS (
SELECT iStart FROM Input
UNION ALL
SELECT num + 1 FROM numb
INNER JOIN Input
ON numb.num + 1 <= Input.iEnd
)
SELECT TO_NUMBER(k.num || l.num || m.num || n.num) num
FROM numb k, numb l, numb m, numb n
ORDER BY k.num, l.num, m.num, n.num
WITH
NaturalNumber AS (
SELECT num FROM Natural_Numbers WHERE num <= 100
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND MOD(A.num, B.num) = 0
),
Parfects AS (
SELECT NN.num
FROM Primes NN
GROUP BY num
HAVING SUM(prime) = num
),
Abundants AS (
SELECT num, SUM(prime) - num AS abundant
FROM Primes
GROUP BY num
HAVING SUM(prime) > num
),
Goods AS (
SELECT P.num, prime, A.abundant
FROM Abundants A
JOIN Primes P
ON P.num = A.num
),
Knapsack(num, prime, pLst, sumVal) AS (
SELECT num, prime
, TO_CHAR(prime)
, prime
FROM Goods
UNION ALL
SELECT a.num
, b.prime
, a.pLst || '+' || TO_CHAR(b.prime)
, a.sumVal+b.prime
FROM Knapsack a JOIN goods b
ON a.num = b.num
AND a.prime < b.prime
AND a.prime <= b.abundant
)
SELECT num "擬似完全数", MAX(pLst) "式"
FROM Knapsack
WHERE num = sumVal
GROUP BY num
ORDER BY num
WITH
NaturalNumber AS (
SELECT num FROM Natural_Numbers WHERE num BETWEEN 1 AND 200
),
Primes AS (
SELECT A.num, B.num prime
FROM NaturalNumber A
JOIN NaturalNumber B
ON B.num <= A.num / 2
AND MOD(A.num, B.num) = 0
),
Parfects AS (
SELECT NN.num
FROM Primes NN
GROUP BY num
HAVING SUM(prime) = num
),
Abundants AS (
SELECT num, SUM(prime) - num AS abundant
FROM Primes
GROUP BY num
HAVING SUM(prime) > num
),
Goods AS (
SELECT P.num, prime, A.abundant
FROM Abundants A
JOIN Primes P
ON P.num = A.num
),
Knapsack(num, prime, pLst, sumVal) AS (
SELECT num, prime
, TO_CHAR(prime)
, prime
FROM Goods
UNION ALL
SELECT a.num
, b.prime
, a.pLst || '+' || TO_CHAR(b.prime)
, a.sumVal+b.prime
FROM Knapsack a JOIN goods b
ON a.num = b.num
AND a.prime < b.prime
AND a.prime <= b.abundant
)
SELECT num "擬似完全数", MAX(pLst) "式"
FROM Knapsack
WHERE num = sumVal
GROUP BY num
UNION
SELECT PF.num,
(SELECT LISTAGG(PR.prime, '+') WITHIN GROUP (order by PR.prime) FROM Primes PR WHERE PF.num = PR.num)
FROM Parfects PF
ORDER BY "擬似完全数"
