理が紡ぎだす美 シリーズ（10）
唐草模様
どこかで見かけた花に似ていませんか。
つぎのものにもご訪問ください。
動視化技術研究所HP
youtube動視化技術研究所
youtube hiroto namihira
2018年9月15日土曜日
2018年9月7日金曜日
情報と知恵 シリーズ
情報と知恵（3）
構造化+知恵
２分探索法は非常に効率的ですが、それでもなお工夫の余地があります。
それは、データの調査位置を狭められた探索範囲の中心と決めている点です。
たとえば、英語のyellowを辞書で調べる場合、２分探索では辞書の中央に位置する言葉を最初に調べます。
しかし、yellowはｙで始まるので語数は少なく ｓ や ｔ などの多くの語数の後にある等の知識があれば、当然辞書の後ろのほうの位置を調べるのが合理的です。
すなわち、知恵を動員して調べる位置の予測をするのです。
検索において構造化に加えて知恵を組み込むときは、その効率はさらに上がります。
それは、予測に伴う分布の知識から、つぎの探索範囲が大幅に縮まるからです。
理論的に計算すると、知恵を組み込むときの探索回数は2分探索を超えて、
であることが分かりました。
n=256×1036のような膨大なデータからの検索でも
T(n)=log2(log2(1036))=7
すなわち、7回の検索回数で見つけられるのです。
神の検索
ほとんど架空の条件ですが、1回の探索後に残る探索範囲がlog(n)に縮まるような場合を考えてみました。
n=2128 として、数値的に検索回数
T(n)
を求めてみると、次のようになります。
T(n)=1+T(log2(n))=1+T(128)=1+(1+T(log2(128))=2+T(7)
すなわち、2回も調べれば残った検索範囲は7に激減しています。このような検索は、神の領域というべきか。
ここで、データ数 n=100000000(1億) として、この中から指定したものを見つけ出すまでの必要な各方法ごとの検索回数を、比較のためまとめておきましょう。
検索方法 検索回数
手当たりしだい 460000000 ：９９％見つけるのに必要回数
経験の墨守
50000000
整理・構造化 27
構造化＋知恵 5
神の検索 3
全体のまとめ
全く考えず、慌てふためいた手当たり次第の対応は、結果を運のみに頼る愚かに近い行動です。これより少しマシなのが、経験の墨守です。経験したことしか学ばないのですから、かなりのことを学ぶには相当時間がかかります。
効率を格段に上げるには、考えなくてはなりません。自分の対面していることの構造を知り、その構造に照らして一つの経験から多くの情報を引き出し、次の自分の効率的な行動に結び付けるのです。物事の整理・構造化はlogのオーダで行動の効率を上げるのです。
整理・構造化の上に知恵を加えれば、一つの経験から引き出される情報の効率はlog(log)のオーダでさらに桁はずれの向上となることが分かりました。知恵とは、予測に似たものです。物事の構造化や知恵の活用という知的行為と検索効率におけるlogとが対応しているのは面白いことですね。
手当たり次第は何も学ばず、経験の墨守は経験したことしか学ばないことです。整理・構造化はこれまでの知見を活用するのですから歴史より学ぶことに対応すると考えると形になりますね。
“愚者は経験より学び、賢者は歴史より学ぶ”
とはこのことか。嗚呼。
2018年9月4日火曜日
2018年8月25日土曜日
情報と知恵
情報と知恵（2）
整理・構造化
つぎは、蓄えるファイルへのデータの置き方の工夫で、検索効率を桁違いにあげる方法です。説明を分かりやすくするために、データをn個の数値データとします。はじめ、データはファイルにデータの生じた順に並べられています。いまデータの内容に着目して、これを値の小さい順に並べ直したとしましょう。
さて、このデータを小さい順（昇順）に並べなおしたファイルでの検索を考えます。いま、検索したい指定データを ａ とします。探し出したいこの ａ は、ファイルのどこにあるか分かりません。すなわち、探索範囲はファイルの全域のn個です。いま、この探索範囲のちょうど真中のデータの値を調べてこの数値がmであることを知ったとします。すると、ファイルのデータは昇順に並んでいるので、1回のデータの調査（検索）から次のことを知ることができます。
a=m のとき 運よく見つかった
a>m のとき ａは真中より後ろのほうにあることが分かる
a<m のとき ａは真中より前のほうにあることが分かる
すなわち、見つからなかったときは、調べて得た情報mと目的のaとの関係により次の探索範囲は今回の半分に縮まります。これは２分探索法と呼ばれています。n＝1000 の場合の２分探索法による探索範囲の縮まり方は、次のようになります。
1000→ 500→ 250→ 125→ 63→ 32→ 16→ 8→ 4→ 2→ 1
探索範囲が1になれば見つかったことなので、２分探索法によれば1000のデータから１０回の検索で必ず見つけることができるという訳です。
一般に、n個のデータから 回の検索でかならず目的のものへたどり着くことができます。この という効率は順次に調べる方法に比べて、桁外れによいものになっています。
下の図は、2分探索において、探索範囲が急速に縮まっていくことを視覚化したものです。
２分探索による範囲の縮まり方
2分探索法の効率の良さは、探索の対象となるデータを構造化したことによるのです。バラバラであったものを目的に沿って関連付ければ、１つの情報から非常に多くの意味を取り出すことができるということです。これが相乗的に効果を生むのです。
2018年8月15日水曜日
情報と知恵シリーズ
情報と知恵
情報という言葉は、世に満ち満ちています。今の世では、その使い方は大変重要なようです。これについて、少し落ち着いて考えてみました。
情報とは、それを知ることで今まで不確かであったことが少しでも確からしくなる知識のことですね。これを得るには、意識して捜さなければなりません。
まず、知りたいことAがあります。初めは、Aについての知識はないとします。そこで、Aについて知っていそうなC1に当たり、Aについての知識B1を得ます。これで、Aのありそうな範囲が狭まります。これを情報と呼びます。
情報処理では、情報を探り出す作業を検索といいます。これには、うまいやり方とそうでないやり方があります。
世の中には一を聞いて十を知る英才もいれば、何度教えても学ばない御仁も居ます。ここで、一を聞いて（すなわち、一つの経験あるいは1回の調査から得た情報を理解して）これをその後の行動に生かすときの検索の効率について考えてみました。
いま、検索効率を、次のように決めましょう。
検索効率 ： 目的のものを見つけるまでの検索の回数
考えの筋道を明らかにするため次のような問題の設定をし、これを通して探索効率について考えてみました。
問題の記述
「n個のデータが書き込まれたファイルがある。データの数nは分かっており､このファイルの中に探したい指定データａがあるがそれがどこにあるか知りたい。
求めるデータの探し方には、検索のためのデータの準備の仕方も含めて、効率的なものとそうでないものとがあります。その効率の測定ですが、既に定義したように、目的のものを見つけ出すまでの探索の回数で測るのが合理的です。記号として、
としておきます。
さてこれから、賢くないやり方のほうから順にとりあげ、その効率について考えてみます。
手当たり次第に調べる方法
まず、どう見ても賢くない方法は、n個のデータからでたらめに選ぶことを当たるまで繰り返す方法でしょう。この方法では、指定のものを見つけるのは偶然しかない。選んだものが偶然に指定のものと一致する確率は 1/nで、nが大きいときは偶然当たる確率は非常に小さい。はずれた次もまた偶然を頼りにデタラメに選ぶということは、１つを選ぶことで得た情報をつぎの探索にまったく使わないことです。したがって、効率は恐ろしく悪い。たとえて言えば、経験からまったく学ばない生き方と同じです。
“バカは死ななきゃ直らない”というやりかたです。
厳密に計算すると、n＝1000のときデタラメに探して1000回以内に偶然見つかる確率は0.6321です。また、99％の確率で見つけるためには、4600回程度の運を天に任せた選択の繰り返しが必要です。
経験の墨守
前の“手当たり次第”よりは少しよい次の方法は、ファイルのデータの任意のものを選んでそれを指定のものと比べ、一致しなければそれを除いたものから次を選ぶことを繰り返す調べ方です。今確かめたデータは求めるものではないのですから、その情報を使いつぎの検索範囲を一つ狭めることができます。これを続けると調べる範囲が着実に狭くなり、ついには調べる範囲が１個になり確実に見つけることができるわけです。すなわち、最大(n-1)回調べれば確実に見つけられます。
指定のものを見つけるまでに最大n回であり、運がよければ1回で見つかることもあるので、平均はn/2回の検索で見つかるとみなせます。大雑把に言えば、データ数nとおなじオーダの検索回数で見つけられる訳です。
T(n)=n
1回の探索から得た情報の利用という観点からいえば、この方法にはもっと工夫の余地がありそうです。経験したそのものを記憶するのみで内容の意味とか理由などを考えようとせず、ただ過去に起きた同じ事を避けようとする愚直な反応によく似ていますね。
登録:
投稿 (Atom)