放送大学全科目感想 020 情報セキュリティ概論(’22)

  • 情報コース
  • テレビ科目
  • 山田恒夫先生(放送大学教授)
  • 辰己丈夫先生(放送大学教授)
  • 難易度 ★★☆☆☆
  • おすすめ度 ★★★★☆

ゲスト講師も入れて5人での講義。技術的な話はもちろん倫理、教育など扱う内容も広い。聞き手はお茶大博士卒でAI研究家の大西可奈子さん。多くの回で貴重なインタビューを聞くことができ、放送授業を聞く価値が高い。個人的には、辰己先生の慧眼が光っていると感じた。第11回の花岡先生の話は若者のSNS行動を知りたい人にとっては必見。

第1回

AI研究家の大西さんが聞き手。90年代、中学校でコンピュータに触れたらしい(同年代だ)。山田先生は70年代~80年代に動物の研究で使ったらしい。コンピュータが発展して悪いことを考えるやつが増えた。なのでセキュリティを知らないといけない。サイバー空間の特性(ボーダレス性、オープン性、匿名性とか)のせいでセキュリティも重要に。

先生が受けた実際の被害。SPAM。先生のパソコンから東南アジアにアクセスしているという報告(原因は不明)。

情報セキュリティとは何か。企業や官公庁などの組織や個人における情報資産全般の機密性(Confidentiality)、完全性(Integrity)、可用性(Availability)等を保障すること。情報資産→情報を資産としてとらえていること。

脅威とは何か。システムまたは組織に損害を与える可能性があるインシデント(事案)の潜在的な原因。

リスクとは。ある脅威がある情報資産の脆弱性によって、システムや組織に損害を与える可能性。情報資産 * 脅威 * 脆弱性。脆弱性とは、情報資産に影響(損害)を及ぼす、こうした脅威に対する対応策が採られていない性質のこと。

情報セキュリティマネジメントシステム→組織としてのセキュリティ管理の実施、マネジメントとしてのセキュリティレベルを決めた運用、リスク管理。

法。不正アクセス禁止法、電子署名法、特定電子メール法、個人情報保護法、サイバーセキュリティ基本法など。

情報倫理。インターネット社会において生活者がネットワークを利用して互いに快適な生活を送るための規範や規律のこと。応用倫理学の一分野(まじで?)。

第2回

パスワード・認証について。ゲストの東邦大・金岡先生。もじゃもじゃしてる。

認証とは。門番に顔とか通行証とかの証拠を見せたりすることから始まった。今はパスワード。遠隔から、というところが昔と違う。なりすましの可能性が上がる。定義は「相手に自分が何者であるかを主張し、相手に本人性を確認してもらう行為」。名乗ってから確認する。記憶による認証(パスワード)、所持による認証(カード)、本人の特徴による認証(指紋)。

リモート認証とローカル認証。リモートだと通信路・サーバーから漏れる。ローカルだと覗き見・アプリからのアクセスで漏れる。生体認証はリモートでは使えない(機密性が高すぎ)。

多要素認証。例えば銀行口座振り込みはいくつかの認証方法を組み合わせてる。パスワード+スマホ認証とか。

パスワード。サーバー上ではパスワードはハッシュ化されているので、送信したパスワードをハッシュ化して比較する。

チャレンジレスポンス方式。サーバーが乱数でチャレンジを送信し、ユーザーはパスワードでチャレンジを加工、レスポンスとサーバー側で計算した加工データを比較する。この方式だと送信データが加工されていて漏れても安全。ユーザーからの見た目もパスワード入力してるだけだから変わらないはず。

簡単なパスワードにさせないために、パスワード構成ポリシーをつける。強度を表示する。パスワードは単に長くするだけで相当強度が上がるので、16字以上にしてくれとかにすれば結構強い。

ユーザー側のパスワード管理。管理ツールがあるらしい。サービスごとに使い分けろと言われた。まあそうなんですけど、大変ですよね。定期的変更の強制はだめらしい。わかりやすくしてしまう。秘密の質問も簡単に推測できるからダメ。

パスワードに対する攻撃。オンライン攻撃:総当たり攻撃。オフライン攻撃:ハッシュ値を取得して解析。ソーシャルエンジニアリング:ユーザーの心理や認知から取得。リスト型攻撃:漏洩したものを別のサービスで使う。

第3回

暗号について。暗号とは、一定の規則に従って情報を秘匿すること。

古典暗号と現代暗号の違い。昔の暗号は文字列をずらすとか1対1のものが多い。3文字ずらすシーザー暗号が有名。現代では暗号方式のレベルが上がった。1970年代以降、DES、公開鍵暗が登場してかなり変わったのでこれ以降を現代暗号という。

共通式暗号。暗号化と復号化が同じ鍵。長距離の共有が難しいことが問題。はやい。AES(ブロック暗号。数バイトずつ)、ChaCha20(ストリーム暗号。1バイトずつ)。

暗号利用モード。暗号の利用法を定義すること。例えばECB。平文→暗号→暗号文ブロックという単位で変換する。すると同じブロックからは同じブロックができるので、予想ができてしまう。ECBは非推奨。

CBC。平文ブロックと一つ前の暗号文ブロックを組み合わせてXORで暗号化する。すると同じデータは出てこない。

公開鍵暗号。暗号化と復号で違うカギを使う。Diffie-Hellman鍵交換にはじまる。お互いが秘密の情報を持っていて、公開の情報を使って累乗と割り算を行う。割り算の余りを交換して、自分の秘密の情報を使ってまた累乗と割り算を行う。すると、余りが一致する(数学的には印刷教材を見よ)。これを共通鍵として使える。

RSA。Rivest, Shamir, Adlemanさんが作った。素因数分解を使う。秘密鍵と公開鍵を交換できることが特徴で、署名にも使える。DSA。電子署名特化。

暗号学的ハッシュ関数。非改竄性の保障をする。SHA-256、SHA-512など。

疑似乱数生成器。鍵の生成にランダム性が必要になる。再現性がないような乱数を作れなければいけない。でも完璧な乱数は(物理的に?)作れないので、疑似という言葉が付く。具体的な説明はなし。

暗号化の標準化。暗号は鍵以外の情報が公開されたとしても安全でないといけない(ケルクホフスの原理)。ISOとかNISTとかいろんな標準化団体がある。

応用。PKI:公開鍵基盤。信頼ある機関(CA)に証明してもらうこと。PGPは当事者間でやること。TLSではセキュリティレイヤーのことで、セキュリティの機能を提供する。

第4回

マルウェアについて。サイバー犯罪の区分から。不正アクセス、電磁的記録対象、児ポ、詐欺、著作権法。電磁的記録対象犯罪とは、サーバーのデータを書き換えたり、クレカのデータを不正に取得したりすること。

不正アクセスの原因と行為。原因→設定・管理が甘い。不正アクセス後→不正送金・購入、メールの盗み見など。

マルウェアとは。不正な行為を行う意図で作成された悪意のあるソフトウェアの総称のこと。ウイルスだけではなく、ワームやスパイウェア、ボットなど。

具体例、Emotet。2019年ごろ流行る。メールにwordファイルがついてくる。しかもパスワード付きzipだったりする。開封すると感染し、外部サーバーと通信する。サーバーからくるのがマルウェア本体で、随時機能がアップデートされる。情報を取得したり、他のアドレスに同じメールを送信する。

感染経路。メール以外にはweb閲覧、ネットワーク通信経由、USBメモリなどの経由がある。

マルウェアの種類。スパイウェア→ユーザー情報を送信。バックドア→アクセスできない裏口を開く(ポートを開くとかかな)。

ボット→リモート操作可能にする。ボットだけでネットワークを構成してボットネットを作る。サーバーを貸したり売買したりもする。DDos攻撃だけではなくマイニングしたりもする。これをやめさせるのをテイクダウンという。

ランサムウェア→データを使用不能にして、復旧に金銭を要求する。CryptLockerが代表例。金銭支払いにも暗号化で匿名性を確保したので実害が大きかった。

対策。マルウェアを取得して動的解析・静的解析を行う。マルウェアの逆アセンブルってどうやるんだろうね。検体取得方法。ハニーポット→わざと感染させる端末。広域観測→監視ポイントから情報を集約。

対策:OSを最新にしておけ。感染したら?まず通信を切る。クレカを止める。特に企業の場合、どういう被害があったかを把握するためには、電源を切らない方がいい。電源を切るとマルウェア自体が痕跡を消すことがある。

第5回

ネットワークとセキュリティ。スマホはインターネットを介してサービスを得るので、ネットワークのセキュリティを担保しないといけない。

具体的に何をするか。まずネットワークの分離。外部ネットワークと内部ネットワークをゲートウェイ、ファイアウォールで隔離する。外部向けサーバーはDMZに置く。DMZにはIDSという不正アクセス検知機能も付けておく。これで内部ネットワークは外部と完璧に分離できる。

クラサバシステムに、インターネットを挟んだサービスは、複数のサーバーを使っている。システム自体がネットワークを構成している。これを3層アーキテクチャーという。3層アーキテクチャーは、プレゼンテーション層、アプリケーション層、データベース層からなる。プレゼンテーション層がユーザーのアクセスする所(webサーバー)。webサーバーがアプリケーションサーバーにアクセスし、アプリケーションサーバーがデータベースに接続する。外部とアクセスするのはwebサーバーだけ。

分離の利点は、サーバーを簡単に増減できること。さらに、webサーバーまでにアクセスを制限できるからセキュリティ面でも有利になる。

脆弱性対策。まずバッファオーバーフロー、スタックオーバーフロー。スタックオーバーフローだとソフトウェア終了後の処理の行き先が変わる。対策としてはコンパイラで検知、メモリー領域に実行不可属性をつける、アドレス空間をランダム化する(被害を少なくする?)琴が考えられる。どれもOSで何とかする機能かな。

ハードウェアによるセキュリティ確保。ハードウェア上に信頼されたゾーンを用意して隔離実効ができる。有名なのはTPM、TEE。

クラウド上でサーバーをレンタルしている場合(サーバーの外部委託)のセキュリティは。通信がゲートウェイを介して外部とやり取りする機会が増えるから、ゲートウェイが大変になってきているらしい。不正アクセスの余地が高まる。

ゼロトラストネットワーク。組織的ネットワーク内で安全という考えは捨てて、細かい単位で認証と認可とデータ保護を考えること。ユーザー認証以外にもソフト認証、ハードウェア認証などを駆使する。

第6回

個人情報とプライバシーについて。辰己先生。

情報とデータとの違い。意味があるかどうかが違う。記号が意味になるかどうかはそれを扱う人次第。雑音とか、理解できない外国語は意味がないので情報ではない。

日常生活での情報。コンピュータ以前は紙などで伝えていたので、複製が困難、遠隔地に届けるのも困難なので、個人情報は広がりにくかった。現代では、情報は文字・色・画像・音になるので、コンピュータ・ネットワークで扱いやすい。

個人から得られる情報→身長とか国籍とか。これ単独では個人を特定できない。ところが、住所や氏名、顔写真などは、単独や組み合わせて個人を特定できる。

個人情報保護法で定義する個人情報とは、氏名、生年月日その他の記述で、特定の個人を特定することができるものとある。

インターネット普及以前は、転居してきた隣人の指名と年齢と新聞記事データベースは照合できなかった。が、普及以後はニュースサイトなどで簡単に検索可能になった。個人情報を組み和せば特定ができる。病歴とか指紋とか、図書館の貸出履歴からもわかってしまう?こういう結合は法律で禁止するしかない。

個人情報の価値を評価すること。アンケートとか会員登録の経費、マーケティング、生産管理等で得られる利益、流出データの回収費用などを足し合わせた者が価値になる。

個人情報取り扱いの基本。適正取得とか利用目的に通知、安全管理、第三者提供の制限(同意なしだとダメ。でも生命にかかわる場合など例外もある)など。

プライバシー。自分がコントロールできる抽象的な領域のこと。自分の情報の用途を自分で決めることができる権利をプライバシー権という。個人情報保護法で保護する。日本にはプライバシー自体を保護する法律はない。憲法の人権から出てくるしかない。

肖像権。個人の写真を見せない権利。パブリシティ権。有名人の写真や名前を見せて利益を得る権利。

個人情報保護委員会に取材してる。マイナンバーのためにできた。国で使う個人情報の監督権限を各省庁を超えて一元管理することが目的。個人の権利と利益の保護、個人情報の有用性(利益)の2つを調整する。子どもたちに向けての広報もやってる。SNSでの個人情報についての動画を見せてもらった。動画に学校、顔写真、風景、建物が移ってて危ないよということとか、オンラインゲームで連絡先を交換するのは危ないとか。

第7回

情報セキュリティポリシーについて。方針~手順までいろんなレベルがあり、組織ごとにも異なる。今回扱うのは「高等機関の情報セキュリティ対策のためのサンプル規定集」。辰己先生も策定に関わってるらしい。

情報の格付け、CIA。機密性・完全性・可用性のこと。機密性の格付けは3レベル(機密性3、2,1)。秘密文章に相当すれば3。あんまりレベルが高くなければ1。大学だとこれくらいでちょうどいい。複製とか転記とかができるかできないかが変わってくる。完全性も可用性も同様にレベルが設定されている。バランスが必要。機密性を重視しすぎると災害時に必要な情報が手に入れられなかったりする。

規定集の例。目的、実際の規定、義務、罰則で構成される。あと具体的な実施手順。例えばパスワードはこうしなきゃならないとか。

企業と大学だとポリシーが変わってくる。大学の方が研究を進めるために秘密を緩くする必要がありそう。

業務の組織と情報セキュリティの組織は違うという話。社長(CEO)・情報統括責任者(CIO)・情報セキュリティ技術責任者(CISO)・情報技術担当者・一般社員、などのような区分がいいとしている。これは一般的な部長・係長、などとは別の区分にする。CEO・CIO・CISOは兼任可能。

緊急時に運用を変えられるようにするのも大事。チーム(CSIRT)を作れるようにしておくのもよい。

教育・監査・評価も必要。役割ごとに必要な教育が違うこと、日常・抜き打ちの監査の必要性、評価にも基準があることなど。

第8回

連携時におけるトラブルと対策について。

まずCOVIDの影響について。放送大学でも単位認定試験・面接授業に大きな影響があった。

クラウドとオンプレミスについて。クラウド→外注で安い、オンプレ→自社運用、希望通りの実現ができるが管理が大変。セキュリティの面ではオンプレの方がいいかと思われるがそうでもない。運用は大変。XaaS→様々なas a serviceのこと。IaaS(インフラ)、PaaS(プラットフォーム)、SaaS(ソフトウェア)がある。

連携:APIについて。ソフトウェア間のインターフェースの仕様・規約のこと。特にWebAPIを取り上げる。APIを介してシステムとの情報のやり取りをする。マッシュアップという概念もある(ちょっと意味わからなかった)。デジタルエコシステム(よくわからん)。

COVID-19がもたらしたもの:テレワーク、オンライン学習で、信頼できるネットワークの外に端末が持ち出されてしまったこと。ファイアウォールの外側のことを考えなければいけなくなった。境界防御セキュリティ→ゼロトラストセキュリティへの転換。ゼロトラストは7つの基本的な考え方がある(印刷教材を見よ)。ICAMシステム、SIEMシステムなどが必要。

認証と認可の違い。認証は本人確認、認可はアクセス権限を与えること。

実装事例。今まではLMSとか教務システムとか電子図書館とか、全部別個に実装されていた。これをNGDLE(次世代電子学習環境)に統合しようとする動きがある。システム同士の相互運用性とか、最適化された学びなどを提供する。そして教育・学習デジタルエコシステムを構成する。セキュリティ対策ではOAuth2.0による人相、IMS技術に基づくデータ交換などを使う。認証システムはkeio.jpみたいなやつかな。

第9回

リスクマネジメント。リスクとは、損害・被害が予想される状況で、まだ起こっていないこと(起こってしまったのはインシデント)。

避けられないリスク:雨が降る。千葉県は100日だがアスワンは1日なので、アスワンでは屋根はいらない。なので被害の程度・頻度を考える必要がある。他には地震。日本には多い。対策としては、地震に強い建物を作るなど。隕石の衝突。甚大な被害があるが、めったにない。これは対策する必要あるのか?ない。よって、大きなリスクと小さなリスクがあることが分かる。リスクを評価して対策の程度を決めないといけない。

IT関係のリスク。例えばパスワード管理。リスクへの対応はどうするか。先生がおすすめするのは段階的対応。事前防御のほかに、事故対応の準備、事中対応、事後処理。事前:アンチウイルスソフトやアップデート。事故対応の準備:ログをとるとかバックアップをとるとか。事中対応:当事者と連絡を取ったり、復旧したり。事後処理:報告書、再発防止策、ポリシーの改定など。

側面対応。HECTL。人的・教育・費用・技術・法の面から対応する。段階的対応とあわせて、二次元的に分析する。例えば教育+事前防御(E1)とか、技術・事中対応(T3)とか。

個人情報とプライバシーの歴史。宇治市役所データ漏洩事件のインタビュー。平成11年の乳幼児健診システムから漏れた。個人情報を名簿業者に売却してしまった。買った人に対しては情報を回収したらしい。裁判では、目的外で情報が使われたのはダメということで損害賠償が認められた。自己情報コントロール権が認められた。宇治市で見直したこと。個人情報は庁舎内から絶対に出さない。業務のネットワークは内部と外部でしっかり分離する(当時はてきとうだった)。市民へのサービスはどう変わったか。費用は高くなったが、質は下げないようにしたので、職員は大変になった(派っきりは言ってないけど)。研修でも必ず1999年の事件には触れるらしい。

個人情報に関する空気感。80年代までは電話帳にほぼ全家庭が情報を載せてた。80年代からコンピュータが導入、90年代からインターネット。95年のEUデータ保護指令、99年の宇治市データ漏洩事件を契機に2003年に個人情報保護法が成立した。

web広告とトラッキング。行動が追跡されてるのでは?ちょっと違う。SNSやニュースサイトの広告枠が共通になっていることによる。サードパーティ・クッキーを介して情報を受け渡ししている。

第10回

情報社会の方とジレンマ。まずルールの定義から。個人のルールが人格、個人同士なら約束、個人と社会なら法となる。法は約束と違って生まれる前からある。

クリエイティブコモンズライセンスについて。著作物とパブリックドメインの中間のこと。一定の条件を守ったら自由に流通させていいというもの。CCマークを付ける必要がある。

オープンソース・オープンデータ。だれでも利用できる。そういえばなんでオープンにするんだっけ?

他にもいろいろ法律がある。特許、個人情報保護、出会い系サイト規制法とか。

情報社会における倫理的ジレンマについて。まず善から。人の生命と約束どっちを守るべきか。善悪は数量化できるのか。2人の生命のために1人を殺す vs 5人の生命のために1人を殺す、とか。

徳の概念。本人としては矛盾していても約束相手と無矛盾ならよい?黄金律「人にしてもらいたいと思うことは、なんでも、あなたがたも人にしなさい(マタイ7-12)」。本当にそうか?いつも妥当はしないが仕事上なら妥当しそう。相互矛盾の一般的な方法はないが、ジレンマを解決する一般的な方法を学ぶことはできる、というのが先生の立場。

違法→合法、悪い↑善い、の二次元軸を考える。左上と右下がジレンマとなる。例えば戦地に海賊版DVDを持って行った人。著作権法に違反するが兵士は喜んだ。告訴するか否か。映画会社は訴えなかった。反発を恐れてのこと。

広島の中学生がUstreamでスマホで撮った東日本大震災のニュースを流していた問題。元NHKの広報の人、浅生さんにインタビューしてる。著作権法違反、放送法違反。でもNHKはインターネット配信がない。当時、インタビューした人はUStreamをむしろ拡散した。矛盾する行為だった。なぜそうしたか。NHKは公共のもの。公共を守るための著作権法、放送法だから、国民の命と財産を守るための手段は何でも使っていくべきという考えだった。公共の使命を感じていた。ジレンマにある、ルール違反をしているという認識はあった。ジレンマに対する考え。ルールと良心の対立。だれが線引きをするのか。自分が信じている善と社会の善の対立。ジレンマの解決方法は。決まり事を破ったら何かいいことがある場合は、決まり事を変えるのが長期的な解決だが、短期的にはそうはいかない。世の中がどうなるかを考えるしかない。そのためには知識が必要。ルールを知って、ベネフィットも知って、その上でどうするか。知った上でジレンマを抱えてから、あえて踏み込む。そうすれば世の中がよくなるのではないか。先生は、責任をもって浅生さんが行動したと判断した。

優先すべきは?より多くの人が幸せになること(功利主義)?多数の不幸よりも一人の命を救うこと?ここから先は倫理と道徳の問題になる。日本人は命を重視しがちだそう。心の準備をしておくことが重要と先生は言った。

最後にハッカーについて。MITの鉄道模型の同好会の用語らしい。線路をどうやってつなぐかということから出てきた。なので熱心に行為を行う人のことを指す。ハクティビズム。ハッキングして社会を変えようとする人。リークしたりツールを公開して、政府や企業の変化を促す。もちろんテロの一種。先生としてはもっと別の方法を使えばいいんじゃないのと言っている。

第11回

インターネットでのトラブルについて。今日からは花田経子先生。情報教育の人らしい。子どもに焦点を当てた話をするそうだ。

分類。SNSでのトラブルとサイバー犯罪に結びつくトラブルの2つ。犯罪件数自体は減っているが、サイバー犯罪は増えている。不正アクセスは14-19歳も結構やってる。被害者になるだけではなく、加害者になるパターンも。

SNSでトラブルがあった子は10%。少ないようだが軽微なものは多分含まれないので意外と多いような気がする。内容は書き込みに関するトラブル、嫌がらせ、ワンクリック詐欺、マルウェアなど。出会い系サイトは減少したが、出会い系サイトでないサイトからの被害は増えてる。児ポの製造分類は、自画撮り送信が一番増えてる。

なぜ被害に遭うのか。犯罪者が友人を装って女の子に画像送信を促す。「私も画像送ったんだから~」とか言って。ただし犯罪者が使うのは他人の画像。女の子を追い詰めて画像を送信させてしまう。あとグルーミング。悩みを聞くふりをして、など。

トリガーとなる行動。パパ活などの問題行動画像を送信するとか。そうすることで被害者に落ち度があると認識させ、実態把握が困難になる。公表もできないから隠されたトラブルとなる。

こどもはどう解決しようとしているか。身近な大人に相談させる。むずかしくね?と思ったが相談者は、友人+保護者がツートップ。意外に保護者に相談してる。でも相談しづらい。SNSの知識が乏しいとか、説明が面倒、迷惑がかかる、話を聞かない、SNS使ってること自体注意される、普段から話をしないとか。発達段階的に自分で問題を解決したい時期だが、それでは問題が悪化する。

こどもをまもるために。コミュニケーションを密にしておくこと、適切な知識を有しておくこと。いざというときの相談相手として認識される様にせよ!!まったくそのとおりだ。

SNSの使われ方。子どもの世代に多いのはオンゲ、SNS、eラーニング、LINE、動画。少ないのはメール、検索(!?)、ショッピング、ホームページ。

目的に応じて使い分けてる。twitter, LINEは一般的・汎用的な使い方をし、個人的に仲のいい子とはインスタやTikTokらしい(そうなの!!??)。複数サービスは同時に使う。オンゲはDiscord、ツイキャス。大人がたくさん利用しているサービスは避ける。例えばfacebook(たしかにおっさん専用SNSだ)。twitterは大人との使い分けがある。インスタは24時間で消えるストーリーが好まれる。あと利用目的に応じた複数アカウント。twitterを1アカウントで全部やってる私はおっさんなんや。若者の52%が複数垢らしい。中央値は3個らしい。若者は休眠垢をもつ。一番多いのはパス忘れ。あと、若者にはアカウント概念自体がないので、休眠垢を消さないで放っておくらしい。

垢分類。通常垢・裏垢・趣味垢・勉強垢・取引垢・共同垢の6つ。

問題垢。エロ垢・売り込垢・病み垢・捨て垢。通報対象になる。病み垢は座間事件でも有名。

SNSにおけるコミュニケーショントラブル。よくあるのは裏垢の暴露。メッセージアプリで発生しやすい。恋人関係の人と互いにパスワードを教えあったりするそうだ。で、兄弟とか友達に裏垢の内容を見せたり、晒されたりしてしまう(自殺例も)。他人に見られたくない情報は裏垢に出すなよ(難しそう)。

誹謗中傷。弁護士への誹謗中傷、脅迫、嫌がらせなど。少年少女が多数関連。

寿司店のアルバイト店員が店舗内で悪ふざけ、SNSにアップロード→店以上に、店員に個人攻撃、私的制裁。

偽情報。トイレットペーパーが無くなるとか、偽爆弾情報とか。

第12回

情報倫理教育。1970年代に情報公害という言葉が使われるようになった。公害が社会問題になっていることに対応する。背景としては、マークシートの浸透とか、切符の発売システムMARS、銀行間決済のネットワークの誕生など。道具が変化したから不安を持ったというのが先生の分析。

20世紀の情報倫理の出来事。1985年、James Moore “Computer Ethics”。94年、山本など。95年は辰己先生も研究してる。95年はネチケットって言葉も出た。

情報モラルという言葉。モラルっていうのは2人における関係性、特に約束・義務のこと。情報モラルっていうものはないのではないか。87年に教育審議会で情報モラルに言及、2010年にモラル指導者研修ハンドブックってのが出てる。2007年で「情報社会を生き抜き、健全に発展させていくうえで全ての国民が身に着けておくべき考え方や態度」、2008年は学習指導要領にも入った。これはルールの押し付けだというのが先生の考え方。

コールバーグ先生。道徳性発達の6段階。罰回避→最終的には良心へ。先生は重要視している。情報モラル教育は、道徳性の発達に配慮しながら行うべきと先生。心的能力のレディネスに合わせる。子どもはみんなDigital Nativeだという前提で。

海外でもインターネット教育は大事、韓国では3-9歳の83%が利用している。いじめ、自殺も起きている。SunFull運動。善良なコメントを書き込むべきという運動。

2012年、辰己先生が実施したアンケートでは表計算とかプログラミングは学びたいが、著作権、メディアリテラシーとか個人情報とかは別に学びたくないらしい。初等中等教育での情報モラル教育は大学生の情報倫理教育に悪影響があるのでは!!??という先生の主張。以降行為については教えられるが、活用について全然教えてもらってないのでは。具体的には違法っぽいが法解釈すると合法になるような例とか。9回目でやったようなジレンマのことを教えてない。違法でも善、のようなことは学校では教えられないのか。

デジタル・シティズンシップについて。2007年ISTEで提唱。デジタルエチケットとか規範、権利、プライバシーとか。

鳥取県情報モラルエデュケーターの今度珠美先生にインタビュー。教育業界に関わって、いわゆる情報モラル教育(あれはやってはいけないとか)に疑問をもったひと。デジタル・シティズンシップでは、安全かつ責任を持つ、倫理的にふるまう、知的創造を阻害しない、価値観の違いに配慮、ICTの特性を良き利用に結びつけるなどが大事になる。悪影響だけじゃなくて、日常的に活用することで、創造的な活動に結びつけられるよ、あと、公共的なことを学んだらよい使い手に育成できるよ、ということを教でえていく仕事だそう。責任、という言葉が繰り返し登場する。デジタル機器を使う責任。なんだか誇らしい気持ちがしますね。子どもにも響くのではないか。

人権が大事だねーと辰己先生。扱う人の問題。今度先生は今後どうするのかというと、人権問題の研究もしてきたので、日本版のデジタルシティズンシップに人権意識も組み込んでいくそう。活用しない→活用しよう、という教育の方向転換を目指す。

第13回

技術者倫理と人材育成。ゲストの中西先生。

倫理教育から。工学教育プログラムにはABET、JABEEという認定評価制度がある。地球的視点からの能力を教育するらしい。畑村先生の失敗知識データベースが出てきた。JABEEを放送大に適用すると、情報セキュリティに対する責任の理解も教育目標の1つとなる。

チャレンジャー号爆発事故。ブースターの継ぎ目からガスが漏れて爆発。安全が第一でキャリアは次だというインタビューがあった。倫理的ジレンマとしては、雇用主への忠誠と、交易を守るための通報の間のせめぎあいがある。日本の原子力学会の倫理規定でも、公衆安全を優先、速やかに公開せよと言っている。

内部告発と公益通報者制度。これ慶應の労働法でやったな。公益通報者保護法。2020年改正で退職者とか役員が保護対象に、通報窓口の義務化など。

人材育成について。阪大セキュリティ本部の猪俣先生にインタビュー。ものづくりのセキュリティはどうするか。オフェンシブセキュリティにとりくむ。実際に攻撃してセキュリティを確かめる。攻撃者の考え方を知る。弁護士の先生も呼ぶ。

ICMPの可視化。すげーな。

enPitにおける人材育成。大学と大学院でそれぞれカリキュラムがある。基礎、演習、専門、先進演習科目がある。

次はNECでのインタビュー。NECセキュリティでは何をやっているのか。現状把握→システム構築→運用までを行う。セキュリティの監視とは何か。センサーを付けてここから怪しい動きがないか監視している。センサーを企業において監視はNECで行っているらしい。教育としては、スキルの底上げ、人材育成のプログラム、トップセキュリティ人材の教育を行う。海外のSANSという団体に派遣したりもしている。倫理観の育成はどうするか。座学と実践(具体的には何やってるんだろ)。100-1はゼロだと言っている。何かコンプラ違反があったらもう終わりなんで、気を付けよと言っている。経営陣にはどう説得するか。投資ではなく経費と言っている。投資はリターンがいるけど経費はそうではないものね。

第14回

中高、大学、生涯教育でのセキュリティ教育について。

情報モラル→危険の回避がメイン。中学の技術家庭では機密・完全・可用性、多要素認証や二段階認証まで習うらしい。高校。情報Ⅰでももちろんセキュリティを習う。CIA等はもちろんデジタル署名、サイバー犯罪とかまで。情報ⅡではDMZ、ファイアウォールとかも全部習う。情報セキュリティという科目も追加されたらしい。ほぼほぼこの科目と同じ内容。情報セキュリティの要素はCIAのほかに真正性、信頼性、責任追跡性、否認防止を入れて7要素としている。

大学。Computing Curricula 2020というカリキュラムがある。CS, IS, SE, CE, ITのほかにCSEC(サイバーセキュリティ)+データサイエンス。

情報倫理デジタルビデオ小品集7ってビデオがある。放送大(山田先生)が作っていたらしい。DVDか。ネットで見れるようにしてくれよ(放送大の人は見られるらしい)。

Niiが作ったやつもある。倫倫姫のセキュリティ教室というのがある。

倫倫姫の情報セキュリティ教室 – 事業 – 国立情報学研究所 / National Institute of Informatics (nii.ac.jp)

大学で加入してたら見れる(私は見れない)

知識体系。SecBok2021というのがある。

猪俣先生にまたインタビュー。enpitやSecCapについて。セキュリティはもうブランディングの問題になっているらしい。

生涯学習について。インターネット安全教室、青少年インターネット環境整備法がある。IPAがけっこう教育行事やってる。セキュリティキャンプとか。最近の攻撃はスマホ決済、フィッシング、デマ。

また猪俣先生。2004年MSBlasterウイルスというのがかなりでかいインシデントだった。そこから勉強会をやろうという雰囲気ができて、無料の講座がいっぱいできた。高槻市でもやってる。総関西セキュリティ大会は400人くらい参加している。初級者向けリレー講座もある。

第15回

展望と発展学習。全員が登場する。

まず大西さんの質問が4つ。知らん人が脆弱性をついて攻撃してくることは→ある。ゼロデイ攻撃という。ログ採取用のソフトウェアLog4jが攻撃されたりしている。攻撃に必要なソフトウェアが高い価格で取引されている。

ゼロトラストは負担にならないか?→負担はある。なるべく負担にならないようにしないといないけど。

学校教育ではどうなっているか→まず情報活用能力の育成。情報モラルカリキュラムがかなり細かく設定されている。高校まである。2006年策定らしい(古い!)。しかも改訂されてない!やばっ

情報セキュリティ概論の後に学ぶことは?→基本が理解できているか確認せよ。J17の知識体系あたりを参考に。情報Ⅰでもカバーしている。放大には演習科目がないのが問題だなあという話もした。

座談会。人材育成の課題と展望。徳島の病院でランサムウェアでカルテが読めなくなる被害。カルテを手書きにして診療を再開した。なんとDMATが対応した。すげー。情シスが1人しかいないのも問題だった。専門用語で話せるような人が必要、情シスだけでなく外部業者に委託も考えよとのこと。3大温泉シンポジウム→セキュリティのイベントらしい。温泉なのに?夜通し情報交換をしているらしいです。花田先生も越後湯沢の実行委員らしい。

こどもの情報セキュリティ。性的コンテンツが経済的価値を生んでしまう。トリガー行動を行うことも、被害に巻き込まれてしまうこともこどもの責任ではない、大人の責任。大人に知識がないのもダメ。高校大学となっていくにしたがって、知らない人と出会う機会が増える。今までに人と会うなと言われていたのに、今度は会わないといけない。ジレンマが生じる。花田先生は18未満と以上を分けたらと言っているが辰己先生はいきなり大人になるわけではないので・・・と懸念を示している。なのでトレーニングをしないといけないな、という共通認識が得られた。

AIとセキュリティ。AIを使ったセキュリティの実現。もう結構実用されてる。ログ検知、パケット監視、マルウェア検知に機械学習が使える。教師データが必要だけど、教師データが間違っていることがあり得る。twitterにチャットボットを作ったら、よくないことばっかり教えるやつが出てきた。それで閉鎖された。教師データを作るのが難しいってのが現状。

AI自体のセキュリティも問題になる。教師データが盗まれたりしないか。大西さんが解説。教師データに問題がなければAIはおおむね想定通り動作するが、問題のあるデータがあると問題のある振る舞いを学習する。データ量は多いので監視は無理。

これからの学習のアドバイス。辰己先生→アップデートを常に。ジレンマの問題は、ジレンマに陥っているかどうかを認識しないといけない。金岡先生→セキュリティはあらゆるところにあるので、セキュリティという側面をいろんな事象に当てはめてみるとよい。花岡先生→大人に知識がないのが問題なので、知識つけてね。子どもとの関係性も学ぼう。中西先生→Cybersecurity for all, by all。草の根活動に参加するといいよ。山田先生→この科目を基礎として、知識は最新のものにしてね。大西さん→アップデートしていかないとな~

放送大学全科目感想 019 コンピュータ通信概論(’20)

  • 情報コース
  • ラジオ科目
  • 葉田善章先生(放送大学准教授)
  • 難易度 ★★★☆☆
  • おすすめ度 ★★★★☆

通信の基本を物理的特性から学び、だんだんと高次の話に移行、信号の表現の仕方や電気信号・電波の話、多重化などの基本技術、さらには放送、IoT、WiFi、GPSなど豊富すぎる話題の欲張り科目。テキストも300P程度と分厚い。練習問題とその解答も充実している。先生の熱意が伝わってくる。序盤には一部数式も出てくるが無視してもよい。添削問題の分量が多く(25問)、試験問題も多いと予想される。

第1回

先生の声かすれててちょっと聞き取りにくい。通信の概要について。シャノンとウィーバーのモデルも含めてだいぶ知ってる話だったので特筆することは無し。

第2回

情報の物理的通信路について。無線がメインでかなり詳しい。電波損失って周波数の二乗に比例して大きくなるのね。だから携帯の電波塔はいっぱいあるのか。wifiのチャネルは以前設定したことがあるからだいぶイメージわく。遅延波とか波の干渉(フェージング)って物理的にはどう対応しているのか?すごく気になる。技術として知りたい。

第3回

信号の表現について。三角関数の数学的な話が続き後半はほとんどフーリエ変換の話。ラジオでは非常に厳しく、テキストに載っている数式も概略だけで片手落ちな感じ。もっと詳細に知るにはフーリエ変換を真面目に学ぶしかなさそうだ。

第4回

A/D変換や標本化の話。量子化やサンプリングについてはほかの授業で既習。折り返しノイズという概念は知らなかったのでこれは貴重。ノイズが載らないようにするにはフィルターでカットしてやればいいらしい。

第5回

信号を遠くに運ぶための変調の話。信号波はそのままではまともに運べないので、長距離伝送に適した姿にしてやって遠くまで運ぶ。アナログ変調で有名なのはAM・FM。数式もついてるけどわかるようなわからんような。電子回路と組み合わせると理解が深まりそうだ。要参考文献。デジタル方式ならベースバンド伝送。これも具体例の電子機器が示されておらず、概念的にへえそうですねと納得するしかなさそうだ。要参考文献。

第6回

デジタルに特化した変調について。AM、FMに相当する変調はわかりやすいが、位相を変化させるという位相偏移変調(PSK)あたりからわけがわからなくなってくる。さらにcosとsinを同時に発することでデータ量を増やす直交振幅変調(QAM)は概論としてはわからなくもないが、数式が意味不明。複素数を使うと2次元表現できて分かりやすいね!と言われてもわからんわ!と思う。まじでやばくなってきましたね。難しい。

第7回

多重化について。多重化とは一本の電線にできるだけたくさんの情報を載せるため、情報を並列に送るための涙ぐましい努力のこと。中でも今回はOFDM(直交周波数分割多重)を扱う。直交とは、波同士が干渉しないことをいう。OFDMでは、波同士が直交するようにうまく周波数を調整して、多数の信号を同時に送る。周波数同士を離さなくていい(ベースバンドが要らない)ので狭い範囲にたくさんの信号を乗せられる。原理はわかった。でも実装方法が難しくてよくわからん。

第8回

物理的な通信路、特に無線通信について。アンテナの仕組みが相当細かく説明されている。アンテナの長さは電波の半波長くらいの時に最もうまくいく。これが波長と同じ長さになってしまうと、波が打ち消しあって受信に向かない。ループアンテナみたいなものは、中学校の時に銅線を大きく巻いて自作してたなそういえば。田舎でFMが入りづらいので、自分の部屋の天井にぐるぐるしてた。

第9回

様々な通信路について。メインは第8回と同じアンテナの話。ただしアンテナは複数の場合。携帯電話は基地局が複数あるから、そのままでは基地局同士の電波の干渉が発生する。なので携帯側で指性を動的に変えて(AAA)、妨害波の影響を減らしている。干渉が発生しないということは、複数の基地局の電波を同時に使用できることでもあり、基地局の方も端末を複数管理できるから、通信速度が倍増する(MIMO)。すげー技術だな。

後半はOSI参照モデルについて。さらっと触れられているだけなので正直よくわかんないです。

第10回

身近な通信、というタイトルだが実質wifiの話。

wifiがなぜ発展したかというと、2.4GHz帯が免許のいらない周波数帯だったかららしい。電子レンジと同じ周波数帯なので干渉する。新しい規格の5GHz帯は、干渉はないが衛星通信には影響する。アクセス制御は有線LANと同じCSMA/CA。高速通信のためには多重化が必要で、第7回でも話の出たOFDMを使っている。エラー対応のため冗長化も行われていて、符号化率(送信データ/実際のデータ)は75%くらい。

次世代wifiではついにMIMOが採用されるらしい。CSMA/CAでアクセス制御しなくてもよくなる。家に基地局が設置されるようなもんだ。

第11回

携帯電話の仕組みの話。割と雑多な話の集合なので、気になったところだけ。

1G~4Gは多重化の方法が異なる。現時点最新の4GはOFDMA(直交周波数分割多元接続)という技術で動いている。MIMOが可能になったのは4Gから。5Gはほとんど説明がないが、高速化のための高周波数帯の使用などがトピックらしい。wikipedia情報だが低レイテンシ(低遅延)も目玉の1つ。DoCoMoだと3.4Gbpsでるらしい。ギガだって。頭の古い人間からするとちょっと想像できないね。

電話番号はパンクする速さがすごく、次は060の使用が開始されそうらしい。

周波数帯は高くなるほど伝送損失が大きいので、基地局が増える。

MIMOを実現するためには、超多素子アンテナ(massive MIMO)っていう100以上の素子を持ったアンテナを活用する。

第12回

IoTの話。今回も雑多な技術の紹介がメインのため、気になったところだけ。

IoTにはLPWA(Low Power, Wider Area)という規格を使う。速度を絞って、省電力とエリアの広さを取った規格だ。細かい規格は乱立しており、LoRa、SIGFOX、Wi-SUN、ZigBeeなど。もう少し近距離になるとBluetoothになる。携帯の通信網を利用したLPWAもある(セルラーLPWA)。

第13回

衛星通信と、海底ケーブルの話。

衛星放送は衛星一個で地球の120度の部分をカバーできるらしい。日本なんか余裕、北アメリカ大陸全部入っちゃうくらいか。すげー。レイテンシが0.24秒あることがちょっと問題。電離層による電波の減衰が少ないのは1GHz~10GHzあたりだそうだ。その確実性から船舶・航空機・自動車などで電話・パケット通信を実現している(MSS)。宇宙探索衛星(ボイジャーとか)との通信はアンテナ3つ張ればできる。200億キロくらい離れているので電波が来るまで20時間かかる。

海底ケーブル。光ファイバーを使う。衛星の1/8くらいの距離だからレイテンシが全然ない。世界の通信の99%は海底ケーブルである。ゲームのようなリアルタイム性の高いアプリでは低遅延が望まれるため、データセンターが直接海底ケーブルに接続されたり、データセンター自体が海底にあったりする。

第14回

放送の話。放送は無指向性だから出力が高い。スカイツリーは10kWで出力してるらしい。テレビ電波は普通水平偏波(地面に対して水平)だが、電波が弱い所では垂直偏波も使われる。伝送方法はOFDMが使われている。1チャンネルを13セグメントに分けて多重化している。携帯用のワンセグの名前はこのセグメントによるもの。おなじみB-CASカードには暗号化を解くカギ(共通鍵?)が入っているらしい。データサービスは、XMLを魔改造したBMLとか、BML専用ブラウザとか、結構ローカル技術が入ってる。

4K8KにはBS/CSが使われる。BSCSは周波数帯の違いがある(17GHz帯と14GHz帯)。そのまんまだとケーブルを通らないので、コンバーターを使って3GHz帯まで下げるんだけど、これがWiFiと干渉しやすいので注意。変調方法はPSK(BS)、QPSK(CS)。多重化の単位はスロット。1チャンネル当たり数十スロットが割り当てられる。デジタル放送は途中で符号化の方法を変えられたりすることが利点、強み。

第15回

今後の展望というタイトルだが、メインはセンシング・計測、特にGNSS(全球測位衛星システム)の話。先生が楽しくなって付加しまくったように見える。

GNSSとは衛星から出る電波を利用して絶対座標を算出することをいう。GPS(アメリカの衛星らしい)の精度補強のための仕組みがいろいろある。まず日本を対象とした「みちびき」という静止衛星システム。2018年から運用で、GPSを補完する役割をするがこれが強力でcm単位で計測ができるようになったらしい。他にも携帯電話通信網、WiFiアクセスポイントを使った相対位置測定で、特に日本の都市部ではかなりの精度が得られるようになっている。GNSSの副産物として、精度30万年分の1の原子時計を使った正確な時刻同期の仕組みも使えるようになった。

放送大学全科目感想 018 Webの仕組みと応用(’19)

  • 情報コース
  • テレビ科目
  • 森本容介先生(放送大学准教授)
  • 伊藤一成先生(青山学院大学准教授)
  • 難易度 ★★☆☆☆
  • おすすめ度 ★★★☆☆

webを中心としたネットワーク周りの話。HTTPの話が多い。慶應の図書館情報学でやったRDFの話もある。あまり深い話はせず、多種多様な話題を浅く広く学ぶ感じで、お手軽。後半の伊藤先生が楽しそうなのがよい。

第1回

森本先生による概説。森本先生若々しい。こういう同級生いた。

web以前はtelnetとかネットニュースとかあったね。あの人たちどうなってしまったんだろう。95年にwebがトラフィック1位になったらしい。webは一般名詞になったので小文字になった。

webといえばハイパーテキスト。ハイパーリンクのおかげで他のページに飛べるようになった(当時めっちゃ画期的だと思われてたな)。HTMLベタ打ちが紹介されている。テキサイだ!いまは阿部寛のホームページ以外では完全に滅びたよね。

webシステムについて。昔のwebシステムではURLとファイルが1対1に対応していた。静的なwebページという。サーバやクライアントの状態において、同じURLでも異なる結果を返すのが動的なwebページという。webシステム/webアプリケーションという。乗換案内とかショッピングとかネットバンキングとかね。SNSも当然そう。ソフトウェア不要、異なる端末からアクセスできる、更新が楽勝ってのが利点。欠点はwebアクセスしないと無理なこと、セキュリティの問題。

第2回

webの基礎。クラサバモデルから。ユーザ⇔クライアント⇔サーバのデータのやり取りで表現される。ユーザとクライアントの関係は、クライアントとサーバの関係そのまんまとも見える。

URLは構文がある。<scheme>://<host>:<port><path>?<query>#<fragment> らしい。言われてみればそうだ!httpsってhttpとどう違うんかよくわかってない。暗号化されていることだけはわかっているが、実装はどうなのか。相対URLの書き方。//から始めれば、実質http://の略と同じらしい。スキーム名は電話番号でtel:ってのもあるらしい。

リクエストメッセージとヘッダフィールド。空行までがヘッダなのね。GETメッセージにはHTML1.1って書いてあるが、1.1以上のバージョンはあるのか?ステータスラインの404って最近あんま見ないよね。ウェブページがサーバーへのリソースではなくクエリを使って動的表示されることが多くなったから、404より500の方が多い感じがある。メディアタイプはだいたい知ってたけど、octet-stream(任意のバイナリ)はしらんかった。

第3回、第4回

HTML/CSSを2回取り扱うらしい。内容はほぼ知っていたので略。まさか2022年にHTML/CSSベタ打ちについて教えてるとは驚き!

知らなかったこと一覧。HTML上のエスケープシーケンス(&quot;とか)は名前文字参照という。あとHTML5は2021年に廃止されたらしい。今は?(→HTML Living Standardらしいです)

第5回

HTTPについて。今の最新バージョンは2015年、HTTP/2。でもこの授業では1.1の解説をやるらしい。

リクエストもレスポンスも、リクエストライン/ステータスライン+ヘッダフィールド、空行、ボディという構成は変わらない。ヘッダはフィールド名: フィールド値という構成。

HTTPメソッドは8つ。GETのほか、POST、PUT(更新)、DELETE(リソース削除)など。

Refererってスペルミスだったのか!

キャッシュについて。webサーバーからは、キャッシュしてもよいかどうか、リソースの有効期限、最終更新日時、エンティティタグ(etag?バージョンを表す)が得られる。最終更新日時やエンティティタグを見れば、前回と同じリソースかどうかわかる。条件付きGETを送れば、304 Not Modifiedが返ってくるのでキャッシュが使える。キャッシュの可否は、Cache-Control:タグで返ってくる。クライアントからは、GETのあとにIf-Modified-Sinceとか、If-None-Matchタグをつけてやれば、条件付きGETを作ることができる。

持続的接続について。TCP接続を切るかどうかの話。持続的接続をすると負荷が軽減できる。Connection: Keep-Aliveを使えばよい。

第6回

動的webサイトについて。随時変化するサーバー情報、データベース内容のGETとか。ヘッダーでリソースを変えることは、コンテントネゴシエーションという。Accept: とか Accept-Language: で指定したメディアタイプによってサーバーが返してくるリソースを変える。一番よくあるのはクエリやメッセージボディでの指定。ここまでの3つは全部組み合わせられる。

で、フォーム?突然技術が古くなった感じ。フォームデータを+とか&とか=とかで加工する古い方法が出てきたが、これってセキュリティ的にやばいやつじゃなかったっけ?POSTで送信する場合は暗号化できたりするんかな。httpsだと勝手にやってくれるのか?(→TLSという技術を使うらしい)

第7回

RDBMSについて。「データベース(’17)」とかぶってるので略。

第8回

クライアントサイドの技術について。描画処理とか、ユーザ操作に対する再描画とか。JavaScriptを使って表示を変えたりすることもこれに該当する。

JavaScriptが出てくると、HTMLの解釈が一旦停止になるらしい。そういえばページ表示してから実行したかったら、何か特殊な実装をしていた記憶がある(→AddEventListener(“load, …)でやるって説明あった)。JavaScriptの具体的な操作は、知っていたことばっかだったので略。まず

第9回

認証とセッション。基本はIDとパス。注意点については情報セキュリティ概論とかぶってるので略。

HTTP認証。まずBasic認証。何も指定しない場合、WWW-Authenticate: Basicが返ってきて、ID+パスを問われる。Authorization: Basicで返してやる。ID+パスはBase64エンコードで送るけどこれはデコードもできてしまう。ヘッダを見られたらアウトになってしまう。Digest認証を使うとMD5でハッシュ化するので安全。

フォームベース認証。INPUT要素のフォームを使う。これもコンテンツ内にべた書きになってしまうので危険な気がする。

セッション。ブラウザとサーバーのやり取りの1単位のこと。検索→商品ページ→購入→情報入力→確認→完了までとか。HTTPはセッション管理がない(ステートレス)ので、同一ユーザーの推定をすることになる。使う情報はIP、UserAgent、Refererあたりが考えられる。アクセス解析はこれを使ってる。しかしIPは同一ユーザでも変わることがあるし、LANから来たら同一IPから複数アカウントが来ることもある。なのでこれはセッション管理としては使えない。なので、毎回認証用の情報を送受信するという手もある。WebブラウザがAuthorizationヘッダを記憶しておいて、毎回送信する。でもこれも面倒。

これを解決するためにCookieを使う。Cookieとはwebサーバーがwebブラウザに記憶させるデータのこと。サーバとブラウザが毎回保存しておいたCookieをやり取りすればよい。webブラウザからはSet-Cookieヘッダが返ってくる。idが入っているので、ブラウザはリクエストのヘッダに毎回Cookie; id=XXXX を送ってやればいい。クッキーには有効期限や有効なドメインなどを指定できる。クッキーにはショッピングカートの商品番号を入れたり、様々なプロパティを保持させることもできる。けど、後述のセッション管理を使うことが多いから、あんまりやらない。セキュリティ上もよくないし。

クッキーによりセッション管理。セッションIDを含むクッキーを発行する。webサーバー側でユーザ固有の情報をセッションIDと結び付けて保存しておけばよい。例えばID+passを送ったらサーバーはセッションIDを返す。ブラウザ側はあとは毎回セッションIDを送ることで認証済みであることを示すことができる。ログアウト時はクッキーを削除する。削除するという命令はないので、例えばクッキーのExpiresを過去にしてしまう。

シングルサインオン。専用の認証機構で一度認証を受けると、横断的に別のリソースを使うことができるようにする。放送大の認証システムや、keio.jpなんかがこれに該当する。IdP(認証局)とSP(サービスプロパイダ)間の直接の通信はない。

第10回

webのセキュリティ。盗聴、不正誘導、攻撃、なりすましについて。

盗聴を防ぐにはTLSを使う。TLSはSSLが元祖。認証には証明書を利用する。認証局から発行されたものが信頼できる。クライアントから証明書を送って、サーバからサーバ証明書を送ってもらう。TLSはTCPとHTTPの真ん中の層として提供される。HTTPと合わさってHTTPS, HTTP over TLSを作る。

ルート認証局の信頼性はどう確保するか。webブラウザ内に保存される。(ちょっとここらへんはわからんかった)「安全な接続ではありません」的なメッセージが出るのは、証明書の検証に失敗しているということ。

フィッシング。偽サイトに誘導してパスワードなどを搾取すること。以下略

webシステムの欠陥について。脆弱性をついた攻撃について。ヘッダに不正なデータを含めたり、存在しないパスを指定したり、メッセージボディにデータをつけたりすることが考えられる。

SQLインジェクション。パスワードに ’’ OR ‘a’ = ‘a’ と入れる。すると、SQLではORが優先されるため、’a’ = ‘a’ が成り立ち、無条件でSELECT文が通ってしまうというもの。

クロスサイトスクリプティング。フォーム送信するデータの中にJavaScriptを入れる。img src=の後に別サイトのURL+クッキーのデータをエンコードするコードを入れて、クッキーを別サイトに送信させること。

セッションハイジャック。セッションの乗っ取り。ここまでの技術を利用してセッションIDを詐取すればできる。

第11回

大規模webシステムについて。冗長化と負荷分散から。予備システムを用意して、システム障害児の即時復旧を図る。コールドスタンバイ方式(予備システムは通常時は停止)とホットスタンバイ方式が(予備システムは常時稼働)ある。負荷分散はリクエストを複数のサーバーに振り分けること。障害発生時も残りのサーバーで処理できるので可用性が高い。ロードバランサを使う。他の実現方法としてはDNSラウンドロビンがある。同一ドメインについて複数のサーバーを割当てているDNSをそのまんま使って負荷分散をすること。あとリバースプロクシ。ネットとサーバーの間に挿入され、サーバへのアクセス要求を転送する。

データセンター。コンピュータやデータ通信機器などの装置を集中管理するところ。電源が大事なので自家発電装置、UPSを多数配備する。発熱するので空調も大事。あと免震、床の耐荷重も必要。監視カメラ、ICカード認証、高速ネットワーク回線もいる。

IIJのデータセンターにインタビューしてる。広報部課長の堂前さん。昔は電算センターと言ったらしい。いまでは大規模データセンターの一部を借りることが多い。事業者の業務はコンピュータ設置場所の貸出がメイン。電気系統やネットワーク、ラックを提供する。コンピュータ設置の依頼もできる。セキュリティオペレーションセンターに監視を依頼することも可能。建物の特徴:大量のケーブルのため50cmの空間がある。耐荷重、免震も大事。免震がないと地震の際にコンピュータがぶつかって壊れる。エンジニアが出入りするのでセキュリティカードをゲートに通さないとダメ。6600Vの受電装置。非常用発電機。道路工事などで断線しないよう、通常と異なった電気の呼び込み。ラック1個で一般家庭数件分の電力を消費するらしい。あと最近はGPGPU(画像演算CPUの目的外使用)が増えてきて、消費電力が高くなってる。ラック一個で中型電気ストーブ10個分。空調装置が故障すると終わるので、空調装置にも冗長性を確保している。

IaaS、PaaS、SaaS。他でやったので略

CDN。Content Delivery Network。アクセス集中を避ける技術。複数のサーバーを用意してミラーリングする。これもIIJにインタビューしている。メーカー新製品発表会とか、ゲームのアップデートの時にアクセスが集中する。大量の設備を用意するのはコストがかかりすぎ。なので従量制のCDNサービスを利用するとよい。CDNは光回線の物理的遅延を回避するのにもよい。セキュリティ対策としてもCDN事業者に外注できるから有利とのこと。

HTTP/2。リクエスト/レスポンスの多重化の方法が1.1と違う。1.1はTCPコネクションを複数確立する。2ではストリームという仮想的なチャネルを使う。ヘッダもバイナリ形式になり、圧縮して差分だけ送信する方式になって効率化されてる。サーバプッシュ機能。リクエストなしでサーバーからコンテンツが来る。キャッシュも使える。1.1との後方互換性もある。ブラウザとサーバのどちらかが古ければ1.1を使うようにできる。

第12回

検索エンジン。クローラ、インデクサ、検索部からなる。クローラはwebページの選定と制御部分からなる。収集は再帰的に行える。クローラは複数同時に動くので制御が必要。同一ページを収集しないようにしたり、重要度をつけたりする。

インデクサは索引情報で、形態素解析を使って単語に分割したり、一定の文字数を切り出したりする(N-gram)。webページはHTMLなので、タグ構造を踏まえた解析を行わないといけない。

検索部。キーワードとインデックスを照合して、webページをランキング形式で提出する所。検索部の処理は世界中のデータセンターに分散している。

PageRank。webの構造を解析してランク付けする。具体的にはバックリンクの数が多いページを重要なwebページとし、ここからリンクを張られているページも重要な頁とするものである。算出式は卒論にも書いたので略。Σがあるからどうやって計算するのだろうと思ってたが、何回も計算して収束するまでやればいいらしい。

HITS。Hyperlink Induced Topic Search。動的にランキングを作る方法。検索結果に適合したページの集合をR(ルートページ集合)とし、ここからリンクを張られているページの集合を考える。HITSではHubとAuthority問概念を使う。Authorityとは、多くのwebページからリンクを張られていること。これを値で表現する。Hubは、多くの権威あるページにリンクを張っているページのこと。これも値にする。HITSではこの2つを使って重要度を算出している。

接続行列。iからjへリンクが存在したら1、なければ0になる行列のこと。Authority値をa1~an、Hub値をh1~hnとして、初期値は全部足したら1にしたあと、接続行列をかけたり、L1ノルムを正規化するということを何回も続けていく。するとだんだん収束していく。これをAuthority, Hubの最終的な値とする。実は接続行列の固有値を求めることでも計算できるので、こっちの方が楽。

マルチメディア検索。テキスト(メタデータ)に基づく方法(TBIR)と、画像特徴量に基づく方法(CBIR)の2通りがある。画像でも音声でもやることは同じ。

第13回

セマンティックwebとリンクトオープンデータ。セマンティックwebとは、人間と機械とのコミュニケーション実現を目指すwebのこと。意味情報の記述にはRDFを使う。

RDFはリソース、プロパティ、プロパティ値の3つの組(トリプル)でリソース間の関係を表す。主語、述語、目的語に相当する。http://kazuanri.org→(dc:creator)→伊藤一成なら、http://kazunari.org がリソース、伊藤一成がプロパティ値、dc:creatorがプロパティ。どれもURIで表記する。プロパティはリテラル(文字列や数値)も指定可能。RDFはXMLを使って表記する。スペース区切りのTurtle形式もある。プロパティ値をURIにすれば、リンクと同様になって関連を表すことができる。

ダブリンコア。あらゆる情報資源に付与可能な語彙集合のこと。titleやcreatorなど15要素がある。図書館情報学でやったな。

ダブリンコア拡張語彙(DCTerms)。dctermsをつける。より厳密なメタデータ記述ができる。available, created, dateなど。foaf(friend of a Friend)というのもある。foaf:knows(知ってる人)とか。

語彙の定義づけはRDFS(RDFスキーマ)で定義する。例えばライオン(S)が肉(O)を食べる(P)は意味をなすが、朝顔(S)が肉(O)を食べる(P)は意味をなさない。これはどうやって定義するのか。クラスを用いる。OOPLに近い。rdfs:Resourceが基底クラス、rdfs:classがクラスそのもの、rdfs:Literalがリテラル値・・・など。他にも下位インスタンス、サブクラスを表すプロパティもあるし、リソースであることを表すプロパティもある。

スキーマ定義の例。これは文字で表すのは難しい。rdfs:typeとかrdfs:SubClassOfとかを使って関係性を記述していく感じ。現実世界をクラス化してrdfs:で構造化していくようなことをするのかな。

OWL。Web Ontology Language。概念間の高度な関係を表せる。犬と猫は互いに素とか、年齢は0以上の整数とか。難しいのであまり実現されてないらしい。

リンクトオープンデータ(LOD)。個々の情報をまず共用することを優先しようとする試みのこと。政府、図書、メディア、ライフサイエンス、地理情報などで使われている。すでにLODのクラウドができている。

5スターオープンデータ。オープンライセンスを使う、構造化データを使う、非独占形式を使う、URIを使う、他のデータへリンクする。これを守るとLODにしやすい。

DBpedia。wikipediaからLODを生成するプロジェクトのこと。

SPARQL。RDFの検索に使うクエリ言語のこと。SQLに似てる。

第14回

HTMLテクノロジ。HTML5では大きな機能拡張があった(廃止されてなかったっけ?)今ではスマホ対応など多様な環境を前提にしたwebシステムを作らないといけない。例えばデバイスごとにCSSを切り替えるとか、user-agentに応じてページを切り替えるとか。

センシングデータの利用。先生が作ったGOSEICHOというコンテンツを見る。

GOSEICHO

スマホを裏返すと「ご清聴ありがとうございます」というというアプリ。デバイスの軸を検出する仕組みがある。alphaがZ軸、gammaがy軸、betaがx軸「を中心とした回転」を検出する。回転なんだね。javascriptの実装としては、deviceorientationイベントをゲットすればいい。abs(e.beta)が170↑、abs(e.gamma)が10↓なら裏返しと判断する。なるほど!

SVG。HTML内にインラインでSVGを書ける。アフィン変換すれば位置や向きも簡単に変換できる。transform=”translate(100. 20) rotate(40)” などと書けば平行移動+回転ができる。JavaScriptと組み合わせて、図形を要素とみなして操作も可能。

ストレージ技術。WebStrageを使えばローカルストレージを使うことができる。形式はキーバリュー(KVS)。Local Storage(期限なし)とSession Storage(セッション終了まで)がある。

リアルタイム双方向通信。今まではAjaxを使ってた。これはクライアント側で動作し、ブラウザでポーリング(定期的にリクエストすること)していた。一定時間ごとに更新の有無をチェックするので、無駄が多い。

Comet→サーバ側でリクエストを保留し、任意のタイミングでレスポンスを返す。コネクションを維持しておき、更新があったらレスポンスを返す。無駄がないがTCPコネクションを占有するのが欠点。これはHTTPの限界と言える。

これを克服するのがWebSocket。まずハンドシェイクでコネクションを確立。プロトコルが確立したらあとは双方向通信を行える。JavaScriptではonmessageイベントとして処理できる。

第15回

WoT時代のwebについて。IoTはデバイスやネットワークが標準化されていないので、インタフェースを統一したい気持ちがある。これをWoT(web of thing) という。

Web API。サーバが提供するAPIのこと。WoTの前提となる。APIのデータ交換にはJSONが広く使われている。JSON形式のライブラリは充実しており、相互運用性を意識することなく利用できる。

JSONにはスキーマがないので、スキーマ付きのものとしてJSON-LDがある。リンクトオープンデータを表現できる。

REST。Representational State Transfer。クラサバが原則、インタフェースは統一、ステートレス(情報や状態の保持なし)、キャッシュ可能、階層型システムという5原則を満たすこと。これを満たすとネットワークを状態機械として扱える。ROA(Resource Oriented Architecture)。リソース指向のアーキテクチャ(?)。識別子にはURIを使う。Restful WebAPIの実装では、CRUDをPOST, GET, PUT, DELETEのHTTPメソッドに対応付ける。

WoTの実例。モータ、LED、光センサをつける。これをROAで階層化しておく。例えばGETメソッドで光量をJSONでゲットできる。POSTでサーボモーターの回転方向を移動させられる。実際にロボットを動かしてる。かわいい。先生がなぜか人形と同じ格好をしている。

KDDIの高木悟さんにインタビューしてる。スマホでアプリケーションを動かす時代なので、ブラウザが大事。KDDIの仕事が増えてる。W3Cにも関わっている。GitHubを中心に標準化のプロセスを議論してるらしい。全部オープン。W3Cの勧告は仕様書と同時に実装がないといけないらしい。ブラウザとOSはほぼ同じ概念になりつつある。webOSという考え方もある。WoTの考え方が浸透し、画面表示できるものなら何でも動くという時代になった。

WebDINO Japanへ。瀧田さん。mosaic時代からブラウザに関わっているらしい。多言語対応を行っていたらしい。CHIRIMENというコミュニティがある。ハードウェアをフルオープンにしようというプロジェクト。ラズパイを使って、ブラウザ上で動く開発環境を作っている。センサーの状態がブラウザで簡単に見られるようになっている。サーボもJavaScriptで操作可能。コードはHTMLとJavaScriptを同時に表示し、簡単に編集できるようになっている。すげー。

WoTの未来。Webがプログラム可能、知識表現の構築、即時処理、活発な交流がキーワードとなる。

放送大学全科目感想 017 データベース(’17)

  • 情報コース
  • テレビ科目
  • 辻靖彦先生(放送大学准教授)
  • 柴﨑順二先生(放送大学教授)
  • 難易度 ★★★☆☆
  • おすすめ度 ★★★★☆

AccesなどでSQLを実際に使っていく、という講義ではない。データベースがなぜ使われるのか、数学的な定義は何かというところから掘り下げていくので、特に辻先生担当の所は難解な部分もあるが、データベースが有利な点についてかなり具体的に学ぶことができる。リレーショナルデータベースを中心とした講義で、後半はRDB以外のデータベースについても学ぶ。

第1回

イントロ、辻先生。

データを体系的に収集・加工、効率的に管理・運用するのがデータベースで、中核的な要素であるとのこと。例えばWAKABA。個人情報や成績・履修情報を管理できる。他にも銀行システム、ネット通販システム、顧客管理システムなど。いずれも業務に密接にかかわるデータの塊を持っている。目的を満たすための必要なデータ、実世界で必要な規則を取り扱うことが望まれる。実世界に沿ってデータベースの構造も変わっていく。

データベースとは、この授業では、目的を持った一定のデータの集まりと定義する。

ユーザーには誰がいるか。データベース管理者とアプリ開発者、それからユーザーがいる。普通は管理者と開発者が同一のことが多いような。

データモデル作成について。実世界→概念データモデル→論理データモデル→物理データモデルの3段階がある。いずれも別々に設計が必要(物理の方はあんまやらないかな)。論理データモデルの例としてリレーショナルデータモデルがある。いわゆるRDBMS。

データの整合性の維持。これはデータモデルで実装できる。例えば、学生の学籍番号の一意性とか、学生が必ず学籍番号を持たなければいけないとかは、データモデル自体に制約が内包されている。これが重要な機能の1つ。

データベース言語には、データ定義(DDL)、データ操作(DML)、データ制御(DCL)がある。データ操作に相当するのがSQLかな。

データ格納方式は木構造、ハッシングなど。検索は効率的に、高速に行われないといけない。

機密保護について。アクセス制限、権限の付与を行うことができる。

同時実行制御。処理単位をトランザクションと呼び、並列処理が可能になる。ロック機能も必要。

三層スキーマ構造。外部スキーマ(見え方、ビュー)、概念スキーマ(テーブルの設計)、内部スキーマ(物理的格納方法)の3つ。それぞれ独立性をもって、どれか1つを変更しても他に影響がないようにしている。

データベースを使う利点。データの整合性の保持が最も重要。副次的な要素として、効率の向上や機密保持、同時アクセスへの耐久性なども挙げられる。

最近登場したNOSQL(Not Only SQL)について。ビッグデータなど膨大で複雑な構造のデータを高速処理する時に使われる。

ここまで駆け足のイントロだったが、この後は講義全体の構成。技術的な話も押さえつつ、実際のデータベースの適用の様子をかなり見せてくれる講義のようだ。

第2回

身の回りのデータベースについて。柴﨑先生。声が大きい。

裏方として働くデータベース。経済活動自体がデータベースに依存しているという。電子カルテが例になってる。確かに私の開発してる電子カルテもデータベース操作がほとんどっす。座席情報は昔は手作業だったのでダブルブッキングがあったが今はほとんどないらしい。ATMは昔からデータベースだよね。絶対に間違いあっちゃいけないし。

WIndows95によってインターネットが開始され、ここから予約サービスのデータベースの役割が大きくなった。2000年以降ブロードバンド回線が普及し、一気にデータ量が増えてデータセンターなどもいっぱいできた。ポータブルデバイスが発達して、データはネットワークの向こう側に置くようになってきた。これらもデータベースで管理されている。

個人の生活とデータベース。まず検索エンジン。私たちが検索しているのはwebページそのものではなく、検索ロボット(クローラ)が巡回して作成したデータベースによるものである。大きなサイトだと数百万台のサーバーを抱えているそうだ。データベースはオンラインショッピングの土台にもなっている。商品情報、在庫情報、顧客情報、発注情報を全部管理しているので何度もデータベースへのアクセスが発生している。

ヤマトシステム開発のデータセンターに取材してる。クロネコヤマトやね。サーバーは3000台、データベースは270台。メンバーズの管理とか問い合わせ、大和グループの基幹システムで使ってる。一日4600万件(!)。問い合わせも700万回。インタビュイーのおじさん、技術者じゃないなー。広報って感じ。ふわっとした解答がおおい。もはや社会インフラなんで、ガス発電装置とか災害時にもばっちり対応しているらしい(データベースとあんま関係ない)。リアルタイムがどうとか伝票レスがどうとかしか言ってないのでデータベースの技術的なことに触れられてないっす。。なぜこのおじさんに高給を払うのだ。。

あっ先生技術的なこと他の人に聞いてるじゃん!!さすが!!

まずヤマトのDBはメンバーズのサービスは完全に別個扱いで、独立。あとはトレーシングDBとダウンロードDBの2つ。ダウンロードDBが大事で、現場で使うデータが全部入ってる。トレーシングDBは現場の状態を随時上げていくDBで、これは問い合わせのときに使う。不在率は20%もあって大変なので、DBを使ってこれを下げていきたいらしい(どうやって?)。

POSシステムって顧客の見た目のデータも入れてるんですね。これそのうちビデオカメラで自動でできるようになるんちゃうのかな。

第3回

データベースの仕組み。

データと情報との違いから。データはただの客観的な真実(今日は雨)で、情報はデータを役立つように加工したもの(今日の降水確率は80%だから傘を持っていこう)という違いがある。情報は正確・整合性・スピードなどいろいろな価値がある。これらを踏まえるとデータベースとは、「データに情報としての価値を持たせ、データを有効に活用できるようにする目的のために、共有性や再利用性を意図して、一定の規則に基づいてコンピュータ上に格納されたデータの集まり」である。

データは昔は紙集計だった。一部がファイル形式のデータになったのち、データ処理の高度化に対応するためデータベースが利用されるようになったといえる。ファイルシステムだと専用プログラムが必要になるし、汎用性がない。一意性もないし不整合も起きる。メンテが大変。データアクセスも煩雑。これをデータベースにすると管理も楽になるし、ほかのプログラムでデータベースにアクセスして再利用すること(マッピング)や複数ユーザー間の共有も可能になる。データベースは無駄のないデータ集合体である。おお、データベース使うメリット大きすぎじゃん!

データベースの概念について。過不足なくデータを蓄積して、適切な規則を作っておかなくてはならない。たとえば図書館の書誌情報。すべて同じ規則(ISBNコードがあるとか、同じ書籍を重複して登録しないとか)に従って入力されているので、データの増減があっても問題なくなる。データベースを図書館に例えると、データベース自体は書棚、DBMSは司書さん、アプリケーションはカウンターである。データベース管理システムが挟まってるところが便利なところなんだろな。

データベース管理システムはエンジンみたいなもん。データベース自体はただのデータの塊なので、実際に問い合わせる管理システムが重要。実際やることは、データモデルの提供や、整合性の維持、排他制御、障害対応。。いろいろある。

データモデルとモデリングについて。モデリングとは現実をデータに定義しなおすことをいう。概念データモデルの代表はE-Rモデル(実体-関連モデル)という。実体・関連・属性で表す。例えば、実体が商品・取引先、関連に発注、属性が商品コードとか価格とか。論理データモデルは前出のリレーショナルデータモデルとか。

3層スキーマアーキテクチャについて。データベース構造を外部スキーマ、概念スキーマ、内部スキーマに分ける。外部スキーマがビュー、概念スキーマがさっきのE-R図、内部スキーマが容量設計とかメモリ設計とかに対応する。それぞれが独立で他に影響しない。独立性ってのがコンピュータ系ではほんと大事な概念なんだね。

第4回

データベースの歴史。先生の声が小さくなった気がする。速度も落ちた。

データベースの起源は、1950年アメリカから始まる。軍の基地の中で分散していた情報を統合して一か所にまとめたところからデータベース(base)という言葉ができた。1957年スプートニクショックで、データの分散化と、分散されたデータの収集・処理・管理が望まれるようになった。

学術的には1959年のマギー氏、源泉ファイル(Source File)という言葉が初めて。データを階層的に管理し、蓄積する仕組み。重複回避や拡張性、機密保持などの必要性を唱え、現在のDBMSに通じる概念を作った。

商用DBは1960年のGE社のIDSがはじめて。社内生産管理システムを電算化したとき、索引部を介して情報をDB化した。まだまだコンピュータが高価な時代。国家機関しか利用できてない。COBOLにIDSを組み込んだのがCODASYLというグループらしい。聞いたことある気がする。1965年発足。1969年ごろからDBの仕様が一般的にできてきたそうだ。

初期のデータベースで採用されていたのが階層データモデル。データを階層木構造で表現する。常に親と子が1対nとなる。データへのパスは1つなので重複が発生してしまう。複数の親を持てないことが欠点。データ構造に変更があるとプログラム変更が必要なのも欠点。もう一つの流派であるネットワークデータモデルだと、データに達するパスは複数になるから、重複はなくなる。ただプログラム変更は複雑で、毎回変更が必要なことも同じ。

新しいデータモデル。リレーショナルモデルはIBMのコッドさんが作った。1970年代。幹や枝の考え方をやめて、表にする。数学の関係代数、集合理論に基づいているらしい。データベースは集合だったのか!!!なんつっても表とSQLとDBMSがあればオッケー。負荷はかかるが、ハードウェアの進歩とともに負荷は相対的にかからなくなっていった。

リレーショナルモデルはすぐには実用化されなかった。原因は既に以前のモデルに基づいて投資がされていたこと、コンピュータのパワー不足、実装の困難さなどがあった。RDBMSは70-80年代にだんだんと発展してきた。80年代になるとワークステーションが発展して、Oracleなんかも成長してきた。LANも発展してクラサバ型サービスができてきたので、需要が高まった。90年代はAccessやMySQLなども登場した。

オブジェクト指向データベース。バイナリやマルチメディアファイルを扱うのに適している。スキーマ不要で複雑な構造を表現できる。オブジェクト指向型プログラミング言語で扱うデータ(インスタンス?)をそのまんまDBに入れちゃうらしい。リレーショナルデータベースと組み合わせたPostgreSQLが代表。

NoSQL。データを分散して保管するためのニーズで生まれた。Microsoft Azure DocumentDBとか、Amazon RDSとか。キーバリュー型のAmazon DynamoDBというのもあるらしい。

第5回

データベースの動作環境。プラットフォームとしてのコンピュータがどのような変化をしてきたか。大型コンピュータ→ミニコン→Unix→ワークステーション→PC→クラサバという流れ。C言語って移植性が優れていたから発展したのか。おおまかには、データベースの動作環境はWindowsやUnixなど汎用化し、コンピュータも安くなって簡単に環境が構築できるようになった。

クラサバで主に使われているのはweb-データベース連携システムという。webブラウザ使えば特殊な端末も必要なく利用できる。近年はweb化が進んでいるのでwebアプリケーションサーバーをつけて、負荷を少なくする仕組みが確立している。webサーバ、アプリケーションサーバ、データベースサーバと負荷を3階層に分散することで、セキュリティも向上する。3階層システムという。

クラウド型データベース。手元にDBを持たなくていいのでコストがかからない。AWSとかね。

分散型データベース。データベースを分割し、複数のデータベース管理システム同士が通信を行う。ユーザーは通信を意識する必要はない。危険分散と負荷分散ができる。

webとXMLデータベース。XMLデータベースはXMLスキーマ自体をデータベースの定義として使うというもの。XMLは階層性を持ち、拡張性が容易な特徴がある。そしてデータ自体も書ける。これをそのまんま蓄積すればXMLデータベースになる。巨大なXMLデータをいかに効率よく管理するか、というのがXMLデータベースの必要性を生んだ。XMLだから別にテーブルじゃなくてもいい。XMLデータベースは基本的には単に蓄積するだけ。タグ情報をインデックス化することで高速アクセスを可能にする。データ定義の変更が頻繁にあるようなデータに向いている。汎用性も高いしマルチメディア情報も格納できる。

xpassとSQLの相互変換は可能なので、その意味ではRDBMSと共存ができる。XMLはDOMに読ませてしまえばオブジェクト指向DBとも連携できる。

オープンソースソフトウェアを組み合わせて構築できる環境としてLAMPがある。Linux Apache MySQL Python/PHP/Perl の略らしい。安価で高性能な環境が構築できる。

データベース言語について。ネットワークデータベースの規格がNDL(1987年)、リレーショナルデータベース言語のSQLも同年。SQLは2016年の定義まであるらしい。標準化は様々なメリットがある(略)。

第6回

概念設計の話。データモデルを作成すること。既出のように概念、論理、物理データモデルの3つ。まずは実世界からE-Rモデルを使って概念データモデルを作成する。概念データモデルを基に論理データモデルを設計する。また既出のように階層、ネットワーク、リレーショナル、オブジェクト指向モデルがある。最後は物理モデルだが、これはDBMSが勝手にやってくれる。

概念設計について。実体関連モデルは計算機科学者のピーター・チェンって人が作ったらしい。E-R図も別名はピーター・チェン記法という。

実体とは。実世界の個々の対象物のこと。一人一人の学生、教員、科目など。「学生」のようなカテゴリは実体型という。クラスのことかな?実体型は属性 attributeを持てる。例えば学生には氏名、住所、学籍番号などを持っている。学籍番号のような一意なキーを主キーという。

関連とは。2つ以上の実体同士の相互関係のこと。関連も関連型としてとらえることが多い。例えば学生→(履修)←科目のような関係。関連型に主キーなんてあるんかいな。人→結婚←人みたいな、同一の実体型の結びつきを表す関係もある。こういう場合関係性(ロール)が与えられる。結婚なら、夫や妻があるね。

1対1の対応関係は、考えやすい。教員→所属←研究室みたいな場合を考えることができる。このとき多重度は1対1という。主キーは教員でも研究室でもいい。

1対多の対応関係の場合は、多の方が主キーになる。例えば部活動と学生。学生の方が多いので、主キーは学生。多対多、例えば学生と科目の関係の場合は、主キーは両側の実体型の主キーの和集合(全組み合わせ)となる。主キーってのは一意性を満たす関係のことね。

実際の図を見て考える。図にするとどうやってモデルを作ればいいかわかりやすいね。昔、電車がリアルタイムで走るモデルを作ったことがあるけど、こんな風にモデルを作っておけばもっと楽だったな。

制約について。部活動と学生は1対多だけど、部活に所属していない学生や、だれも所属していない部活動があってもいいのかは明らかではなかった。これを認めるか認めないかを、参加制約という。関連図に最小値や最大値を書くことで参加制約が明確になる。

ある実体に依存して初めて存在できる実体型のことを弱実体型という。例えば科目に対するレポート。単体で存在できるのは強実体型という。弱実体型は、対応する強実体型の主キーに対して、部分キーを持つことができる。強キーと必ずペアで用いられる。

3項関連型。例えば履修を複数年度にしたい場合。学生、科目だけではなく年度(時期)も関連として採用してやればいい。

Is-A関連。社員に対する営業部員・製造部員のような関係。社員がスーパータイプ、営業部員・製造部員はサブタイプという。継承ともいってるし、クラスに近い考え方だ。

UML。統一モデリング言語の略。今使われてるのかな。ここまでの概念は全部表現できるみたいだよ。属性を実体型に含めて書けるので見やすい。

第7回

リレーショナルDBモデル。論理データモデルの1つ。リレーションは数学的に定義できる。情報の単位自体をリレーションと呼んでる。スキーマとインスタンスがある。構造、操作、制約が3つの要素である(?)

リレーションインスタンスというのは、表1個のこと。リレーション名とは、いわゆるテーブル名のこと。行はタプルという(いろんなデータの集合だからかな)。

主キーはスーパーキー(一意なキー)かつ候補キー(スーパーキーかつ極小単位)であるキーの中で、設計者が選んだもののこと。NULLを取らないという制約がある。

リレーションの定義は、全リレーションの直積集合のこと。いくらでもあるね。

リレーションは同一要素を持ってはならない。タイムスタンプとか通し番号とか持ってないとダメね。順番にも意味はない。

正規形。入れ子型を禁止すること。入れ子のものは別のテーブルに分けてやれば正規化できる。

リレーショナル代数。和集合とかの集合演算のこと。同じ属性とドメイン(テーブルのことかな?)をもっていないとだめ。商演算は難しいな。直積演算の逆。選択(select?)や射影もある。射影は要素の重複ができてしまうので、重複は排する。

整合性制約。ドメイン制約(変数の範囲の制約)、一意性制約(同じ値の排除)、非NULL制約(空データはダメ)、主キー制約(=一意性制約+非NULL制約)、参照整合性制約(外部キーは必ず外部リレーション内にある)がある。

概念データモデル→論理データモデルの変換について。実体-関連図を使えばそのまんま変換できる。っていうかこの図自体がほぼ論理データモデルなんだな。ID関連型(弱実体型への関連)の関連はリレーションに入れる必要がない(どうせ1対1になるしってことかな)。弱実体型に所有実体型の主キーを持たせとけばいい。関連は、やろうと思えばリレーションに併合してしまうこともできるみたい。その場合、1対1関連ならどちらでも、n対1型ならn側に併合できる。n対mの場合は無理。

第8回

データ操作について。ユーザーの要求は主に、問い合わせと更新である。今回は問い合わせについての学習。

リレーショナル代数→集合論に基づく問い合わせの体系。リレーショナル論理→論理式を用いてデータを表現。代数と論理は等価らしい(ほんとか?)

リレーショナル代数はコッドさんが作った。演算は8種類。和集合とか差集合とか。8種類のうち3つはほかの5つで表現可能だから実質5つ。和、差、直積、選択、射影。

和集合演算。同一ドメインの表を合算して重複するものは排除したもの。論理式だと、または(∨)で表現可能。

差集合演算。論理式だとA∧¬Bで表現可能。

共通集合演算。かつ∧と同義。和、差、共通集合演算は同一ドメインで同一属性じゃないとダメ。和両立という。共通集合は R – (R – S) でも表現できる(図を書いてみよ)。

直積演算。全タプルの組み合わせで結合する演算のこと。膨大な数になるね。別ドメインに同一の属性があっても、リレーション-属性を一組にして区別し、問答無用で組み合わせを考える。

選択演算。これが一番重要。選択条件を使って絞り込む。選択はσで表す。

射影演算。指定した属性だけ残す。減らした結果重複が生じたら、重複は削除。

商演算。R/Sなら、Sの属性値が全部含まれているRの属性値だけを残すことに相当する。例えば「S:アメとガムとカップ麺」で「R:コンビニ」を割れば、アメとガムとカップ麺を持っているコンビニが残ることになる。商はめっちゃ頑張れば射影、直積、差を組み合わせまくって表現できる(詳細は略)。

自然結合演算。2つのリレーションに共通の属性があるとき、同じ属性を持つタプルを結合すること。直積+選択+射影で表現可能。共通の属性がないタプルをダングリングタプルという。

θ結合演算(または単に結合演算)。共通の属性がなくても、結合条件を与えて結合させることで一般の場合に拡張したもの。これも直積+選択で表現可能。

外部結合。ダングリングタプルをNULLを用いて強引に結合してしまうこと。結合に使った全タプルが含まれることになるが、NULLがあるから扱いにくそう。

第9回

正規化。リレーションスキーマがよいものかどうかを判断する手掛かりになる。論理設計の一部。

関数従属性。Xの値が等しいすべてのタプルにおいて必ずYの値も等しいということ。X→Yの関係が成り立つことと同じ。学籍番号→氏名とか。リレーションRの出現しえるインスタンスの満たす性質のこと(リレーションを作るための必要条件ってことかな)。

関数従属性は実世界上の規約で決まる。例えば「受注番号が受注ごとに新しく発行される」という規約があれば、「受注番号→受注年月日、顧客番号」のような関数従属性が成り立つ。

関数従属性の表記方法。A1, A2, … Am → Y と表記する。カンマを省略することもある。A1A2…→Y 。X∨YはXYと書くこともある。

Kがスーパーキーであるとは、関数従属性K→A1A2…Anが成立することと定義することができる。Kが候補キーであるとは、Kの部分集合K’がスーパーキーにならないことともいえる。

A1A2…Am→B1B2…Bnという関数従属性が成り立っていたら、A1A2…→B1,A1A2…→B2のように分割できる。例えば、受注番号と項番が候補キーになっていれば、ここから受注年月日、顧客番号、単価などを一意に決定できるでしょ?ということ。受注番号単体では一位にならない。直感的にはそりゃそっかーって感じだけど式にして一般化も可能なんだね。

アームストロングの公理系。まず反射律。YがXの部分集合なら、X→Yが成り立つ。添加律。X→YならX∨Z→Y∨Zが成立。推移律。X→YかつY→ZならばX→Zが成立する。この3つが基本になる。

関数従属性の閉包。リレーションRにおける関数従属性集合Fが与えられたとき、①Fの要素と②Fの要素の任意の組の関数従属性が考えられ、①②をあわせてFの閉包という。F+と書く。なんのこっちゃって感じです。具体例が欲しい。

アームストロングの公理系は健全で完全であるという。健全→Fの各要素にアームストロングの規則を用いると、どれもF+の要素になる。完全→F+の関数従属性は、全部Fの各要素にアームストロングの公理系の各規則を適用すれば、導出できる。というわけで、関数従属性集合の閉包はアームストロングの公理系を使えば求められるってわけ(foon)。

閉包を求めるアルゴリズム。全然意味わからんが、「スーパーキーというのは数学的な手続きを踏めば必ず求められる」ということまでは理解できたので、そこまでにしておこう。

更新時異状。第一正規形では全部スカラー値になっているが、異状が起きることが3パターンある。

修正時異状。ある事実を表す情報が複数のタプルに存在する場合。例えばある商品番号の単価を更新したら、全部更新しないといけない。更新漏れがあるのが修正時異状。

挿入時異状。ある事実を表す値をデータベースに追加したいが、情報が足りなくて追加できない場合。

削除時異状。ある値を削除する時、意図しない形で別の事実を表す情報が失われること。受注情報を1行削除したら商品情報がなくなるとか。

これらをなくすために正規化が必要。まず第2正規形。Rの全ての非キー属性が、Rの候補キーに完全関数従属していること。完全関数従属性とは、Xの任意の真部分集合X’についてX´→Yが成立しないことをいう。成立してしまうことを部分関数従属という。部分関数従属をなくしていけばよい。

第三正規形。第二正規形かつ、Rの全ての非キー属性が、Rのいかなる候補キーにも推移的に関数従属しないこと。推移的関数従属性とは、関数従属性X→YかつY→ZのときX→Zが成り立つこと。推移的関数従属をなくしていくことになる。実質、全ての候補キーについて第二正規形と同じようなことを行えばよいということになる。

ボイス・コッド正規形。X→Yが自明な関数従属性であるかXがRのスーパーキーである、という条件を満たすこと。具体例を見せてくれたがよくわからんかった。

第10回

データベース言語。SQLについてくわしく。SQLはIBMが作ったSEQUELが原型。その後ベンダーごとに拡張が進み、ANSIやISOが標準化した。

リレーションとは属性の構成、ドメインの直積の部分集合のこと。リレーショナル代数とは、データ操作演算体系のこと。リレーションとSQLはデータの扱い方が少し違う。リレーションでは重複タプルは許されないが、SQLでは許される。また、リレーションでは順序が意味を持たないが、SQLでは順序があり、行や列の順序も支持できる。

SQLはDDL(データ定義)、DML(データ操作)、DCL(データ制御)で構成される。

DDLは具体的にはCREATE、ALTER、DROPの3つ。

表の種類。実表(実体)、ビュー(論理的な表??)、導入表(一時的な表)。

CREATE文。CREATE TABLE 表名+(列・データ・列制約)*n+表制約。表制約では、PRIMARY KEYで主キーを設定したり、CHECKで値の範囲を制限したりできる。

ALTERは属性の変更・追加。DROPは表の削除。

DML。選択はSELECT *(よく使うので略)。射影はSELECT文で列名指定。重複除去はSELECT DISTINCT。和集合はUNION ALL、差集合はEXCEPT ALL、共通集合はINTERSECT ALLを使う。ALLを省略すると重複除去も兼ねる。副問い合わせは()の中にSELECT文を入れる。

第11回

DBMS1回目。データベースには大量のデータが蓄積されていることが前提。高速処理、データの整合性の保障、同時処理が必要になる。他にも障害復旧、セキュリティ、操作手段(言語の提供)も必要。

構成。問い合わせ処理部、トランザクション管理部、記憶管理部からなる。

前回のデータ定義、操作、制御はそれぞれメタデータ管理、問い合わせ処理、トランザクション処理として実装される。

メタデータ管理。メタデータとはデータのデータのことで、テーブルに関するデータや、列、索引、型構造のデータのこと。データ辞書に格納される。

データベースの格納方式。揮発性では困るので磁気ディスクに格納する。レコード、ファイルといった単位を使う。テーブルとファイルは1対1対応する。レコードは行、フィールドは列。論理的配置と物理的配置は違うことに注意。

代表的な格納方法に、ヒープ、索引編成、B+木、ハッシュがある。

ヒープ。効率的だが、順序はキー値の順にはならない。順次探索しかできないのでノロい。

索引検索。インデックスのことかな。主索引(主キーかな)と二次索引(主キー以外のフィールド)がある。二次索引を用いると検索が効率化できるが、レコードの格納位置が変わると、索引中の格納位置も変えないといけない。なので、ディレクトリ参照(どこにレコードがあるかの情報)をするようにする、ここでいうディレクトリはwindowsのファイルシステムとは違うようだ。レコード挿入は索引修正が必要になる。レコードをずらさなくていい工夫が必要。—バーフロー領域を使ったりしてなんとかする(よくわからん)。

索引を階層化して検索時間を減らすことを考える、これがB+木。木の高さをなるべく等しくするような木のこと。葉以外の節が索引(どうやってるの?)。B+木自体が探索木になる。キーの値を二分探索していくといずれ辿り着く。レコードの挿入は木構造の再編成をすることで実現する。

ハッシュ。ハッシュ関数を用いてキー値からレコードの格納位置を算出すること。高速。でも範囲指定とか全レコード読み出しが無理。

問い合わせ処理。コストをできるだけ小さくすることを最適化という。処理の流れは構文の判定→最適化と実行プランの生成→実行プログラムの生成→実行。

多様な実行プランの存在要因。代数演算処理には組み合わせに任意性がある(等価なものがいっぱいある)こと、代数演算処理がデータへのアクセス処理の仕方に影響を受けることなど。例えば選択と射影をする方法には、選択→射影でも、射影→選択の順でもいい。

テーブルの結合方法。まず入れ子ループ法。結合先から1行読んで、結合元の各行を読んで言って結合。これだと結合先(外部)に行数が少ない方を持ってくる方が速い。

マージ結合法。各テーブルを結合フィールドでソート後、フィールド値の小さい順に結合する。ソートにコストがかかるが、その後は速い。

ハッシュ結合法。ハッシュ表に両方とも行を読み込んで、同じハッシュ値になるものを結合。ハッシュ表が主記憶上に保持できれば高速処理が可能。

第12回

DBMSの第2回。トランザクション管理について。トランザクションは処理の単位のこと。例えば5000円の振り込み処理を考えると、出金と入金が両方同時に行われないといけない。片方では困る。

ACID特性。原子性、一貫性、隔離性、持続性。これが順守されていないといけない。原子性→全部完了 or 全く実行されないこと。一貫性→DBに矛盾が生じないこと。隔離性→各トランザクションは独立して実行できる。持続性→トランザクションが終了すれば、障害発生しても結果が消えないこと。

トランザクションが終わったら、コミット(終了)かアボート(障害発生、中止)のどっちかになる。

同時実行制御。口座の話だと、送金処理中に他人の入金があった場合どうなるか。制御がないと他人の入金が上書きされてなかったことになってしまうかもしれない。複数のトランザクションが同時実行されるとき、矛盾が起きないようにしないといけない。代表的なのはロック方式。排他制御する。1つのトランザクションだけがロックをかけられる。後のトランザクションはアンロックされるまで待つ。まあこれもプログラミングの実務でよくやるよね。

直列化可能性。複数のトランザクションを並列処理した結果、逐次処理と等価になること。これがうまくいけば並列処理可能になる。2相ロッキングプロトコルでこれを保障できる。複数のトランザクションで読み書きの対象データをロックし、処理終了までアンロックしないこと。ロックを解除したら再度ロックできないようにする。これでいいらしい(数学的に証明できるのかな?)。ただ、複数の資源を同時にロックせざるを得ないので、効率がちょっと悪い。

共有ロックと占有ロック。共有ロックは読み込み用。参照を許可する。占有ロックは書き込みを行うのでアクセスも禁止する。これを使い分けて高速化を図る。

デッドロック。複数のトランザクションが互いに他のアンロックを待っている状態になること。T1がxをロック、T2がyをロック、T1がyを待ち、T2がxを待つとデッドロックが発生する。こういうときはDBMSが強制的アボートをして解消する。

隔離性レベル。未コミット読取り→コミット済み読取り→再読み込み可能読取り→直列化可能、の順でレベルが高い。

障害と回復。トランザクション障害。トランザクションの途中で異常が発生した場合のこと。システム障害。全トランザクションが停止すること。メディア障害。ディスククラッシュのこと。一番障害が大きい。

ロールバックとロールフォワード。ロールバックが実行開始前、ロールフォワードは実行完了にすること。アボートしたらロールバック、コミットしたら障害発生してもロールフォワードする。

メディア障害をに備えるためには、フルバックアップしたり差分バックアップしたりする。差分バックアップはトランザクションだけ記録して実装してる。

ログ。データベースの更新を記録したもので、更新前と更新後の状態とか、トランザクションそのものを記録する。ロールバックもロールフォワードもログを見て実行する。

ログを取るタイミングの問題。WALプロトコル。ログ先行書き出し(Write Ahead Log)のこと。データベース更新前に全部ログを記録してしまうこと。そうしないとロールフォワードが不可能になる。更新後ログも先に書いてしまう。

チェックポイント。一定間隔でバッファのデータをディスクに書き込むこと。ログはでかいので復旧には時間がかかる。チェックポイントがあれば、これ以降のログを用いて回復処理が行えるから、処理時間短縮になる。

第13回

データベースの発展技術1。データストアについて。

データベースの機能から。本質的な機能として、データの論理形式・格納と操作。選択的な機能は永続性・整合性・高速応答性・堅牢性。

データ操作の4要件、CRUD。Create, Read, Update, Delete。

キャッシュデータベース。応答性の優れたキャッシュデータベースを真ん中に挟んで高速化を図ること。これうちの実務でもやってるぞ!不整合が起きないようにする工夫が必要になる。

データストアとは何か。データベースの機能、性能を特徴づけるデータ集合の入れ物。データ取扱い単位の概念を含む。実装の詳細は含まない。論理的モデルと物理的モデルの中間あたりに位置する。

データストアの5分類。キーバリュー型、列指向型、リレーショナルデータベース、ドキュメント指向、グラフデータベース。

キーバリュー型。キーとバリューの組(タプル)のこと。大規模性、高速性が特徴で、演算機能はない。

列指向型。タプルを識別するキーと、属性:値の多数の組。タプルごとに異なる属性を持てる。キーバリュー型のもう一段階複雑なやつって感じ。リレーショナルデータベースと比べると、列単位の読み書きや列の追加が簡単なことが特徴。逆に、リレーショナルデータベースは行指向といえる。

ドキュメント型。XMLデータベースとか。柔軟なデータ形式が特徴で、入れ子構造も行ける。集計は無理。

グラフデータベース。次回に回す。

社会での様々なデータベース。IoTのことを聞くため、ソラコムのCTO安川さんにインタビュー。今私たちは時計とかカメラとかいろんなものからDBにデータを上げてる。で、こういうデータは消えない、消さない。データベースは大規模化してる。web、IoT時代だと24/365で稼働、高速応答が求められる。リレーショナルデータベースは何でも使えるのが利点。ただ、いつも使いやすいわけではない。アプリケーションによっては特定の機能に絞った方がよいこともある。そこでデータストアの選択が大事になる。

キーバリューストアを使う場合。ショッピングストアとか、可用性、高速性、分散処理が大事な分野で有利。性能の向上も簡単。線形でできる。一方でSQLだと大掛かりになってしまう、重い。スケーラビリティが厳しい。柔軟なクエリ、トランザクションが必要ならRDBを使えばいい。

オンライントランザクション型では、ランダムアクセス性能に強いSSDの方が有利らしい(!)。ハードディスクはランダムアクセスは苦手。なのでサーバーでもSSDが好まれるようになってきている。連続したデータならハードディスクでも強いので、今でも使われることがある。

Update、Deleteが実際ないようなデータベースもある。再配置とか面倒なんでやめて、リンクだけなくしてしまう。そうするとかなりコストを省くことができる。メッセージを削除してもデータベース中には残っているという話。デリートマークだけつけてるってことかな。

列指向データベースの使いどころ。RDBはオンライントランザクション型に強い。トランザクションが行と同じだから。一方でデータの分析には列指向が強い。ユーザープロファイルからデータを取りだして解析したいって時、RDBだと全部の表を読まないといけないけど、列指向だと速い。

第14回

グラフデータベースについて。グラフの基本についてはほかの講座でやったので略。

プロパティグラフ。ノードには名前がついているほかに、プロパティも持っている。エッジにも名前やプロパティがついている。

グラフデータベースの構成。リレーショナルモデルなら、関係性をデータベースに保存することができる。JOINすればいろんな関係性がわかるが面倒。一方でグラフモデルなら、エッジをたどることで簡単に関係性が分かる。ネイティブ処理エンジンというのを使って、高速にエッジをたどる機能がある。

Cypherという言語を使う。SQLに似ている。

CREATE (alice{name: ‘Alice’}), (bob{name:{‘Bob’})

みたいにノードを生成できる。エッジを生成するときは

CREATE (alice{name: ‘Alice’}) – [:FRIEND] -> (bob{name:{‘Bob’}), (alice) <- [:FRIEND] – (bob)

みたいにやればよい。直感的だ。

RDBとの違い。例えば人テーブルに年齢という列を加える。RDBだと非常にコストがかかる。グラフデータベースなら、プロパティの追加で済む。列指向型と同じで簡単。また、1対多の関係も簡単。エッジを追加するだけ。

エッジの検索。

MATCH(p) WHERE p.name = ‘Alice’ RETURN p

で、Aliceというノードを検索できる。

MATCH文とCREATE文を組み合わせることもできる。MATCHした結果を使って、そこにCREATEでノードを追加できる。

MATCH (p{name:’Alice’}) – [:FRIEND*2] -> (friend_of_friend) RETURN DISTINCT friend_of_friend.name
にすれば、Aliceの友達の友達の結果を検索できる。グラフの特性を大いに使った問い合わせだ。これをRDBでやると、JOINを何度も使うことになり、非常にコストがかかってしまう。隣接性を使う場合はグラフの方がとても有利。友達の友達の友達の・・・ってやるときは数字を増やすだけでいいしね。

第15回

分散データベース。

検索高速応答性を考える。インデックスはある程度範囲を絞ったうえで線形探索するから、場合によっては遅い。B+木の計算量はO(logN)で速いし範囲検索も可能。ハッシュはO(1)でめちゃはやいが範囲検索は無理。

ストアドプロシージャ。データベース側に処理内容を保存しておいて、例えばSELECTとログのINSERTを同時に行うようにする。バッチ処理をDB側においておくようなもんかな。アプリケーション側との通信の削減と、処理の漏れが無くなる。

Map Reduce。入力した文章群をMap Stepでクラスターごとの文章にノード単位で分割、さらにReduce StepでShuffleしてwordに分割。出力でwordごとの回数の合計を得る。大量のデータを処理できるのが特徴で、分散処理もできる。ストアドプロシージャの分散DB版。

スケールアップとスケールアウト。スケールアップは高性能なハードウェアを使えばいい。が、金がかかる。スケールアウトでは、処理を分散させて全体としての性能を向上させること。金がかからない。協調動作が難しいのが欠点。

スケールアウトの手法。まずレプリケーション。データベースの複製を用意して、同期する。負荷は減るが、データの変更が大変。

シャーディング。データの一部分をドメインみたいな感じで分けて管理。北海道、青森県、岩手県で分けるとか。同期がいらない。ただ、ボトルネックが一番処理の集中するDBになる。東京ってDBを作ったらそいつが辛い処理になってしまうね。

分散データベース。まずCAP定理。C整合性、A可用性、P分断耐性。整合性はどのノードからも同一の値が読み出せること。可用性は、アクセスできればリクエストに応答できること。分断耐性は、システムが分断されても機能を継続できること。故障があってもこれを満たしてほしいが、全部は無理。2つはいけるが1つは諦めなければいけない。これがCAP定理。

CAだけ生きていて分断されてるときは、互いに通信をシャットアウトすればよい。CPだけ生きているときは、一つの断片だけ機能させる。すると整合性はなんとかなる。APだけのシステムにするなら、全断片を機能させるが、不整合は生じる。いずれかの組み合わせを選択しないといけない。だいたいはCPかAPを選択する。

BASE。Basically Avaliable Soft-state Eventual consistency。基本的に可用、データ状態は厳密でない、結果的に整合性をもつ。例えば分散DBで、住所データベースを実現するとして、新住所を更新したとする。これを他のDBに通知して、いずれは全ノードで新住所に更新されればいいやという考え方。一定時間内は不整合が発生する。障害があれば不整合の時間は長い。

決済への応用。決済は素早く行わなければいけないので、中央データベースに毎回アクセスしていられない。そこで少額の決済処理を店舗側データベースでも行えるようにする。で、処理は順次中央データベースに送られていくようなモデルにすれば、正確性と迅速性を確保する。一定金額以上は中央にアクセスしないといけないようにすればよい。

気象情報などのセンサネットワークはそもそも分散してデータが発生するし、逐次的に発生する。これも分散処理に向いている。

放送大学全科目感想 016 コンピュータの動作と管理(’17)

  • 情報コース
  • テレビ科目
  • 葉田善章先生
  • 難易度 ★★☆☆☆
  • おすすめ度 ★★☆☆☆

前半ではハードウェア周りからコンピュータの動作とは何なのかを攻めていく。後半はOSを中心とした話題。先生はハード専門なのか、ハードウェアの方が突っ込んだ話が多い。全体的に情報量は多め。ひたすら先生が一人でしゃべっていて、インタビューなどはなし。印刷教材で十分かもしれない。

第1回

葉田先生一人での講義。OSの話らしい。

いろんなコンピュータがあるよねって話から。基本的な機能を提供するのがOS。

10回でハードウェアの話。5回でOSの話。結構知ってる話も多いので知らない話だけ書いていこう。

OSはプログラムとハードウェアの管理を両方行う。プログラムについてはタスク管理をしてマルチタスクを実現する。OSがハードウェアを管理するので、プログラム側からはハードウェアの違いを意識しなくてよい。

ハードウェアの話。同一コアのCPUのことをホモジーニアスというらしい。異なるコアだとヘテロジーニアス。CPUは命令セット空間(命令の集合)を持ち、ヘテロジーニアス型だと命令セット空間が異なる。なので別々のプログラムが必要になる。

レジスタには汎用レジスタと制御レジスタがある。制御レジスタにはプログラムカウンタ、PSW(フラグを集めたもの)などから構成される。汎用レジスタはデータレジスタといい、算術論理演算回路(ALU)で使われる。

OSの重要な機能として抽象化がある。プログラムがCPUのことを意識しないようにする。1つのCPUをOSが仮想CPUに分割したりできる。実際は1つのCPUが並列処理をシミュレートしたような動作をする。入出力装置についても仮想メモリとメモリを同一に扱ったり、SSDやHDD、USBメモリを同一に扱うことができる。

第2回

演算装置について。

プロセッサは電子回路でできている。電子回路の例としてLEDが光る回路が出てきた。スイッチに電流が流れればLEDが消灯。スイッチに流れなければLEDが光る。これがNOT回路。実際は電圧の高低で表現する。コンピュータの01は電圧の高低で表している。高電圧を1、低電圧を0とするのが正論理で、逆は負論理。先生が見せてくれたNOT回路はICで実装されている。

クロック信号について。クロック信号はパルスで出力される。電圧の高低を速い周期で繰り返す。電子回路はこいつに同期して処理を行う。命令1つあたりのクロック数をCPIという。CPUの速さを測定するとき、クロック周波数ではあてにならないので、平均CPI(全命令のCPIの平均)で比較することが多い。プログラム実行時間は命令数 * 平均CPI / クロック周波数 となる。

クロック信号にはノイズが入る。このような場合でも動作するようにしきい値を設定する。しきい値と比べた高低を調べれば少々ノイズが入っていてもよくなる。

シングルコアとマルチコア。シングルコアだと書かれた順で処理が実行されるが、マルチコアだと、命令を並列処理できる。OSの管理機能と組み合わせて処理速度を上げていく。

プロセッサーの処理方式。データ処理と命令方式をそれぞれシングル、マルチにするかによってSISD, SIMD, MISD, MIMDがある(頭が追っつかない)。

命令セット空間について。だいたい基本的な機能はどの命令セットにもある。独自の命令を拡張命令セットという。

プロセッサのコアについて。ALUの例として、D型フリップフロップというICを考える。割と簡単な回路図で表現されている。電圧の高低を記憶できるので、01のどちらか、1ビットを表現できる。4bitを記録するなら、D型フリップフロップが4つ必要になる。読み出しでは4つの値を結合して解釈すればいい。このとき、4つのフリップフロップにクロック信号を同時に与えれば、4つの値を同時に解釈することができる。

レジスタが値を保持するにはどうするか。出力を入力に直接つなぐと、クロック信号が変わっても同じ値が保持される(なんのこっちゃ)。

演算を行うためには、出力→入力の間に回路を置く。例えばNOT回路を置けば、レジスタの値が更新される。保持回路(ただの線)とNOT回路をスイッチで切りかえれば、処理の切り替えと同義になる。スイッチも回路で実現できる(要復習)。

プログラムカウンタについて。プログラムの例が出てきた。プログラムカウンタには次の命令のアドレスが入っている。プログラムカウンタを変更するタイミングは、クロックの立ち上がりのタイミングと同じ。(駆け足でよくわからんかった)

第3回

CPUの処理について。

64bitと32bitでは命令セットが違うが、64bitCPUは32bitプロセスも実行できる。互換性があるという。

ASCIIコードは8bitである。データに何を対応付けるかはプログラムによって違う。データの基本単位のことをワードという。64bitOSならワード長64bitってわけ。データ長がワードを長える場合はどうするか。データをワード長で分割すればいい。64bitOSで32bitのデータを扱うと、32bit余るのでプロセッサの性能が完璧に使えるわけではない。

命令とオペランドについて。命令は命令部とオペランド(命令用のデータのこと。任意)。オペランド部のデータのことをイミディエイトデータともいう。

機械語を数値で表すと16進数2桁(命令部+オペランド)であるが、これを人間でもわかるように記述したのがニーモニック。ADD A, 6 のように書く。アセンブリ言語の単位である。もっと人間にわかりやすくしたのがプログラム言語。結局最終的には機械語にするんだけど。

命令実行について。命令フェッチ(読み込み)→デコード(命令解釈)→オペランドフェッチ→演算→書き込みという流れ。この一連の流れを命令サイクルという。一部の処理が省略されることもある。最初の二つをフェッチサイクル、残りの3つを実行サイクルともいう。フェッチサイクルはメモリからデータを持ってきて、命令デコーダーで解釈することに相当する。実行サイクルは、読みだしたデータをALUに投入してレジスターなどに書き込むことに相当する。

何やら概念的で具体的なイメージが全然わかないな。

命令が連続している場合、フェッチ、実行サイクルは別々の回路なので、並列して処理できる。先取制御、先回り制御という。細かく区切ればパイプライン処理になる。

命令にもいろいろ種類がある。転送命令、演算命令、算術演算。。。

最後にアーキテクチャの話。CISCは可変長命令、簡単な命令は短いなど最適化されている。RISCは命令が固定長。単純な命令が多く、パイプライン処理に向く。プログラムは大きくなる。

第4回

周辺機器との通信について。

直接制御と間接制御。入出力ポートなどでつないでCPUが直接アクセスできるのが直接制御。プロセッサをかますと間接制御となる。間接制御では制御はプロセッサが行う。たぶんプログラム的にはインターフェース用の関数があるんだろう。

個別ポート方式とバス結線方式。ポート+インターフェース+周辺機器をセットで組み合わせるのが個別ポート方式。ポートのアドレスが分かればプログラム的にはやり取りが可能になる。バスという専用線を使うのがバス結線方式。バス→インターフェース+周辺機器の組み合わせだが、バスは全周辺機器で共通のため、交通整理が必要になる。

入出力ポートによる接続について。まずメモリーマップドI/Oについて。メモリ空間にI/Oポートを割り当てる。メモリ操作によって周辺機器を操作できる。ポートマップドI/Oはメモリ空間ではない専用のI/O空間にポートを割り当てる(windowsはこっちか?)。マイコンではレジスタにI/Oを割当てたりもする。いずれの接続方法でも、I/Oポートを介して周辺機器のレジスタにアクセスしてデータをやり取りする。どのポートでも電圧の高低と0 1を対応付けて入出力する。演算回路の途中にポートを入れることで、信号を入出力することができる。

バスを介した入出力について。バスは乗り合いバスのバスからきているらしい(まじで!?)プロセッサとタイミングを取り合って、みんなで共通のバスを使っていく。データバスの信号線の数をデータバス幅といい、32bitなら32本信号線がある。このほかにアドレスバス、制御バスがある。

バスを使ったデータ読み出し。よくわかりませんでした。制御バスが、他のバスの動作を抑制しているってことかな?バス使用中はほかの装置はバスを使えませんよってするんだと思う。

第5回

効率的なプログラム実行について。プロセッサの方が周辺機器より速いので、待機状態を避けるためにいろんな工夫が必要になる。

プログラムは待機状態をとるためにループ構造を持つことが多い(ループがないと一瞬で終了するから)。機能ごとにサブルーチンに分けて、都合に応じて呼び出す、という構造をとっている。これに合わせて周辺機器の制御を行えばよい。

まず繁忙待機。メインプログラム内では、ループ内で外部回路操作命令を定期的に行うことをいう。ポーリングともいう。周辺機器のステータスが何か変化したら何か処理を行うって感じの処理になる。周辺機器の状態変化が速すぎると取りこぼしが出る。

割り込み。プログラムに割り込み処理を設定しておいて、周辺機器側から割り込み処理を呼び出すやりかた。プログラムにはやっぱりループが必要。割り込み処理は取りこぼしはないが、プログラム構造がとても複雑になる。中断再開の仕組みが必要になるから。

割り込み処理の詳細。仕組みは仕事中に電話がかかってくることと同じ。割り込みには外部割込み(異常を表す機械チェック、入出力割込み、タイマーとか)、内部割込み(0除算した場合など、プログラムによる割込みや、SVCスーパーバイザーコール・システムコールのこと、がある)がある。

データバッファを使うかどうか。バッファなしだと割り込みに全対応しないといけないので大変。バッファありだと、細切れでデータ転送ができて、一定量溜まったときに初めて通信できるから、割り込みの回数が減る。なので便利。効率的。

割り込みサイクルはどこに挿入されるか。フェッチサイクル→実行サイクルの次に挿入するしかない。フェッチサイクル→実行サイクルの間に割り込みフラグを立てておいて、フラグが立っていたら割り込み処理をする、という方式になる。詳細としてはPSW退避サイクル→PSWロードサイクルの実行、の2ステップになる。これが終わったら、退避サイクルで退避していたデータから最初の状態に復旧して、またフェッチサイクルに戻ればいい。

割り込み検出方法。まずベクター割り込み方式。割り込み番号を周辺機器に割り当てておく。番号込みで割り込み処理が伝えられるので、番号ごとに対応ができる。割り込みハンドラー(割り込み番号+αの情報のことと思う)を保存しておく割り込みベクターが必要になる。ポーリング割り込み方式では、割り込みハンドラーを1つだけ持つ。これだと誰が割り込み処理を投げたかわからないので、全周辺機器の状態を調べて発生元が誰なのかを特定する。割り込み番号がかぶっていても対応可能という利点がある。

割り込みにも優先順がある。割り込みハンドラーに優先順をつけておいて、エラーなどレベルの高い割り込みから処理していく。レベルの低い割り込みと高い割り込みが競合したら、やはり高いものから処理する。多重割り込み処理という。

第6回

補助記憶装置について。

ハードウェアを使うプログラムには、ハードウェア制御のプログラムと目的の処理を行うプログラムの二種類がある。ハードウェア制御はOSに任せておけば、目的の処理だけを行うプログラム(アプリケーション)は自分の処理に集中できる。

物理的資源と論理的資源。物理的資源はハードウェアのことで、論理的資源は実際には存在しない思考上の存在のこと。OSは物理的資源(CPU)から論理的資源を作って割り当てる役割をする。論理プロセッサ、仮想プロセッサともいう。

抽象化。携帯音楽プレイヤーの再生操作とか、対象の共通の操作方法を取り出すこと。周辺機器も種類ごとに抽象化を行えば操作が簡単になる。コンテンツプレイヤーの回路構成や部品の違いは、インターフェースの統一によって解決できる。ハードウェア抽象化も同じように、プリンターならプリンターの機能、記憶装置なら記憶装置の操作方法を決めておいて、どれでも同じ操作ができるようにする。カプセル化ができる。

データの抽象化について。ファイルは抽象化の1つ。ただのデータの集まりを、とらえやすいものにする効果がある。また、電圧の高低や磁気による記憶を0-1に変換することも抽象化の1つ。フォルダーも抽象化の1つである。

データの記憶について。物理的性質を吸収する役割を持つのがボリューム、フォーマット、ファイルシステム。補助記憶装置はデータを記録する1単位があるが、OSはそれを意識させないようにする役割がある。

OSによる記憶装置の認識について。物理ボリューム内に複数の論理ボリュームを作ることができる。OSは論理ボリュームを別ドライブとして認識する。未対応のファイルシステムは見えない。

第7回

OS構造と周辺機器について。ソフトウェアは他への影響が少ないような課題に分割され、モジュールとして実装される。できるだけ機能の重複がないようにして、モジュールを組み合わせてソフトウェアができる。これを構造化という。中身をブラックボックスにしてインターフェースでやり取りできるようにすれば便利。構造化プログラミングという。

オブジェクト指向プログラミングについて。オブジェクトとインスタンスの話は略。

分割によるソフトウェア開発について。分割されたモジュールそれぞれを見ていくと、ユーザーに近い部分とハードウェアに近い部分では機能が異なる。ユーザー付近では主にUIなど抽象化レベルの高い機能が、ハードウェア付近では抽象化レベルの低い機能が実現される。

OSの下部にはハードウェア抽象化層(HAL)があり、ハードウェアの違いを吸収している。

OSの基本的な機能をカーネルという。スーパーバイザーともいう。モノリシックカーネルは一つのカーネルで全部を補う。UNIXなど。効率的だが、一つのメモリ空間で全部を補わなければいけない。だから一つ不具合が起きれば再起動するしかない。マイクロカーネルはOSの提供する機能を別々に動作させ、OS内にシステムサーバーを設けてマイクロカーネルをそれぞれ担当させる。独立したメモリ空間で実行されるので、異常が発生しても個々のサーバーの問題になる。(具体的なOSは?)手間はかかる。最近は両方を組み合わせたハイブリッドカーネルが流行りである。

ようやく周辺機器の利用について。周辺機器を利用するにはOSに認識させないといけない。周辺機器を接続するとOSからデバイスIDが割り当てられる。デバイスにはHDDのようなブロック型デバイス、キーボードのようなキャラクター型デバイス、ハブのようなパケット型デバイスがある。

デバイスドライバ。HAL層に入るのがデバイスドライバである。階層構造があり、個別のドライバの層と、共通の機能を持つHID(マウス+キーボード)、ディスクドライバ、プリンタ、ネットワークの層がある。ネットワーク層の上にはプロトコルスタックもある。デバイスドライバの上には管理機能の層もある。デバイスドライバを都度勝手に設定してくれるのがプラグアンドプレイ機能。

データ転送の高速化の工夫について。データ転送をずっとやっているとプログラムが止まってしまう。DMAを使うと、DMAコントローラを介して周辺機器とメモリーがCPUを介せず直接アクセスできる。CPUのキャッシュメモリも速度を上げる工夫の一つである。メモリインターリーブは物理メモリにアドレスを分割して記録することで高速化を実現する。

第8回

OSによるプログラム実行管理について。補助記憶装置に記録されたプログラムからプロセスが作成され(ロード)、メインメモリに格納される。プロセスをインスタンスともいう。プロセスはメモリ空間に領域を確保する。プロセスのメモリ空間はコード領域、データ領域(グローバル変数)、ヒープ領域、スタック領域に分割される。ヒープとスタックは容量が可変。コード領域は下から上(アドレス小→大)に向かって実行される。

プロセスの生成と終了。ロード→実行・資源の割り当て→終了・資源の解放という順。プロセスの終了は、正常終了・異常終了・強制終了がある。

複数プロセスの実行。3つのプロセスが実行されているとき、メモリにはそれぞれのプロセスがある。仮想プロセッサがそれぞれのプロセスを担当する。マルチタスクを実現する方法はいろいろある。マルチコアならそれぞれのプロセスを対応させられる。プロセスを担当するコアを動的に切り替えていけば効率的に動作させられる。

プロセス切り替えについて。実行状態を退避するには、記憶装置に、メモリー空間に加えてプロセッサの制御などのコンテキスト空間も保存しないといけない。復旧の時は、コンテキスト空間も一緒に復旧すればよい。プロセス切り替え(コンテキスト切り替え)にはコンテキスト空間も切り替えないといけない。仮想プロセッサに割り当てるコンテキスト空間をそれぞれ記憶装置に持っておいて(コンテキスト退避領域)、プロセスごとに物理プロセッサに毎回割り当てていけば動作を実現できる。マイクロカーネルはカーネル機能をプロセスとして動作させている。常駐プログラムみたいなもん。

スレッド。プロセス内の処理の流れのこと。スレッドごとに仮想プロセッサが割り当てられる。動画エンコーダーとか、webブラウザを考えればよい。画像やら動画やら、画面ごとの処理やらを分割して並列処理している。コンテキスト切り替えのコストは同一プロセス内なので少ない。軽量プロセスとも呼ばれる。

プロセス・スレッドの管理。実行可能状態・実行状態・待ち状態の3つの状態がある。実行可能状態では仮想プロセッサが割り当てられていない状態、実行状態は仮想プロセッサが割り当てられて動作している状態、待ち状態はプロセッサとは関係なく実行の中断している状態をいう。プロセスが開始すると実行可能状態と実行状態を行き来して、終了する。待ち状態は、主に周辺機器を使う場合に実行状態から遷移する。待ちが終わったら実行可能状態に遷移する。

OSの特権モード、非特権モード。特権モードは全ての機能が使える。入出力や制御機能も使える。非特権モードは通常の使い方で、制限がある。モードは階層構造も持てる。

スケジューリング。OSのカーネルが持つ。実行可能状態のプロセスを順序だてて実行する。スループットがなるべく高くなるようにしたい。待ち状態や無限ループが発生している場合は飛ばしたい(具体的なやり方は不明)。ここは詳しいことがわかんなかったっす。。

第9回

プロセスの協調動作とメモリー。プロセス協調とは。プロセスが複数同時に実行されること。プロセス内には複数のスレッドがある。すると資源の譲り合いが必要になる。プロセスにはそれぞれ仮想プロセッサを割り当てる。プロセス間のを同期を取る必要がある。

プロセスαとβがあるとする。同じ資源を利用する命令がある場合どうするか。例えばファイル書き込み。同時に書くとファイルが壊れるから、一方が書き込み中は他方の書き込みを禁止しないといけない。プリンターも同時に使えない。資源の取り合いが発生することを競合という。資源の解放待ちの時間のことを封鎖ブロックという。封鎖ブロックが終わったらプロセスは再開する。

相互排除。資源を利用するスレッドを1つにすること。利用中であることを占有とかロックという。利用できないことを封鎖とかブロックという。資源管理はOSが行う。資源を利用する機会は全てのプロセスに公平に与えられるし、時間がかかっても必ず資源が利用できる。

資源管理用のプログラムを制御プログラムという。管理を行うところをクリティカルセクションという。クリティカルセクションでやること。一番簡単なのは割り込みの禁止。簡単だが他のプロセスに支障が出ることがあるから、できるのは短時間だけ。

次にフラグを使う。記憶領域に01のフラグを作っておいて、1にするのをフラグを上げる、0にするのをフラグを下げるという。資源のフラグを上げておけば、利用中というわけ。

セマフォによる管理。セマフォ変数を使う。0以上の値を記録できる。最大で使える回数を最初に設定しておいて、P操作(acquire)でデクリメント、V操作(release)でインクリメントする。0なら使えないってわけ。

資源の管理を行っていてもデッドロックになることがある。みんなが解放待ちになって処理が進まないこと。

プロセス間通信。プロセス同士のデータ交換のこと。メモリー共有、メッセージ通信といった方法がある。共有領域つかったことあったっけ?あんまやんないよね。危険だし。メッセージ通信にはIPCとか。メッセージで同期を取ることもできる。これはけっこう実務でもやる。データベース管理ツールと、メインのプログラムでよく通信してる。チャネル、ポート、メッセージボックスなどを介する。

メモリー管理。OSを使ってメモリを管理することを考える。カーネルとプロセスの間に連続した空き領域ができる。プログラムに応じて連続した空き領域の所を使っていくが、細切れになってしまうことがある。断片化という。断片化解消の方法としてコンパクションがある。デフラグみたいなやつ。実行中に再配置できるのをリロケータブルという。

ページング。物理アドレス空間と論理アドレス空間は違うという話。たしかに、論理アドレス使わないとコンパクションとかできないよね。論理アドレスがあるからこそ連続したメモリ領域の確保ができる。C言語では論理アドレス使ってるんじゃないか?物理アドレスの1単位をページとかフレームという。論理アドレスと関連付ける機能をMMUという。関連付け自体をマッピングという。

仮想メモリ―の仕組み。まずオーバーレイから。プログラムをオーバーレイローダー+ルートモジュール+モジュール(複数)に分割。機能が必要になった時点でモジュールを切り替える機能のこと。

仮想メモリ―。物理メモリーに加えて補助記憶装置(バッキングストア)を足して仮想メモリーにすること。ページングによって、論理ページ⇔物理ページの対応表(ページテーブル)が作られるが、物理ページが割り当たってない論理ページを参照(ページフォールト)が起きれば、バッキングストアからデータを持ってくることになる。これをページインという。頁アウトは意味わかりませんでした。印刷教材を読みます。

第10回

記憶装置とOSの起動。記憶装置の話。一次記憶装置と二次記憶装置。プロセッサ、電源と連動した記憶保持をするのが一時記憶装置。いろんな記憶装置を紹介してくれてる(略)。

半導体メモリーの分類。RAM→SRAM(Static RAM、高速低容量), DRAM(Dynamic RAM、高容量)。ROM→マスクROM(完全読み込み専用)、EEPROM(Electronically Erasable and Programmable ROM、たまに変更できる)、フラッシュメモリー(ほとんどはこれ、書き換え可能)。マスクROMはこれファミコンのカートリッジだな。電池ついてるし。

フラッシュメモリーの分類。NOR型。アドレス指定でランダムアクセス可能なのでプログラムも記録できる。BIOSやスマホのファームウェアなど。NAND型。ページ単位のアクセスが可能。大容量用。SSDとかUSBメモリとか。NAND型にはSLC(Single Level Cell)型とMLC(Multiple Level Cell)型がある。MLCの方が大容量。

フラッシュメモリーと記憶素子について。記憶素子ごとに記憶できる回数が決まっている。まんべんなく使えば寿命を延ばせる(ウエアレベリング)。

補助記憶装置(略)。

OSの起動と動作モード。起動中の動作をブート、ブートストラップという。電源ON→リセット割り込み発生→ブートローダーがBIOSを実行→IPLを実行して二次ブートローダが実行→OS実行という流れ。

コールドスタート(ハードウェア初期化有)、ウォームスタート(ハードウェア初期化されてる状態からの起動)。

OSの動作モード。サスペンド→待機状態。メモリのみ電源保持。ハイバネーション→補助記憶装置にメモリの内容を移してから電源OFF。ハイブリッドスリープ→両方の組み合わせ。

第11回

OSについて。OSの種類から。スパコンは専用OS。組み込み機器はTRONなど。サーバーはUNIXだよね。規模にあったOSを適用することをスケーラビリティという。最近はスマホ→PCの順でソフトウェアが移植されるようになってきた。これをモバイルファーストという。

スケジューリングの違い。単位時間をタイムスライスと言い、タイムスライスごとに平等にプロセスを回るのがラウンドロビン。時間が長いプロセスを優先することになる。これを使うのはタイムシェアリングOSという。

リアルタイム処理。携帯電話の着信があった場合を考える。タイムシェアリングだと通信の途切れが発生する。なので優先度を上げたい。イベントに基づいた優先順位付けをイベントドリブン・スケジューリングという。優先度が高いプロセスが来たらプロセッサを横取りする。これがリアルタイム処理。このような動作をするOSをリアルタイムOSという。

定期的に同じ処理を行う処理を周期プロセスという。これは動作を予測できるので、アルゴリズムに組み込みやすい。リアルタイム処理にも二種類、ハードリアルタイム(〆切が厳しい)、ソフトリアルタイムがある。

汎用OSと組み込みOS。規模が大きい場合は汎用OS、タイムシェアリングを利用しがち。スマホ、携帯、組み込み機器は組み込みOSになる。

汎用OSの動作。ROMにブートローダーが記録されていて、まずこれを実行する。OSは補助記憶装置からRAMに読み込み、OSが実行される。

組み込みOSの動作。OSはROMに書いてある。一部はRAMに転送。ほとんど書き換えないで高速に動作させる。一部のデータだけをRAMに書く。

省電力モード。プロセッサ停止モードとクロック停止モードがある。ハイバネーション=クロック停止モードのこと。プロセッサー停止モードの方が簡易。何か押せば元に戻れる。クロック停止モードだと何か特殊な操作が必要(電源ボタン押すとか?)。

第12回

OSとソフトウェア開発について。ソフトウェアはアプリとも呼ばれる。

家電や携帯機器のプロセッサの選択。低コスト、小型化、省電力、軽量が望まれる。PCよりも性能が最低限のものになりがち。

プログラム実行とOS。OSがない場合もある。OSがない場合、リソースがいらないというメリットもあるが、だいたいはOSも搭載してる。

ポットの制御を考える。ヒーターをONにすると水温上昇、OFFなら下降する。温度センサーで水温を測定し、設定温度との比較を行い、ヒーターのON/OFFを切り替える。これならOSはいらない。

複雑な制御をする場合。プログラムXがモジュールA,B,C,Dでできていると考える。モジュールが関係しあっている場合は、これを制御するのが大変。そこでOSを使った方が楽になる。開発の利便性を取る場合はOSを搭載した方が有利。

組み込み機器では必要な機能を絞ったOSを使うことになる。必要な機能はタスク管理、割り込み管理、ネットワークと通信、グラフィック機能があればよい。

分割によるソフトウェア開発。APIを搭載していればモジュールに分割して開発できる。

システムコール。割り込みを発生させる処理のこと。システムコールには番号が割り当てられている(システムコール番号)。スーパーバイザー呼び出しをプログラムが呼び出して割り込みが発生する。

プログラム開発について。セルフ開発とクロス開発。セルフ開発はホストとターゲットが同じ、クロスは例えばPCでスマホの開発をする場合など。

互換性。バイナリレベル互換とソースレベル互換。バイナリレベルはそのまんま使える互換。ソースファイルは複数環境でコンパイルできるのでこれで互換性を保つことををいう。移植はソースファイル互換では足りない環境依存部分だけを修正すること。仮想マシンを使えばどんな環境でも同じプログラムの実行ができる。Javaとか。

第13回

ユーザーインターフェースについて。昔の出力部分はLEDとか電球とかだった。入出力装置としてはほかにDIPスイッチがある。4bitメモリーと同じ。昔はメモリーがないので、マークシートやパンチカードを使っていた。オペレーターという担当者を介していた。OSと同じ。

最初の使い方はバッチ処理。オペレーターに渡して、コンピュータを使って実行してもらう。コンピュータが決められた手順でプログラムを連続して実行していた。1970年ごろまで。

次は対話形式。コンピュータにコマンドを入力して、結果を返してもらう。これの繰り返し。

フォントによる文字の表示。文字列をコンピュータがビットマップに変換してディスプレイに表示する。

ウインドウシステムの登場。GUIを使って直接操作方式を採用し、より直感的になった。

インターフェースの分類。ハードウェアインターフェース(機器同士)、ソフトウェア・インターフェース(ソフトウェア同士)、ユーザー・インターフェース(コンピュータと人間)をつなぐもの。

人間とコンピュータとの接点について。メンタルモデル。マニュアルを読んで操作方法を獲得する。この時に頭に作られるモデルをメンタルモデルという。インターフェースを工夫すると、メンタルモデルが作られるまでの時間を短縮できる。インターフェースには日常生活のメタファーが用いられる。例えばデスクトップ画面。机に見立てている。

アフォーダンス。人に行動を誘発させること。アイコンやボタンのデザイン。プチプチを見るとつぶしたくなるよね。ボタンがあるとクリックしたくなるよね。色の対比でもアフォーダンスを表現できる。配置も大事。視野に配慮したゲシュタルト特性を考えることもある。

入力装置。人間の中にある情報を入力する場合と、外にある情報を使って入力する場合がある。キーボードは前者。ポインティングデバイスや音声認識もある。出力。ディスプレイが用いられる。HMD(ヘッドマウントディスプレイ)なんかも出現している。

これからのインターフェース。モバイルの文字入力。携帯ではT9というテンキーベース。スマホやタブレットではソフトウェアキーボードが使われる。

ウエアラブルコンピューティング。いつも利用できる、人間の能力の拡張、コンピュータによって外界との情報の調停を行うこと。

第14回

OSとセキュリティー。複数の利用者でコンピューターを共用するには、プライバシー保護と個人環境の維持が必要になる。これを可能にするのをマルチユーザー機能という。なので利用者識別のアカウントとパスワードが必要になる。ファイル操作については略。

OSによる資源の保護について。アクセス制御。操作に属性を付加する。具体的には書き込みとか読み込みとか。アクセス制御情報はアクセス制御行列で表される。行が主体(domain)、列が対象(object)となる。それぞれR(読み), W(書き), X(変更)ができたりできなかったりを設定する。

ケーパビリティリスト。ドメイン(主体)と対象、操作(ファイルAとRとか)の一覧にしたもの。これは一覧の作成が大変なので、普通はアクセス制御リストを使う。対象ごとに、ドメインとアクセス権をセットにしたもの。

セキュリティと暗号化。CIAの要件がここでも出てきた。脆弱性、暗号化、ユーザー認証などは情報セキュリティ概論でやったからいいか。

第15回

コンピュータの利用形態とOS。最初の開発の部分は今までの復習って感じなので略。

SoC。System on Chip。チップ一個で必要なシステムを実現すること。基盤の構成が簡単になる。小型化、高速化にも有利。

ユビキタスコンピューティング。パーベイシブコンピューティングともいう。いたるところにコンピュータを組み込むこと。前から言われてたねこれ。小型化高速化でだんだん現実味を帯びてきてる。

クラウドコンピューティングの定義。「構成の変更が可能な計算機資源の共用領域に簡単にそしてオンデマンドにネットワーク経由によるアクセスを可能とするモデル」ああいわれてみれば。特徴は①オンデマンドセルフサービス②幅広いネットワークアクセス③計算機資源のプール④迅速な伸縮性⑤計測されるサービス。

仮想化技術。OSの上にハイパーバイザーを載せて、さらにその上でOSを複数実行する。これをゲストOSという。ハードウェアの上に直接ハイパーバイザーをおくパターンもある(ハイパーバイザー型)。クラウドコンピューティングではよく用いられているらしい。

IoT。ウエアラブル端末とかも入るのね。ヘルスケア端末もネットワーク利用ができる。蓄積された情報の分析も可能。自動車のプローブ情報(運行情報のこと?)も活用が期待されている。

センサーとアクチュエータ。ボタン、動き、温度湿度を計測したり、LEDを光らせたりできる。プログラミングしたらいろいろ動作可能(なんてアプリだろこれ?)。

実世界と仮想世界。IoTで得た情報を「実世界⇔仮想世界⇔コンピュータ処理」の相互作用に載せて、実社会に役立てることができる。

放送大学全科目感想 015 心理と教育へのいざない(’18)

  • 心理と教育コース
  • 導入科目
  • ラジオ科目
  • 田中統治先生(放送大学特任教授)
  • 向田久美子先生(放送大学准教授)
  • 佐藤仁美先生(放送大学准教授)

第1回

教育学の概説。田中先生。田中先生は共通テストの委員会の副座長でカリキュラムに詳しい。で、その先生がカリキュラムの一般化を嘆いているという話だった。

教育は抽象化が大事。いままで自分が受けた教育だけの話をしたって一般性がない。モデル化、理論化して初めて他人に教えられような価値のある教育学になる。

教育には何かを教えたいという度合いが強くなるほど、教育効果が薄れるという特徴がある。これを教育のパラドックスという。塾講師での実感として全くその通りだと思う。

教育には教授するベクトルと引き出すベクトル(用語忘れた)があり、伝統的には前者に重きが置かれている。でも先生は後者を重要視している。赤ちゃんですら内面に持っているものがある。それを引き出してやる。

個別化と一般化のベクトルもある。経験上、個別指導塾では一般的なことより個別的な対応をした方が本人の満足度も指導効果も高い。基本的には個人の自発性に任せ、教師は補助をしてあげるというスタンスだ。これがチェーン店だと一般的なカリキュラム重視になってしまうのだろう。個別指導塾で一般的なことやるのなんて方向性が食い違ってると思うけどね。

放送大学全科目感想 014 データの分析と知識発見(’20)

  • 情報コース
  • テレビ講義
  • 秋光淳生先生(放送大学准教授)
  • 難易度 ★★★☆☆
  • おすすめ度 ★★★☆☆

Rを使ってデータ分析を行う。生徒さん3人(本業はみんな声優さん)と秋光先生が講義する形式で進む。印刷教材との使い分けができているという意味ではよいが、生徒さんがRで演習しているところは放送授業の無駄遣いって感じもする。講義内容自体はすばらしい。非常に短時間で簡潔に、Rの基本から仮説検定、主成分分析、因子分析のような統計の基本だけではなくニューラルネットワーク、形態素解析などにも踏み込んだ説明をしてくれる。かなりわかりやすい。

第1回

基本的にRの話らしい。学生役が3人。俳優さんという感じ。柔らかい雰囲気。講義ではR-Studioを使う。各項目を見る限りでは結構分析手法が本格的で大変そう。

Society5.0について。もう5.0なの?4.0とかどんなんだったん?あらゆるものがインターネットにつながっているということらしい。

データの利活用について。客観的根拠に基づきに判断せよとのこと。分析結果の読取りはもちろん、結果は言葉で表現できないといけない。データは何を表しているのか?何が読み取れるのか?ということが大事。

データは収集選択し、処理して変換するもの。分析に適するように変換したものを様々な手法を通して解釈し、検証し知識を発見する。ここら辺はウォーターフォール的ではなく行きつ戻りつする。データマイニングは言葉としてはもう古いらしい。

Rの基本操作について。オープンソースで無料らしい。先生macよりwindowsを先に言ってるからwindows派だな。とおもったらmacの画面出てきた。生徒さんはwindowsだ。生徒さんの操作の過程がでてきてる。自分でも操作した方がいいのかなあ。

1+2と入力すると3が出る。変数にも x1 <- 2 のようにすれば値が代入できる。生徒さん操作に慣れなさすぎで、先生がJISキーボードの解説してる。ライブ感はあるが生徒さんが操作してる時間が長い。印刷教材とギャップがあるのでは。。

第2回

レポート作成。平均や分散を計算したりする。生徒さん服が変わったので毎回別の日に収録してるのね。

メモをどう取るか。私はスマホ派ですがカレンダーに書いたりもします。

代表値。最大・最小・平均・最頻・中央値などのこと。今日はこれらを計算するのかな。中央値とかも一発で計算できるのかな?

平均値の定義。いきなり大変な数式になった。平均はμで表す。分散をn-1で割る場合はこれを不偏分散というらしい。

Rは配列をc(combine)で表す。 y1 <- c(80,91,22,67,88) みたいな感じ。mean(y1) で平均、var(y1)で標準偏差が求められる。配列の範囲は[1:5]みたいに表す。Rは0ベースじゃなくて1ベースなのね。y1[1] <- 40 のようにすれば配列の要素にアクセス・代入できる。

Rスクリプトについて。スクリプトのウインドウを開いて、命令を書きまくっていけばバッチ実行できるってわけか。Rはスクリプトがメインだろうなあ。当然ファイル読み込みもできる。コメントは # 井桁で表す。標準出力はprintを使えばいい。

knitrを使ってレポートを作ること。wordでも作れるらしい。でも文章自体はmarkdown形式なんだなあ。便利だよねmarkdown。

マークアップ言語とWYSIWIGの違い。マークアップはHTMLなど文章と命令がセットになっているもののことを言う。Markdownはマークアップを簡略したもののこと。R MarkdownはR独自のMarkdownなのか。例えば“`で囲むとRの命令をそのまま出力することができる。#は見出し。先生けっこう難しいこと話してるから、生徒さんついてけてるか心配や。

第3回

ファイル操作。

Rのデータ型には整数とかbooleanのほかにファクターってのがあるらしい(あとで学ぶ)。データ形式にはスカラ、ベクトル、行列のほかにリスト、フレーム(?)ってのもある。

行列は A <- matrix(c(1,2,3,4,5,6),ncol=3,nrow=2) みたいに代入する。デフォルトでは列ごとに代入だが。nrow=2のとこをbyrow=Tにすると、行から代入する。

リストはジャグ配列と同じ。sasaki<-list(“英語”,…)みたいに代入。

データフレームは一番よく出てくる。データベースとほぼ同じ。リストで列ごとにデータ型を固定したもの。代入はheightとweightの配列があったとき、 D<-data.frame(height, weight) みたいにすればよい。D と入力すれば表が表示される。

ファイル読み込み。csvかタブ区切りが基本みたい。まあ基本はタブだよね。文字列にカンマ入ってたら終わりだから。タブ区切りファイルはread.table(), csvはread.csv()で読める。

生徒さんの操作確認の所が壮大に無駄だぜ!

共分散、相関関係の計算方法。原理原則は高校の数Iでやったことの復習だ。var()が分散+共分散、cor()が相関係数を算出するコマンド。一発で出るので楽じゃん。Rは統計に特化して、頻発する命令を短くしたものなんだな。言語ってそういうものかも。よく出る語彙は短いよね。

第4回

表の作成(クロス集計)について。秋光先生と生徒さんのやり取りはアドリブかな。秋光先生の反応けっこう変わってる。

尺度について。質的データ(名義尺度、順序尺度)と量的データ(間隔尺度、比例尺度)がある。尺度ってのは単位のことだろうか。名義尺度はそのまんま名前のこと。名前にはあんまり意味がない。区別することだけが目的。順序尺度は順位とかアンケートの度合いとか。間隔がどれも等しいわけではないことが特徴。先生が持ってるデジタル式のレーザーポインターみたいなやつ便利だな。間隔尺度は全部等間隔に並んでるデータのこと。比例尺度は何かを基準にして1.5倍とか7倍とかで集計するやり方のこと。比例尺度は0が決まってないといけない。0がないこともある。例えば温度。摂氏0度には存在しないという意味はない。西暦も同じ。これらは比例尺度は使えない。

クロス集計表。2つの事象が起きた・起きなかったことを○○ ○× ×○ ××の4つに分類して正方形の形で集計すること。1つの事象だけ集計したものを周辺度数、全部合計したものを全体度数という。相対度数は3種類になる。行についての相対度数、列についての相対度数、全体度数に対する相対度数。全体度数が一番見やすいかな。項目を増やせば多重クロス表も作れる。

シンプソンのパラドックスについて。全体でみると勉強した人の方が合格しているのに、40歳以上・未満で集計するとどちらも勉強しなかった人の方が合格している。足し合わせるのと個別で見るのでは別の見た目になることが起きる(なんで??)。

相関の考え方。ファイ係数とユール係数がある。どちらもad-bcを計算している。-1~1の値が出る。相関関係があれば1に近づく。事象2つではなく複数になった場合は、期待度数とかカイ二乗値を考える。期待度数は行や列の合計から各項目の値の予想値を計算したもの。これの実際の値とのずれ具合がカイ二乗値らしい。

実際にRを使っていく。table関数でクロス集計表の作成、addmarginsで合計を計算してくれる。

第5回

グラフの作成。生徒さんみんな家で自学してるらしい。えらい。

散布図はplot() 折れ線はtype=o (plot使うってこと?) 円グラフはpie() (色遣いはどうやって指定するんだろ?)棒グラフはbarplot() ヒストグラムはhist() で書く。

円グラフは全体の割合、棒グラフは0から始まる(とは限らない)ことが大事。

見出しはmain= 軸の名前はxlab= ylab= 凡例はlegend で表す。点とか文字とかを追加したければpoints()とかtext()とかを使う。

実際やってみる。やはり折れ線はplot(type=”o”)でやるらしい。b(プロットにかぶらない線), l(ただの線)も使える。text(h1,rownames(h1)) ならテキストがグラフ上に表示される。plot→textの順で呼べばグラフにテキストが追加される、という流れになる。

関数のグラフ。curve(log(x))でlogxのグラフが書ける。curve(sin(x))でsinxのグラフ。これいいな。tex文章に追加できないかな。

ファクターについて。size <- factor(c(“S”, “M”, “L”)) などのように指定する。数値にラベルを付けることもできる。範囲はcut(sh, breaks(c(min(sh)-1, 10, max(sh)), label=c(“N”, “Y”)) などのように指定する。これで年齢層を3分割できたりする。col=rainbowにすれば虹色の棒グラフができる。

生徒さん意味わからなさ過ぎてつかれている。

第6回

検定の話。生徒さんが宿題出されててそれをちゃんとこなしてるのがすごい。Rってグラフきれいですね。

仮説検定。母集団から標本を取り出したとき、標本の特徴から母集団の特徴を取り出すことができるのか?というのが検定。標本を取り出したら、めったに起きないことが起きたのが第1種の過誤、本当には起きていないのに起きたと間違えるのが第2種の過誤。

確率分布の話。連続分布と離散的分布。離散的分布で代表的なのは二項分布。サイコロの出る目の確率でよく使う。10回投げて10回全部表になるのはめったに起こらない。連続分布だと正規分布が一番有名。形は難しいけどこれってたしか積分したら1になるようにしてるんだよね。

Rではdで始まるやつが密度関数。dbinomとか、dnormとか。確率(積分したところの値)ははp、確率点(?)q、乱数はr。検定は.testでカイ二乗検定ならchisq.test。短い名前でだいたい全部の分布が実装されている。よく使うんだね。例えばpnorm(2.0,1)なら2σ以下になる確率で、0.997…となる。

正規分布の曲線、グラフがたったの8行で書けている。すごいね。

rbinom(10,10,1/6)みたいにすれば、10回サイコロを振って何回1が出ますか、という意味になる。二項分布が正規分布に近づく、ということもR上で確かめられる。

カイ二乗検定の実践。先生私プログラマーですけど、意味わかりません。概念的には、プログラム上で乱数を発生させて、カイ二乗検定をして、集計してヒストグラムに表せるってことなんですね。それ以上のことは不明。

第7回

回帰分析。線形の多項式について、データからこれらの係数を求めることが目的。係数aは最小二乗法で求める。実際どうやって内部で求めてるんだろね。行列?→偏微分 = 0で求めるらしい。

偏微分 = 0 を解くと、全体平均を必ず通ることが分かる。回帰曲線の係数aは、分散、共分散を用いて Sxy – aSxx = 0という関係があるらしい(まじで!!??)数学的な意味は印刷教材でじっくり見てみよう。この関係から、変数がn個の場合でも分散、共分散の行列を考えれば、逆行列を出すとaが出てくる。

先生~数学的に厳密であろうとして生徒さんが置いていかれてます!!逆行列も概念的に説明しようとしてますます意味わからなくなってます!でも数学理解できてたらグラフの意味が分かってくるってのは同意です。数学大事。

予測の精度の話。回帰曲線は分散が0でなければ出せるけど、予測が正しいかどうかはなんともいえない。乱数を足したり引いたりするとわかる。測定値の分散というのは、数学的に計算すると、予測値の分散と残差(予測値の差)の分散の和になっていることが分かる。残差の分散が少なければ少ないほど誤差が少ないといえる。そこで残差が少ないほど1に近づく変数を定義し、決定係数と呼ぶ。決定係数が0.9なら残差少ないね、よかったね、ということになる。

偏相関係数について。見かけの相関を説明する係数のこと(いみわからんかったので印刷教材にパス)

Rでやる方法。h2 <- lm(weight~height, data=h1) って打つだけ。lm? 短いな。で、plot(h1), abline(h2) で終わり。これで回帰曲線が書ける。summary(h1) って打つだけでいろんな検定値、平均やら分散やら全部出てくるので便利。str(h2)ってやるとさらに、回帰分析的なデータがいっぱい出てくる。

第8回

主成分分析について。変数をできるだけ減らすことらしい。データの圧縮のこと。先生スライド分かりやすいっすね。

平均化→平均を0にする。標準化→平均化+標準偏差で割って標準偏差が1になるようにする。

主成分分析の導出。y個のデータをz個に減らす場合、y1~yrまでのデータに係数をかけてzmを定義してやる。そうして変数を減らしていく。というわけで係数の導出がまた問題になってくる。概念的には、立体(変数3つ)を平面(変数2つ)で切って膨らんでいる方向を決定していく過程になるらしい。

元々の情報量を射影して、損失(直交する量)がなるべく小さくなるようにするのが原則。いろいろ掛け合わせて足し合わせると、また分散と共分散が出てくる。標準化すれば結局相関係数を使えば係数が出てくることになる。で、これを最小にするためには、ラグランジュの未定乗数法を使う。これは結局、分散・共分散行列の固有値・固有ベクトルを求めることと同じ。これで求まる。

寄与率。主成分分析の決定係数みたいなやつらしい。どれだけうまく予測できているかの尺度。さっきの式で固有値が出てくるけど、この固有値が大きい順に第1主成分、第2主成分というように決定できる。寄与率は、(自分の固有値 / 全固有値)、で求まる。累積寄与率は、でかい方から寄与率を足していって自分まで足したときの値になる。

Rでやってみる。prcomp() を使えば一発。ここまではprcompで何やってるのかっていう解説なのね。

身長体重で主成分分析をすると、両方√1/2にしたやつが第一主成分になる。これでほぼほぼ表せてしまうらしい。ほとんど比例ですねってときはこうなるのかな。身長体重両方を主成分分析したグラフの軸にすると、ほとんど重なってしまう。

主成分分析は回帰分析と似ているけど、回帰分析が縦方向の値を減らすのに対して主成分分析は(回帰直線の?)垂線方向の値を減らしている。ので、目的が違うという話だった。

第9回

因子分析。観測データの背後に潜む因子を見つけること。独自因子、共通因子の2つがある。共通因子がメインで、それにプラスして独自因子を使うって感じらしい。変数より因子の方が数が多くなる。

Y=CF+DEと表現できる(行列)。Cは係数行列、Fが共通因子、Eが独自因子。共通因子、独自因子は平均0、分散1。共通因子、独立因子は独立で相関なし、共通因子間には相関があることもある。ない場合は直交解、ある場合は斜交解。

分析手順。共通因子の個数を決める。カイザーガットマン基準(相関行列の固有値1以上)、スクリープロット(相関行列の固有値のグラフから決める)を使う。→因子負荷量を求める。最尤法、最小二乗法、主因子法がある。→因子軸の回転を行う→解釈。

最尤法について。5回闘って3回勝つ確率は?二項分布で考えると5C3 * p^3 * (1-p)^2 である。(それで??)

因子の回転について。因子負荷量は一意には決まらない。回転によって特徴が分かりやすいような、解釈しやすいような軸を探す。直交回転(バリマックス法)、斜交回転(プロマックス法)がある。

演習。まずread.tableでテーブル読んで、corで相関係数を計算、plot(eigen())で固有値をプロット。これはスクリープロットにあたる。次にw3<-factanal(w1, 2, rotation = “promax”)で因子分析。プロマックス法を使ってる。で、最後にplot(w3)で結果表示。Rで書くと一瞬だね。

eigen()で固有値が1以上なのが2個、スクリープロットで見ても2個だけ固有値でかいから、2つを採用する。今回の例なら統計学+心理学史、精神分析+神経科学+認知心理学にそれぞれ共通因子があるように見える。これをFactor1, Factor2とする。共通因子行列Fが作れる。後は独自因子をつけていけばいい。例だと共通因子で50%くらい説明できたということらしい。

第10回

多次元尺度法。まず距離の公理について。非負性(負にならない)、非退化性(点が等しければ0)、対称性(順序を逆にしても等しい)、三角不等式(a<b+c)。要するに三角形の頂点間の距離について成り立つことだと思う。

古典的多次元尺度法。距離が分かっている仮定で座標を求める。距離行列Dを考える。各成分は各点間の距離の二乗。

各点を表す行列Xから、ヤングハウスホルダー変換をして距離行列Dに変換する。回転、反転、平行移動をして、距離行列を満たすようなXを求める。感覚としては行列ごと二乗するような感じ。これをまたよくわからん変換をして対角化、固有値を求めると中心を原点に来るような座標に変換してあげられる(ぜんぜんわかりませんでした)。

Rでの演習。cmdscaleを使う。サンプルとして山手線の駅間所要時間の二次元行列を使う。readしてからas.distで距離の形に変換、そのあとcmdscaleで多次元尺度法の計算を行う。あとはplotで表示。textで座標の上に名前を表示してあげる。何ができるかというと山手線ができます。cmdscaleでk=2を指定して二次元に変換したところ、65%くらいの情報が説明できているということになった。

第11回

クラスター分析。

前回の山手線のデータを使って階層的クラスター分析。渋谷、原宿が近いのでグループとしてまとまる。もう少し距離を挙げていくと高田馬場・池袋とか、上野・秋葉原とか。サブグループをまとめていくと山手線の西、東でまとまる。最後に全部が一つにまとまって終わり。こういう束ね方を階層的クラスター分析という。樹形図で表現できる。

作り方。まず距離の近い2つの点をまとめる。二点間距離がわかってればできる。で、点をまとめるんだけど、まとめた点と他の点との距離を計算する方法はどうするか。例えばABとCの距離。AB間の真ん中を取るか、ACとBCの最小値にするか。どちらかを採用して、また計算し直す。再計算法には最短距離法、最長距離法、群平均法(距離の平均を求める)、重心法(真ん中を取る)、ウォード法(クラスターが巨大にならないようにする。グループ間の距離が最小になるようにする)がある。

演習。また山手線のデータを使う。read.csv→as,distまでは前回と同じ。そのあと、hclust()でクラスター分析する。method=””に方法を指定。最短距離法はsingle、最長距離法はcomplete、群平均法はaverage、重心法はcentroid、ウォード法はward.D2を指定。ここではウォード法を使う。で、plotでプロットする。

プロットしてみると5つとも距離が結構違う。singleだと品川がハブられてしまう。バランスが悪い。completeだとグループはいい感じになる。centroidも品川がハブられる。ウォード法もいい感じ。

k平均法。k個のグループに分けること。2個点を選んで、2つのグループの代表者として、近い点の代表点のグループに分ける。次に、グループの重心を代表点とする。次に重心からグループを作る。これを繰り返して、グループが変わらなくなるまで続ける。これだと最初ランダムに適当に2点を選んでも必ずどこかに収束する。ただ、収束する点は一意になるわけではない。

Rで演習。read.table→kmeansで終わり。plotとpointsで表示。

第12回

アソシエーション分析。まず因果関係の話。ビールと紙おむつの相関は。紙おむつを買いに来たお父さんがビールも買って帰る。相関というのは、同じ人が買ったという関係がある、ということ。

アソシエーションルール。100人の学生がA~Eの5科目のいずれかを学習する場合、学生+受講科目の組をトランザクションデータという。例えばAとBという科目に注目。n(A) n(B) n(A, B) などの集合が考えられる。A→Bが言える場合は、AがBの部分集合ということになる。するとBに占めるAの割合なども計算できる。

アソシエーションルールの指標。支持度、期待信頼度:自分/全体。支持度はAかつBの割合で、期待信頼度はBの割合。信頼度は条件付確率みたいなもので、リフト値は信頼度/期待信頼度。期待信頼度は打率、信頼度はチャンスの時にヒットを打つ割合。リフト値はチャンスの時のヒットを打つ割合は通常の打率と比べてどのくらいか。

例。100人いてA25人B40人AかつB20人→支持度は20/100=0.2 期待信頼度40/100=0.4 信頼度20/25=0.8 リフト値0.8/0.4=2

Rで演習。arulesというパッケージを使う。Groceriesを読む→as(g0, “data.frame”)で変換→itemFrequency→apriori()で計算。パラメータはlist(confidence=0.5,support=0.01)に設定。→sort(d=T, by=confidence)→inspectで調べる。supportは支持度、confidenceは信頼度かな。

(confidence=0.5,support=0.01) のところはフィルターのようなもので、数値が大きければルールはいっぱい見つかるし、小さければ絞れるが0個しか見つからないかもしれない。

第13回

決定木。グラフの定義から。頂点(ノード)と枝(エッジ)があるのがグラフ。ループがないグラフを木という。集合は分割して木構造にすることができる。図だとわかりやすいんだけどちょっと言葉では表しにくい。分け方は一意ではないので構造は一通りではなく、分割方法に依存する。

とはいっても一番特徴をよく表している木を作りたい。どうするのか。例えば成績データ。属性と点数を関連付けた気を作りたい。属性を説明変数、点数を目的変数と呼ぶ。目的変数がカテゴリー変数(数種類ある)なら分類木。連続変数なら回帰木にするのがよい。今回は点数を70点以上、70点未満に分けているので、分類木がよい。

40歳以上、未満、男性、女性という属性で分類すると、70点以上/未満の散らばり具合はどうか。年齢か性別のどっちがいいかどうやって判断するか。指標となるのはジニ係数。不純度が低くなるように分割する。不純度が低いというのは、別のものを取り出す割合が小さいということ。ジニ係数の計算方法は1 – pa^2 – pb^2。確率の二乗を引いたもの。分割前は0.5だけど、男女で分けると0.444, 0.375。年齢で分けると0.32, 0.32。年齢の方がいいね、ということがわかる。なので年齢を使って木構造にしよう。

Rで演習。rpartというパッケージを使う。read.csv→rpart(?? + ?? + …, method = “class”)→library(rpart.plot)→rpart.plot(extra=2)で。

第14回

ニューラルネットワーク。なんか突然神経の話になった。神経はパルスを出す。シナプスを出して他の神経細胞に伝えていく。電位が上がったり下がったりするんだけどある程度高くなると突然パルスを出す(らしい)。神経細胞をモデル化すると数式にできる。重みを掛け算して足し算して、ある程度のしきい値を超えるとパルスを出す。uを足し算した値とすると、パルスはy=f(u)。f(u)をシグモイド関数という。パラメータの取り方によっては急激に1に近づくようにもできる。

階層型ネットワーク。ニューロン同士は複雑なネットワークを作れる。これを簡単にするために、左から右に繋がっていくようなネットワークを考える。例えば入力、中間層、出力で構成するネットワークを考えることができる。どれも複数あるので、多入力多出力の関数という。

バックプロパゲーション。入力と出力、あと教師信号を用意する。教師信号と出力と比較して誤差を計算し、また後ろに流す。誤差は二乗で評価。結合荷重wは偏微分で-をつける。(よくわからんかった)

最急降下法。結合荷重が誤差に与える影響を計算し、誤差が減る方向に結合荷重を修正するのだけれど、偏微分を使うので、どこに解を持ってくるかが問題となる。局所解に収束してしまうので、初期値によって結果が変わってくる。

汎化と過学習。教師信号が誤差を含むことがある。学習が不十分でもありすぎてもいけない。粒度が問題になる?

Rで演習。サインカーブを用いる。訓練用データと検証用データを使う。nnetライブラリを使う。nnet(output~input, data=train, size=1, maxit=1000)→predict()でできる。あとはplot, pointでグラフを書いて検証。中間層を大きくしたり、イタレーションを大きくすると時間がかかる。あんまり中間層が大きいと過学習になる。

第15回

テキストマイニング。まず形態素解析から。自然言語処理と同じ話や。文を語に分解するのが形態素解析、これを組み合わせると構文解析になる。「横浜に行った」なら「横浜(名詞)」「に(助詞)」「行っ(動詞)」「た(助動詞)」。ソフトウェアで有名なのはChasen, MeCab, Jumanなど。

演習。青空文庫テキストを使う。RMeCabを使って、docMatrix(“C15, pos=c(“連体詞”,”副詞”))を実行、a1[row.names(a1) != “[[LESS-THAN-1]]”,] で1回以上出てくる集合をゲット、さらにa3[row.names(a1) != “[[TOTAL-TOKENS-1]]”,]で数を数える。さらにt, distで距離を取って、cmdscale, kmeansを使い多次元尺度法にかける。すると指定した副詞、連体詞を含むような文章をグループ分けすることができる。

放送大学全科目感想 013 発達科学の先人たち(’16)

  • 心理と教育コース
  • ラジオ番組
  • 岩永雅也先生(放送大学学長・2021年~)
  • 星薫先生(放送大学准教授)

第1回

イントロ。聞き手は放送大学卒(実は慶應&早稲田卒でもる)のアナウンサー、二宮朋子さん。ツッコミが的確で鋭い。

発達とはdevelopmentを明治時代に訳した言葉で、「包みを解く」という意味がある。西洋では、もともと決定論が支配していて、すでに完成されているものを明らかにしていくという意味合いが強かった。現代ではそれを反省して、環境による効果も加味され、発達とは「内在と外在が相互作用して、変容していくこと」であるという定義に変わっている。

本講義は文献購読的な講義らしい。残りの14回は、それぞれ1人の思想家をフューチャーし、文献の引用も多数していただけるそうだ。楽しみ。

心理学と教育学の研究方法の違いにも言及があった。心理学は体系だっているが、教育学は体系がない。それが、○○心理学(発達心理学とか)という呼び方と、教育○○(教育工学とか)という呼び方の違いに影響しているらしい。

心理学で扱う人たちの概説。アリストテレス、ダーウィン、ブント、ダーウィン、ピアジェ、バートレット、土居健郎(どいたけお)。土居さんはよく名前を聞く。このうちアリストテレスとダーウィンは全然心理学ではないけれど、基礎を築いた人には違いないので言及するらしい。全体的には、意識は足し算である、要素に分解できるという派閥と、そうではなくてもっといろんなものが結び合わさっているという派閥の争いになるようだ。宮崎駿にも言及された。彼はこどもが独自の世界を持っている、大人と考え方や感じ方がそもそも違うのである、ということをわかっていて、作品には大人と子供の感じ方のギャップがよく表れているらしい。

教育学は時間がなく人を紹介して終わった。デュルケム、貝原益軒、シュタイナー、モンテッソーリ、アリエス、清水義弘。中には議論の分かれる人(シュタイナーとかモンテッソーリ)もいるらしいが、面白いので取り上げましたとのこと。なんかずいぶん対象を突き放したような人だ。

第2回

アリストテレスの「心とは何か」について。アリストテレスは心理学の基礎を築いたといわれる。といっても彼の興味の中の一分野にすきない。内容はもとより、「心」というものを取り出して研究対象にしたところがすごいと思う。我々はアリストテレスの作った枠の中で考えてるんだなあ。

アリストテレスは心身一元論をとり、心は最も価値があるものだとする。ギリシャの人たちって価値の上下を大事にするよね。私は価値の上下はあんまり好きじゃないんだけど、上下がないと秩序も生まれないってことなのかな。で、理性は一元論の中からはみ出した存在らしい。矛盾してるけど、永遠のものを考えたかったという気持ちが伝わってくる。永遠=最高、至上、だから理性を持つ人間も至上、人間第一主義ということなのかな。

第3回

貝原益軒について。一番心に響いたのは「そらに覚えざることは、用に立たず」ということ。覚えていないことは使えない・役に立たないってのは昔から言われているんだな。今後の訓示として受け取っておきます。とにかく覚えるまで繰り返そう。

九州男児らしく女の子の教育についてってところがあってうるせーと感じたが男文字もやれとか学もないといかんとか言ってるだけまだましという考え方もある(でも縫物やれとかうるさい)。女性の七難(子なしとか、離縁の理由になるらしい)ってひでーなそれ。一応これにも一部分異を唱えているらしい。

第4回

ダーウィン。もともと生物学に進む気はなく、親に医者になれとか言われて育ったらしいが、いやになって5年の研究の度にでてそのあと有名になったそうだ。進化論は当時キリスト教の禁忌に触れる感じだったので論文発表はすっげー後になった。

今回紹介された文章は人間の表情と心の関係についてのもので、種の起源より後に書かれてる。表情とその根拠となる心の描写が生き生きとしておもしろい。心理学自体がダーウィンの思想にベースを置くところがある。進化論が誤用された優生学の氾濫という負の歴史もあるので、心理学者はダーウィンに複雑な気持ちを抱いているらしい。

放送大学全科目感想 012 データ構造とプログラミング(’18)

  • テレビ科目
  • 情報コース
  • 鈴木一史先生(放送大学教授)
  • 難易度 ★★★☆☆
  • おすすめ度 ★★★☆☆

同じ鈴木先生の講座「アルゴリズムとプログラミング(’20)」の上位互換で、同講座と半分くらいかぶっている。アルプロと比べるとこちらの方が内容が高度で、C言語の程度も高いのだが、テレビ講座の利点を生かし切っておりこっちの方がわかりやすい。毎回動作確認を丁寧に行ってくれて好感度が高い。なお先生はにちゃんねらーでまどマギのファンと思われ、タイトルに関連AAが毎回ちりばめられている。

第1回

イントロと配列について。C言語はある程度知っていることが前提なので、同じ先生のアルゴリズムとプログラミング(’20)を履修してからの方がよいね。

C言語をwindowsで簡単にコンパイル・実行する環境って何があるのかなー。web上でやった方が速い気がする。

( ´∀`)モナーがいるんだけど。。先生にちゃんねらーじゃん。

テレビ科目で見やすいんだけど、windows3.1味のある古いグラフィックで洗練されてない。

配列ってなんで添え字0から始まるんだろうね。

C言語のrand()ってintの最大値までの値を返すのか。だからrand() % 100 みたいにしないとだめなのね。てっきり0~1の間なんだと思ってたけどそれだと不便だな。

構造体の配列。まあだいたいDBに対応する。固定長だけど。メモリ量が多くなってきたら、mallocで動的確保した方が無難とのこと。ヒープに確保できるので。

スライスって配列をぶった切る関数じゃないの?配列を拡張したものみたいに紹介がされている。

配列へのデータ挿入。最大n個のデータを移動しないといけないから計算量はオーダーnになる。削除も同様。つまり負荷が大きい。

データ探索について。線形探索はこれもオーダーn。二分探索は整列済みの配列に対して行わなければいけない制約があるが高速。図解してくれていてこれはわかりやすい。配列の場所としてlow, mid, hiの値を用意して、探索する値がmidと比べて大小どちらか確認、またlow, mid, hiを設定しなおす…の繰り返し。midにある要素と検索したい値が一致したら終了。

線形探索が遅いことを実践。30万件のデータを30万回検索すると当時の最新のCPUでも18秒。一方、二分探索だと0.02秒。ちなみに事前に要素をソートするqsortも0.029秒しかかかってない。

第2回

スタックについて。スタックと言えばお盆(食器の方)らしい。たしかにそうだね。

先生の手元が常に動いているのが気になる。

swap(頂上と2番目の値を取り換える)、duplicate(頂上のデータをコピーしてpush)って操作は知らなかった。

スタックの実際の実装方法。アルゴリズムとプログラミングの所でも習ったけど、ようやく映像で見られる。まず配列で実装する方法。添え字を保存しておけばOK。ただ配列サイズがいっぱいになる可能性がある。挿入も削除もオーダー1で高速。コード例も映像で見られるからいいな。

スタックを1億個使ってCore i7で動作実験。乱数発生も含めて1秒で終わった。高速ですね。

文字列データについて。Linuxには48万件程度の辞書データが入ってるらしい。文字データとしてこいつを使い、スタックに積む処理も高速で1秒だった。

スタックの応用について。まず文字列の反転。たしかにpopしてけば逆になるな。今後使ってみよう。それから逆ポーランド記法。78+(7+8と同じ)のように記述するやり方。どこまでが被演算子かわからないので、7 8 + のように区切りを入れる必要がある。処理方法としては、演算子が出てきたら2回popして計算してpushすればいいってわけ。楽だね。

3 4 + 5 * なら→3 4 をpushした後 + が出てきたから、3, 4 をpopしたあと3 + 4 = 7をpush。次に5をpushしたら * が出てきたから、7, 5をpopして、7 * 5 = 35を計算してpush。これで35が答えになる。逆ポーランド記法ではカッコがいらないことが特徴。

スタックはSTLに入ってますよって話もしてる。STLの場合、可変長になってるだろうから処理速度はどんくらいなんだろうね。

第3回

キューについて。タイトルにキュゥべえ出すなよ。。。先生。。。

キューの構造はわかってるからいいとして、実装が気になる。配列を途中から途中まで使うようなイメージなのか。だから先頭と末尾の添え字が必要。オーバーフローと空のチェックも必要。使っていけばすぐ配列の末尾に達するから、リングバッファ化するしかない。計算量はO(1)。はやい。

C言語のコード例、穴だらけ(MAXが小さいとかリングバッファになってないとか)なんだけど、教育用だから仕方ないか。。

enqueueを1億回やるテスト。1.2秒で終わった。バッファも1億個作ったのな。4バイト変数で4GBか。まあできなくはないか。

stdにもキューがある。queue<int>みたいな。ただ、メソッド名がpushとpopなのでスタックとまぎらわしい。

キューの応用。まず両端キュー。頭と後と両方で追加削除が可能。enqueとdequeueの意味が普通のキューと変わってくるのでわかりづらい。

優先度付きキュー。dequeueのときに、優先度の高いもの(値が小さい場合のことが多い)から取り出される。だからenqueueした順とは限らない。利用例としては、イベントの待ち行列、OSの割り込み、ダイクストラ法、ハフマンコードなど。なのでかなり大事な技術みたい。効率の良い実装が望まれる。配列(n)、順序配列(n)、ヒープ(logn)といった実装があるがヒープが一番効率がいい。配列だとdequeue、順序配列だとenqueueにコストがかかってしまう。

あれ、ヒープの実装はどうやるの?→第14回でやるみたい。

第4回

連結リストについて。汎用的なDBを作るのと同じなんだって。リスト自身が他の要素へのポインタを持ってることまでは把握してる。もしかしてDB自体が連結リストなのかな?

C言語依存の解説だけど、他言語でも実装方法は変えようがないから同じだよな。基本的な関数名は教えてくれるので親切。

ノード作成のコード、head->next->next->next->next->next = NULL とか糞コードに見えるけど意地でもポインタ変数を使わないためにはしょうがないのかな。

nullってナルって呼ぶのが最近の流行りなの?ヌルじゃないの?日本語読みだからダメ?

連結リストって都度メモリ確保してるけど、例えばC#のListなんかはこれ使ってるのかな?それとも配列型で、数が大きくなったらメモリ追加確保なのか?

ノード挿入。先頭、中間、末尾に挿入する場合の3パターンに処理が分かれる。先頭ならheadを更新、中間なら前のノードのnextを変更、末尾ならnextにNULLを入れないといけない。挿入は、メモリの並べ替えをやらなくていいから効率はよい。

実際のコード、毎回引数にheadを入れないといけないのか―。面倒だけどしょうがないか。XMLのオブジェクトが常にdocumentのポインタを必要とするのと一緒かな。

10万件でテスト。0.004秒で終わった。はやっ。ただこれは、全て先頭への挿入だったから。末尾だとどうなるか。12.6秒。毎回ノードを全部たどるから遅い。10万件でもけっこうきついね。そういえば以前、鉄道駅をノードにしてこれをたどりまくるJavaScriptのコードを書いたことがあるけど、遅かった。速くするための工夫がいろいろ必要になるんだな。

ノード1億個を先頭に挿入→4秒。1億ノードの末尾に1個だけ挿入→0.382秒。おそい。

ノード削除。これも先頭、中間、末尾で処理が変わる。先頭ならheadを変える。中間ならノードを繋ぎかえる。末尾なら1個前(これをgetするのが面倒そう)のnextをnullにする。で1個メモリを解放すればいいね。

10万件削除(先頭)の実行時間は0.006秒。楽勝ですね。

第5回

連結リストの応用。まず探索について。連結リストは基本的にシーケンシャルアクセスなので、オーダーはO(n)になる。整列はどうするか。整列済みリストに挿入するなら簡単で、リンクをたどりながらどこに挿入するか判定していけばいい。これもオーダーはO(n)。ソートアルゴリズムはマージソートっぽくなるらしい(要コード例)。

接続は単にnextと他のリストのheadを繋ぐだけだから簡単。マージも楽。分割も簡単。

連結リストでスタックを実装する。pushでheadに1個データを追加する、popでheadから1個データを取っていけばOK。簡単じゃん。計算量も両方ともO(1)。はやい。配列と同じ。しかも容量制限なし。

キューの実装。enquereは末尾に1個データを追加、dequereはhead1に1個データを追加でOK。これも簡単。enquereは末尾のポインタ取っとけばO(1)かな。とっとかないとO(n)だから遅い。実際、末尾まで全部サーチする場合のデータ削除は10万件で12.6秒もかかる。

コード、テレビの画面で見ても理解が難しいことを先生が認めている。そうか?わかりやすいと思うけどな。

連結リストから派生したデータ構造。双方向連結リストとか、環状連結リストとか。前のノードへのポインタを保持する双方向連結リストは、データ量は大きくなるが実装としては妥当な感じがする。便利。近代的プログラミング言語でも標準的らしい。stdでも<list>で提供されているらしい。C#のListも同じか?

環状連結リストはどういう場合に便利なのか謎。→OSのプロセススケジューリングで使われているらしい。たしかに、終わるまでずっと繰り返すような処理には向いてる。で、当然環状双方向連結リストも実現できる。これもどういう場合に使うんだろう。。

第6回

バイナリサーチツリー。ようやく実装方法が全然わからん奴が出てきた。

ツリーとは階層関係を表現するもの。数学的にはグラフの一種。ツリーはノードとエッジからなる。エッジはリンクと同じ。先頭ノードのことを節、vertexという。ツリーはベン図でも表現できる(!)。カッコでも表現できる(!)。例えばXMLもツリーだから、カッコとかベン図で書けるんだなあ。ノードのレベル(階層)はルートを0とする流儀と1とする流儀があるらしい。授業では0で定義。ノードが持つサブツリーのことを自由度という(なんで?)。

バイナリーツリーは子ノードの数を最大2個に制限したものをいう。日本語では二分木とか二進木とかいう。完全二分木は、最下層以外全部2個のノードをもっていて、かつレベルが全部同じ場合。で、バイナリサーチツリーは、左ノードの方が小さい、右ノードの方が小さい、というように配置したツリーのこと(別に完全二分木じゃなくていいみたい)。コード的には、左右ノードへのポインタを持っていればよい。

実装コード、左右に手動で挿入していくKUSOコードになっているが、挿入関数を作っていないからしょうがないか。

走査について。決まった規則で(全)ノードにアクセスすること。走査にもいろいろあって、行きがけ、通りがけ、帰りがけ走査がある(定義は略)。このうち通りがけ順操作は整列と同じ効果になる。どうにかしてバイナリサーチツリーを作ればソートできるってわけか。3つとも実装は簡単で、再帰呼び出しと出力の順番を変えるだけ。

最大値、最小値を求めること。簡単で、左ノードをたどれば最小値、右ノードをたどれば最大値になる。どちらもノード数が少なく、すぐ求められる。実装も楽勝。結局、バイナリサーチツリーを作るところが最大のポイントになるのでは?ノード数を数えるコードも簡単で、左右のノード数を再帰で数えて+1(自分の数)を返せばいい。ノード数は別にバイナリサーチツリーじゃなくてもよくて、ツリーなら何でも使えるね。高さを求めるコードも再帰で行ける。再帰ってかなり頭使うなぁ。

第7回

バイナリサーチツリーの操作について。探索と削除と挿入。探索は前回やったんじゃ?

探索はルートノードから値を比較して左右に辿っていけばOK。これは性質から明らかなんでそりゃそうだよね。ツリーにない値を探索しているかどうかは、末端まで行けばわかる。葉ノードまで到達しても値にヒットしなければ、該当なし。

挿入はまず探索から行う。葉ノードまで行ったら左右に挿入してやればいい。何もない場合からツリーを作るときは1番目のノードをルートにする。けど、これだと毎回ルートの取り方によって異なるツリーができない?どういうツリーにすれば効率的(レベルが浅くなる)になるんだろうね。

ノード削除について。削除は3通りの場合分けが必要になる。

  1. 葉ノードなら、単に消すだけでよい。
  2. 子ノードが1個ある場合、親ノードと子ノードを接続して自分は自滅する。
  3. 子ノードが2個ある場合。これが大変。inorder predecessor(順序内前任者、削除したい左側のサブツリーで最も右側にいるノード)を考える必要がある。通りがけ順走査では削除したいノードの一つ前のノード=ソートした時一つ前に来るノードを、これから削除するノードの所に入れてやる。これで順序を保てるというわけ。うわーコード大変そう。もう一つのパターンとしては、inorder succesor(順序内後継者、削除したい右側のサブツリーで最も左側にあるノード=ソート順で一つ少ないノード)を同様に、これから削除するノードの所に入れてもいい。それで削除ノードをdeleteする。これ、自分で思いつくかというと思いつかないなぁ。

コード例は印刷教材参照だって。そりゃそうだよなー。

バイナリサーチツリーの挿入順の話。整列してから挿入すると、単なる連結リストになりレベルが深くなってしまう。完全バイナリツリーだとツリーの高さはlog2(N+1)となり、高さに比べてノードをたくさん収納することができる。すると探索が楽。100万個でも高さはせいぜい20個。乱数を適当に挿入してもだいたいそうなる。ツリーの高さに計算量は比例するから、すべてO(logn)ということになる。ただ、形が悪いとO(n)になる。

じゃあいい感じの完全バイナリツリーに近いツリーを作るためにはどうするんだ、ってことが気になるけどそれは教えてもらえなかった。残念。ぱっと思いつくのは、だいたい中央に来る値からツリーに入れていけばいいんじゃないかってことくらいか。

第8回

ツリーの応用。平衡木とかいうのも説明するらしい。

まずはツリーの全ノード削除について。子が1-2個ある場合は削除が面倒なので、なるべく子が0個の場合(葉ノード)を削除したい。帰りがけ順走査をつかえばよい。コードとしては、左側にあるノードを優先して再帰で削除していくだけ。そうすると自動的に左側の葉ノードから消えてく。簡単!

メモリリークの話が出てきた。ちゃんと削除すればリークは起きないですねって言ってる(けど、最近の言語はみんなGCついてますよ!)

パス表示。すべてのパスを表示するためには、葉ノードを網羅してそこまでのパスを求めればよい。というわけで再帰的にノードを辿り、葉についた時点でパスを表示するとよい。

左右のノード反転。これも再帰的に左右反転関数を実行しまくるだけで終わり。コード短いでしょ!?って言ってる。

ツリーの高さの計算。サブツリーの高さを比較して+1して返す、これを再帰。この授業は再帰を勉強する科目なのかもしれない。

平衡木。やっと本丸に来た。葉ノードまでの高さをなるべく同じにするツリーのこと。AVLツリー、レッド・ブラックツリー、スプレイツリー、AAツリーなどいろいろあるらしい。ここではAVLツリーを見る。AVLツリーは、左右のノードの高さの差が必ず1以内になるらしい(どうやってやるんだ?)。

基本的に挿入・削除方法はバイナリサーチツリーとやり方は同じだが、挿入・削除後の処理が大変。でも見ていってくれるらしい。ルートからみて、高さが低いツリー、高さが高いツリーに挿入する場合、さらに高い方のツリーの左右のどちらに挿入するか、の場合分けが必要(以降は印刷教材を参照らしい。残念)。

実例。データ数を増やしていくと、ランダムの場合と高さがだいぶ違う。AVLツリーはランダムの場合の半分以下の高さになっているように見える。速度はAVLツリーの方が若干遅いがそこまでではない。ほぼランダムと同じ。でも計算量はlognに保たれる。いい感じのアルゴリズムだ。でも後処理が面倒らしい。実際どうなのか印刷教材が楽しみ。

第9回

ハッシュテーブルとオープンアドレスの話。

ハッシュ法は定数時間で速い。最速。本当なの!?そういえば配列のサイズとかってどうなってるんだろ。要はキーから算出したハッシュ値を配列に割り振ればいいんだよな。キーからの狭い配列に対する写像って感じ?ハッシュテーブルの配列数はバケットというらしい。

具体的なハッシュ関数について。ハッシュは切り刻むということ。一番簡単なのはmod。でもこれ10で割るんだったら、10までの配列にしか使えないよね?

ハッシュ値は衝突する。まず起こりにくくするには、配列を大きくしたり、演算を工夫したりする。演算の工夫、中央積算法。二乗して真ん中の方の値(6桁なら3-5桁目とか)をハッシュ値にする。折り畳み法。数字を分割して足し算して上から二桁とか必要な桁を取り出す。どっちにしても結局衝突は起きると思うけど。。?

衝突したらどうするか。その時の手段の一つがオープンアドレス法。空いてる配列を探すやり方のこと。具体的なやり方にはまず線形探索がある。+1していって空きを探す。簡単だが空きが連続して埋まるクラスターが発生してしまう。すると負荷がかかりやすい。

平方探索。再ハッシュ回数の定数倍とか再ハッシュ回数の2乗の定数倍とかを足して空きを探す。いい感じに見えるが、どれも同じ間隔の位置を探しちゃうから、セカンダリークラスタが発生する。

ダブルハッシング。ハッシュ関数を2つ用意し、片方は必ず足す、片方は再ハッシュ回数で掛ける。用意するハッシュ関数も工夫する。探査間隔が毎回変わるので、クラスタリングが避けられるというわけ。

ハッシュテーブルを実際に動かしてみる。データ数1億で、バケット数は2億、1.5億、1.1億とすると、1.1億は衝突がおきまくって遅いはず。実際、2.3倍くらいの速度差があった(思ったほどではない)。バイナリサーチツリー(o(logn))と比べるとすっごく高速。20倍速くらい。ただしメモリを食う。

第10回

ハッシュテーブルと連鎖法について。連鎖法とはハッシュテーブルの衝突解決のための手法の1つ。同一ハッシュ内のデータは連結リストにしてやればいいってわけ。(たぶん)メモリの使用量がかなり少なくなるが、衝突があると計算量は連結リストの計算量と等しくなるので、O(1)ではなくなるという欠点がある。

実装としては、ハッシュテーブル自体を連結リストの配列として実装する。で、ハッシュ値を格納するときに連結リストのノードを毎回確保して挿入していく。

実際計算量はどうなるのか。連結リストの長さL = データ数 / バケット数を考えると、計算量はO(1) + O(L/2) となる。バケット数が少ないほど、衝突が起きやすくなるので計算量はO(L)に近づく。バケット数と計算の速さはトレードオフというわけか。計算してみると、バケット数を1/100にすると、10倍の時間がかかった。

実装例、ハッシュテーブルの挿入に成功しているとなぜかエラーを返しているんだけどミス?

文字列データをハッシュテーブルのキーにする場合。まずK&R法。データをASCIIコードに変換してから全部足し算して、バケットの数で割り算すればハッシュ値になるというわけ。K&R本に載ってるんだってさー。djb法。左ビットシフトしながら足す(詳細はよくわからん)。ビットシフトがあるので、ハッシュ値はかなりでかい値になる。

コンピュータのメモリはだいぶ大きくなった(40年で100万倍)。なぜか光るメモリの紹介をされた。メモリが増えたのでハッシュテーブルで少々メモリを食っても速度の恩恵の方がでかいというわけ。

ハッシュ関数の応用として電子署名や改竄チェックのMD5、SHAなどがある。ほんの少しの改竄でもMD5は全然違う値になるので簡単にチェックができる。

ハッシュタグとは。# のことを井桁(いげた)記号とよぶ。米国ではナンバーサイン、パウンドサイン、欧州ではハッシュと呼ぶらしい。データ構造のハッシュとは関係ない(そうだったんか)。

第11回

再帰について。再帰と言えばマトリョーシカ人形。机に人形置いたまんま先生が話進めてる。

再帰コードは自分自身を呼び出して、毎回異なる(たしかに)引数を渡していくのが特徴。

簡単な例が階乗。20の階乗で243京になるらしい。コードは5行で終わり。ほぼほぼ return n * factorial(n-1); だけだしね。

再帰のコードは、まずwinding(再帰呼び出しが続くこと)が続き、terminate condition(終了条件)を満たしたら、、unwinding(もとの場所に戻っていくこと)の処理が行われて終わる、という捉え方をする。

フィボナッチ数。実質 return fibonacchi(n-1) + fibonacchi(n-2); だけ。再帰が2種類あるところがポイント。この再帰関数は廃棄されている計算結果が多く、無駄が多い。fibonacchi(30)を計算すると、400万回の関数コールが行われるらしい。じゃあどうやって効率化すればいいのかは示されなかった。

ユークリッドの互除法。本体は return gcd(y, x%y)); のみ。これはx, yの大小関係が考慮されてないけど大丈夫なんだろうか?

フラクタル図形への応用。フラクタル図形は自己相似になっているので再帰と相性が良い。POV-Rayというソフトが使いやすいらしい。例としてシェルピンスキー三角形をあげる。中点を結んだ正三角形をどんどん取り除いていくときれいな図形ができる。三次元のテトリックス図形というのもある。3Dでもそんなにコードの行数がいらない。メンガーのスポンジというのもある。同じことを立方体とか正方形でやればいい。

再帰とスタックについて。スタックを使うと再帰処理と同等の処理を扱うことができる。メモリが少ない時代はよく使われた。再帰は簡潔で数学的な記述もできるが、トレース(っていうかデバッグ)が難しい。バイナリサーチツリーの例をスタックにしてくれたがわかりづらい。コード量が増えたことだけがわかった。速度はどうなのか?

末尾再帰。実行する最後のステップが再帰になっていること。これをfor文に変えてやると、いろいろと節約できる。ちょっと例が分かりにくかったので、印刷教材で要復習。

第12回

ソーティングについて。さんざん他の講義でやったことだから、飛ばし気味に差分だけ学んでいこう。

ソートをやるためには必ず大小関係がないといけない。大小関係さえあれば昇順降順で並べ替えられる。

ソート前と同じキーの順序を変えない、安定ソートを実装するにはどうするのか。この講義では言及されず。バブルソート、挿入ソートは安定らしい。選択ソートは不安定。原理上安定になるかどうかで判定するしかないのか。

バブルソート10万件。O(n^2)だし時間かかるはず。12秒。厳しいね。ループ内がソート済みならなにもしない、という改良版バブルソートだと50%整列済みの配列を使って10.1秒。メモリ移動のコストを省くと2割くらいは速くなるのね。95%整列済みだと5秒。

選択ソート10万件は2.8秒。バブルソートよりはだいぶ速い。バブルソートはswapの回数が多いから遅いらしい。やはりメモリ内移動のコストはでかい。ただ、不安定ソートなのが悩みどころ。

挿入ソート、コード見ても何もわからん。困った。整列済みだと非常に速いのが特徴らしい。10万件でやはり2.73秒と速い。選択ソート並み。50%整列済みだと2.0秒、95%整列済みで0.262秒。とてもはやい。

古いPCと新しいPCでのソート時間の比較。先生の趣味のコーナーだな。99年のCeleron 300MHz vs 2017年のCore i7 2.8MHzを対決する。バブルソート10万件をおこなうと99年で315秒、2017年で15秒。22倍の差があった。ここで99年PCでクイックソートを行うと0.110秒。2017年PCよりずっとはやい。アルゴリズムによってこんなに差が出るのか。なお2017年PCでクイックソートをやると0.006秒。

第13回

ソートの応用。また他でやったアルゴリズムなので飛ばし気味で。

クイックソートは1960年にはもう作成されていたらしい。ホーア卿とか言う人が発明した。イギリス発祥なのか。分割統治アルゴリズムともいわれる。C言語のqsortはクイックソートの改良版(?)らしい。具体的にコード見てみたいね。クイックソート10万件の実験、0.009秒。はやい。1億件でも10秒で行ける。

クイックソートを2回行うこと。2回目は整列済み配列をさらにソートすることになる。どのような速度になるか。1回目は一瞬で終わるが、2回目は18.9秒。あれ、整列済みだと弱いのか??なんで???理由としては、ピボットの選択手法によっては再帰の深さがめっちゃ深くなってしまうかららしい。というわけで、ピボットの選択方法によって対策をすれば整列済みデータでも全然速くなる。

再帰ではなくスタック利用のクイックソートについて。メモリが少ない環境では利用価値がある。大変な感じのソースになるが印刷教材に載ってるのかな。

C言語のqsortを使うとソート済みでも30万件→0.01秒で終わる(未整列よりはやい)。

マージソート。まず配列を分割し、少しずつマージしていく。実装としては、マージ用の配列と同じ要領のtemp領域が必要なのが特徴。1億件も13秒で終わる。たぶん、配列の分割がlog回で済むからだろう。利点は配列の整列未整列に依存しないこと。安定ソートであること。欠点は、メモリコピーのせいで若干パフォーマンスが落ちること。実測でもクイックソート比で3割遅い。結局、実用ではクイックソート改良版が最強ということになる。

第14回

ヒープの話。ヒープとは、ツリーに基づくデータ構造のこと。ノードの挿入と削除を高速に行える。完全二分木である。葉の高さが同じか、左>右になっているもの。なんか今回先生飛ばしてるな。

最大ヒープ。親ノードの値が子ノードより大きいか等しいもの。最小ヒープもある。他にはフィボナッチヒープ、d-aryヒープなど。普通はバイナリヒープ(二分木のみ)を指す。

ノード挿入。まず最下段に追加、次にヒープ条件(最大とか)に従って値の交換を行う。ヒープ条件を満たしてなければ上段のノードと交換しまくっていけばいい。この時の計算量はo(logn)になる。交換の可能性は1/2と仮定できるので、正確には0.5 * logn。葉が多いから行える操作だ。

ノード削除。ルートノード削除を例にすると、まず葉ノードとルートノードを交換する。その後挿入と同じで、上から下に向かって交換を行っていけばいい。この際、どっちの子ノードと交換するかについての条件は不明。計算量はやっぱりo(logn)になる。

実際の実装では配列で行う。ルートが配列の1番目、レベル1が2,3番目、レベル2が4,5,6,7番目…などのように実装していけばいい。ダイレクトアクセスも可能にある。添え字kの左の子ノードは2k、右は2k+1、親ノードはk/2(切り捨て)で表現できる。なるほど!!添え字0からスタートでももちろんできて、左を2k+1、右を2k+2、親を(k-1)/2でやればいい。でも1からスタートした方がコストが少ないので、だいたいは1からスタートで実装しているらしい。

ヒープを利用したアルゴリズムの実装。まずは優先度付きキュー。ヒープで実装すればどれもo(logn)でいける。どうやって実装しているかは謎。印刷教材を見よってとこか。最大ヒープを使ってキューをenqueueの度に並べ替えれば、優先度の高い順に勝手に並べ替えられるってことなのかな。

ヒープソート。まず全部データをヒープに挿入して、ルートから最大値を取り出し(削除するってことか?)ヒープを再構成しながら挿入済み配列にデータを移していく。計算量はo(logn)が2回分。クイックソートよりはこの2回が効いてきて若干遅いが、整列済みかどうかに影響を受けない。あと、クイックソートと同じく不安定ソートであるのが欠点。10万件で0.009秒、1億件で82秒。クイックソートよりけっこうかかる(コードが適当だからかもだって)。

第15回

グラフの話。グラフとはノード同士をつなぎまくったデータ構造のこと。ツリーもグラフの一種である。

グラフ周りの用語について。頂点Vertex(ノード)と辺Edge(ポインタでリンクを張ることに相当)。辺の両端にある頂点は隣接しているという。ある頂点から別の頂点に至る連続する辺のことをパスという。パスは複数ありうる。

連結グラフと非連結グラフ。すべての頂点を行き来できれば連結で、分断されていれば非連結。輪になっていたら閉路グラフ。Cnと表記する。辺に方向性があるグラフを有向グラフという。

辺に重みをつけると重み付きグラフ。これはカーナビとか運賃でよく使う。完全グラフは全頂点間に辺があるもの。辺の数は計算できる。

コンピュータでどう表現するか。まず隣接リスト。a→b,c b→a,c c→a,b,d d→c みたいな感じ。有向グラフも重み付きグラフも表現可能。自己参照もOK。

隣接行列。辺があるかないかを二次元行列で表現。ちょっとテキストで書くのは無理。ピクロスみたいな感じ。容量が大きい。有向も行けるし重みは数字を大きくすればいいからいける。無向グラフなら三角行列で十分。

実装。行列の方が楽で探索時間も少ない。ただしメモリを食う。

グラフの密度について。密度が低いと隣接リストが、高いと隣接行列が有利。だいたいeの数がvの2乗に等しくなってくるとけっこう密度が高い。

コード例。ぜんぜんいみわからん。

グラフの探索。接続情報に基づいて全頂点をたどることをいう。まず深さ優先探索。頂点をたどって行って先に進めなくなったら後戻りする。未訪問の頂点を訪ねて、頂点をスタックにpush。進めなくなったらpop。C言語で300行くらいになる。大変。とりあえずスタック使うんだなってことだけがわかった。

幅優先探索。近くにある頂点を優先的に訪ねていく。キューで実装する。頂点に隣接する未訪問の頂点をenquere。未訪問の頂点がなければdequere。動作例を見て何となく意味は分かった。深さ優先探索より速そう。どういう欠点があるのかな。

放送大学全科目感想 011 統計学(’19)

  • 情報コース
  • ラジオ科目
  • 藤井良宜先生(宮崎大学教授)
  • 難易度 ★★★★☆
  • おすすめ度 ★★★☆☆

統計教育について研究している教授による統計学。数式をできるだけ少なくして、概念を掴んでもらうことを重視したという。扱う範囲は広範でそれなりに高度であるため、各分野を詰めていこうとすると結局それなりに数学が必要になる。数式が苦手な人にとってはそれなりに出てくる数式にひるみ、数学が好きな人にとっては物足りない授業になっているように感じる。

第1回

数Iの統計の復習をしつつ、統計学が何を目的とするのかを説明している。全体的な話が多くふわっとしていてびっくりするようなことはあまりないんだけど、どうも今後確率が重要になってくるらしい。個人的には数学的な内容を濃い目でやってほしい。

第2回

高校の確率論の復習。大学では全事象をΩで表すこと、∩はハット、∪はカップと読むことを覚えた。非常にやさしい解説で、初学者に良い。統計学的には、確率モデルをいかに作るべきかが大事、そしてモデルはあくまでもモデルであることを意識しないといけないことが大事のようだ。

第3回

確率分布について。数Bの確率論に加えて一部、積分表示の累積確率密度関数も扱う。さすがに印刷教材がないと苦しくなってきた。後半戦の離散型確率関数の平均や分散の考え方は何とか理解できた。できるだけわかりやすく説明してくださっており助かる。独立事象だと分散は和をとっても良いというのは忘れていた。式を使って証明してみたいものだ。

第4回

二項分布。最初の分布のところまでは、確か正規分布に近い形、真ん中の膨らんだ形になるんだなってとこまではイメージできたけど、信頼区間のあたりでだいぶついていけなくなった。この節で一番大事な式は E(X) = np かな。

第5回

多項分布モデル。変数の種類が多いと種類数の階乗で場合の数がかかってくるので、一気に分母が大きくなり、大変な計算量になることが分かった。あとχ二乗検定は独立か否かを調べる指数であること、帰無仮説→棄却の流れは、背理法に近いことがわかった。統計でもある関係が成り立つことを証明するのは難しいから、無いことを否定するって手法になるんだろうな。

第6回

ポアソン分布モデル。λとeの-λ乗を使って偶然発生する事象をモデル化する。二項分布を分割し、極限を取るとポアソン分布になる。つまり無限に細かい二項分布ってわけ。定義より平均はちょうどλ、分散はλ/nになる。わかりやすいね。

第7回

正規分布モデル。いままでのモデルがどれも離散的な値を取り扱うのに対して、正規分布は連続的な値を扱う(そうだったのか)。あれ、じゃあ試験の点数って離散的だから正規分布よりポアソン分布モデルの方がいいんじゃ。。?まあ仮定的に正規分布に従うってことでいいのかな。しかしいままでいろんな試験の点数分布を見てきたけど、正規分布には全然従ってないですよね。だから偏差値ってあくまで参考程度で、あんまりあてにならないのかもしれない。特に外れ値の場合なんかはそう。

第8回

正規分布モデルでの統計的推測。正直、ラジオ音声では片側検定・両側検定のところ以外ほとんどわからず。印刷教材で復習が必要。たぶん、標本が正規分布に従うと仮定して、そこから平均・分散を推定する際に、得られた値が妥当かどうかをカイ二乗検定を使って調べる、ってことなんだろうけど。。

第9回

正規分布モデル間の群間の比較について。t検定とは、複数の群間の平均に違いがあるかどうか調べること。結局それだけのことについていろんな式をごちゃごちゃやって、有意水準5%に達してるかどうかを見てるだけってことでいいのかな。エクセルだったら関数一発の所を、できるだけ数学的に正確に知りたい気持ちはあるが、大変そうだ。

第10回

回帰分析。ようやく馴染みのある話題になった。相関があるからと言って因果関係があるわけではないという有名な話も出てきた。平方和の偏微分=0を解くって書くんだったらせめて印刷教材では式を最後まで書いてほしいなー。すっきりしない。

第11回

重回帰分析。2以上の変数を使って統計を説明すること。モデルが複雑になればなるほど、いろんな罠が待ち受けている(多重共線性とか)。寄与率ってのは見かけだましの値にあることも多い。だいたい君はただの相関係数の二乗だ。相変わらず偏微分=0のところは参考文献参照と言って飛ばしている。本当の所、そこが知りたい。

第12回

モデル選択の話。変数増減法はコンピュータの発展で採用できるようになったが、手動だと単純に計算が無理に思える。最尤法も、素直な方法に見えるが、これを発展させたAICは、係数に2がついているところが全然意味わからん。

第13回

ロジスティック回帰分析。確率自体が変数によって変化する場合のグラフを考えるんだけど、式の形を見ても直観的にグラフの形が浮かんでこない。なんじゃこりゃ。0/1で表される二値の統計量に対して、Y=0である確率、=1である確率をlog(もしくはeの何乗か)を使って表すことができる、というところまではわかったが、、

第14回

主成分分析と因子分析。主成分分析は各変数の統計量への説明の度合いを按分してできるだけ少ない成分で統計量を説明できるようにすること。因子分析は、各変数の背景となる因子を定義して、各変数を因子を使って表現すること。似ているようで、発想が全然違うということが分かった。

第15回

全体の復習。本講義は数学的な説明をなるべく少なくして、概念を掴んでもらうことに重きを置いたという。でもテキストを見る限りだと、数式が中途半端に出現し、文系の人はつらくなるし、私のような人にはもうすこし厳密に話をしてほしいなあという感じがする。