マツシタのお勉強

【Deep Learningのお勉強 #1 】パーセプトロンとはなんぞや

はじめに

『ゼロから作るDeep Learning』という本を読み、得た知識などをメモとしてを書き記す。 また、この記事はパーセプトロンというアルゴリズムについてまとめる。 どうやら、パーセプトロンというものは、ディープラーニングの起源となるアルゴリズムらしく、パーセプトロンの仕組みを学ぶことは、ディープラーニングを理解する上で重要らしい。

パーセプトロンとは

パーセプトロンとは、複数の信号を入力として受け取り、1つの信号を出力するもの。 パーセプトロンはよく以下のような図で説明される。

f:id:atiek1121:20170414155521p:plain

上の図の中のx1, x2は入力信号であり、yは出力信号となる。また、w1, w2は重みを表している。 また、それぞれの◯は「ニューロン」と呼ぶ。

パーセプトロンの計算方法

上の図のように、入力信号がニューロンの送られる際に、「重み」が乗算されて、x1の入力信号が送られる時の値はx1*w1となる。また、入力信号は複数あるので、ニューロンyは全ての入力信号の総和を計算し、x1*w1 + x2*w2となる。この総和がある限界値θを超えた場合、yは出力として1を出す。

このように、「複数の信号を受け取り重み付けされた値の総和」が「限界値」を超えた時に値を出力することを「ニューロンが発火する」と表現する。

またパーセプトロンの出力信号は1か0の2値であり、限界値はθとして表す。よって上記の例では以下のような式でパーセプトロンを表現することができる。

パーセプトロンの「重み」とは

パーセプトロンの入力信号はそれぞれ固有の重みを持っている。この重みは、それぞれの入力信号の重要性をコントロールする要素として働く。

重みが大きければ大きいほど、それに対応する入力信号の重要性が高くなるということ。

パーセプトロンの「バイアス(限界値)」とは

上に登場した式を見るとθという限界値が存在し、入力信号を計算した値がこの値を境界にして出力の内容を決めている。

このθは- bと置き換え、バイアスと呼ぶこともある。θ = - bとすると上記の式は以下のように書くことができる。

こうすることで左辺を0にでき、単純になる。

重みwの働きは信号の重要性をコントロールすることだったが、バイアスの働きは、発火のしやすさをコントロールする。

機械学習でいう「学習」とは、この重みやバイアスをコンピュータで自動で行わせ、適切なパラメータを決める作業である。人が行うことは、パーセプトロンの構造を考え、コンピュータに学習データを与える事になる。

最後に

パーセプトロンの概念はなんとなく分かってきたが、このモデルが機械学習にどう活かされていくのかはもう少しお勉強が必要そうだ。

【グラフ理論とネットワーク理論】Graph #1

グラフとは何か

グラフは以下のコンポーネントで成り立つ。

  • 節点、頂点: 対象物(スイッチ、ルータ)
    Node, Vertex: Objectives(Switch, Router)

  • 枝、辺: 接点間の関係(伝送路)
    Branch, Edge: Relation among nodes(Transmission lines)

つまり、グラフとは節点と枝によって構成される。

グラフには既に名前が付けられているものがある。

・空グラフ Empty graph: ノードだけでエッジを持たない。
・完全グラフ Complete graph: 全てのノード間にエッジを持っている。
・補グラフ Complement graph: 元のグラフを補完するグラフ。元のグラフと補グラフを足すと完全グラフとなる。

グラフの性質

・同形 Isomorphic: あるグラフと同じグラフ。接点数、枝数、関係性も同じなグラフ。
・平面グラフ Plane graph: どの辺同士も交差しないグラフ。
・非平面グラフ Non-plane graph: どんな同形も枝同士の交差を生んでしまうグラフ。
・有向グラフ Directed graph: 辺に向きがあるグラフ。
・無向グラフ Undirected graph: 辺に向きが無いグラフ。

経路と連結性 Path and Connectivity

経路、連結は以下のように定義されている。

  • 経路、道: 始点Vsから終点Vtに至る枝の系列
    Route, Path: Series of branches from source Vs to sink Vt
  • 連結: VsからVtに経路がある
    Connected: There is a route from Vs to Vt
  • 強度に連結 Strongly connected: Vs→Vt、Vt→Vs

グラフ理論における経路、連結性に関する性質

・連結グラフ: すべての節点が他のどの節点とも連結しているグラフ
 Connected graph: Every node is connected to any other node.
オイラー線: グラフの全ての枝を通る一筆書きの閉路
 Euler line: Loop drawn with a single stroke of the brush.
オイラーグラフ: オイラー線が存在するグラフ
 Euler graph: Graph which has an Euler line.
・局所次数: 節点に付いている枝の数
 Local degree: The number of branches of a node

グラフ理論における定理(教養として)

グラフがオイラーグラフであるための必要十分条件は、すべての節点の局所次数が偶数であることである。

木とカットセット Tree and Cutset

木とは以下のようの定義されている。

  • 木: 閉路を持たない連結グラフ
    Tree: Connected graph without loops

木の性質

・木は枝数が最も少ない:
 今の状態から枝を足そうとすると閉路ができてしまい、木ではなくなる。
・覆う:
 元のグラフをGとし、Gからできる木をTとした時に、TはGを覆うと言う。
 通信網を作る時に始めはTの状態からスタートさせ、トラフィックが増えるにつれてGの状態にしていく。

カットセットとは

あるグラフGを2つに分けて見た時(それぞれをサブグラフV1、V2とすると)、V1とV2を繋ぐ辺のセットをカットセットと呼ぶ。例としては、島が2つあり、それぞれの島にはグラフ(ネットワークなど)が形成されてる状態を考える。この時、2つの島を繋ぐ辺の事をカットセットと呼ぶ。生命線のようなもの。

木とカットセットに関する定理

Gを覆うTは、Gのあらゆるカットセットと少なくとも1本の共通な枝を持っている。

AtCoder ARC 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

B - 2点間距離の最大と最小 ( Maximum and Minimum )

B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest 004 | AtCoder

N + 1個(0 ~ N)点がx,y平面上にある時、i番目の点とi+1番目の点との距離が与えられる(0 <= i < N)。 この時、0番目の点とN番目の点の距離で取り得る最大の距離と最小の距離を出力する問題。

解法

最大距離

最大距離は与えられた各点の距離を全て足し合わせることで取得することができる。この時、与えられた点は全て一直線上に存在することになる。

最小距離

与えられた点の内0番目とN番目を除いた点で上手く直線を折ることで、0番目とN番目の距離を短くすることができる。 なので、どのように直線を折るかを考える。

与えられた点と点の距離の中で最も長い距離を見つけ、その線分の両サイドの点で直線を折り返す。これによって0番目とN番目の距離を最小にすることができる。

ソースコード

AtCoder ARC 004 A - 2点間距離の最大値 ( The longest distance )

A - 2点間距離の最大値 ( The longest distance )

A: 2点間距離の最大値 ( The longest distance ) - AtCoder Regular Contest 004 | AtCoder

N個のx,y座標が与えられ、任意の2つの点の距離が最大となる値を出力する問題

解法

与えられる点の数がN(2 <= N <= 100)なので、任意の2点を全列挙すると計算量はO(104)となり、問題なく間に合う。 任意の2点を決めたら、三平方の定理により2点間の距離を算出し、最大となる値を出力する。

ソースコード

HimotokiとAPIKitでAPIクライアント

APIKitとは

GitHub - ishkawa/APIKit: Type-safe networking abstraction layer that associates request type with response type.

Himotokiとは

GitHub - ikesyo/Himotoki: A type-safe JSON decoding library purely written in Swift

単一のモデルをデコード

Requestプロトコル継承したGithubRequestを作成・Extension。

リクエストを生成するためのStructを定義

リクエスト実行

ポイント

通常のAPIKitの使い方では、リクエストを生成するための構造体にresponseメソットを定義する。 しかし、Himotokiを使うことで、responseメソッドの処理もGithubRequestプロトコルをExtensionする形で実装させることができる。 こりによりよりコードがシンプルになる。

コードだけみるとRateLimit構造体のdecodeが呼ばれていないように見えるが、

これのメソッドを呼ぶと内部的にT.decodeを読んでいる。

Himotokiのカスタムオペレータ

Himotokiのdecodeメソッドを見ると<|という謎のメソッドが使われている。これはカスタムオペレータといういうもので、+-といったようなオペレータを独自で定義する方法である。Himotokiのソースコードを見ると以下のように定義されている。

<|の左側に記述したものが上のメソッドの第一引数で右側に記述したものが第2引数となる。

複数のモデルをデコード

以下の例は、Github上のリポジトリーを検索し複数のリポジトリーの情報をレスポンスとして返すようなものである。

先程の例と同様に、typealiasに指定したモデル(今回でいうとRepositoryCollection)のdecodeが内部的に呼ばれる。 さらに、RepositoryCollectionをdecodeする過程で子モデルであるRepositoryモデルのdecodeも呼ばれるので、結果的にモデル配列をdecodeすることができる。

サンプルプロジェクト

github.com

ネットワークの仮想化

ポートベースVLANとタグベースVLAN

VLANとは、物理的にには1つのネットワークを理論的に複数のネットワークに分ける技術。

営業部が入居するオフィスに、経理部も同居することになった時、LAN配線は既存のもの使いながら、営業部と経理部とであたかも別の2つのLANがあるかのように使う事ができる。

これを実現する技術として、ポートベースVLANタグベースVLANがある。

ポートベースVLAN

スイッチやルーターに搭載されている複数のポートのうち、いくつかをグループとして指定し、そのグループに属するポート郡を独立した1つのLANのように見せる技術。

タグベースVLAN

1つのLANケーブルの中に複数のLANの情報を流す技術。 ポートベースVLANによって複数のLANを同じネットワーク内に作ることができるが、物理的にはLANケーブルは1つである。そこで、LANケーブルに流す情報にどのLANかを示すタグを付けることで、複数のLANを識別することがでる。


VPNとトンネル

VPN(Virtual Private Network)とは、インターネットなどの既存のネットワークの中に、新たに仮想的なネットワークを作る技術。

トンネル技術と認証

トンネルとは、ある通信回線の中に作り出した、仮想的な通信回線の事。

VPNにはインターネットのような安全性が保証されないネットワーク何に作るので、暗号化をする必要がある。この時IPsecなどのプロトコルを使用する。


仮想化

仮想化とは、物理的なネットワークやコンピュータを使って、論理的にネットワークやコンピュータを作り出す技術

仮想化によって物理的に1つのネットワークを論理的に複数のネットワークを作り出したり、その逆を行うことができる。例としてはVLANやVPNも当てはまる。

VALN: 物理的には1つのLANの中に、仮想的に複数のLANを作り出すこと。 VPN: 物理的には1つのLANケーブルの中に、仮想的に複数のLANケーブルを作り出すこと。

仮想化のメリット

  • 物理的な装置の数や場所に制約されず機能を利用出来ること
  • 装置の処理能力を有効活用できること(持っている能力を持て余していることが多い)
  • 必要に応じてスケールアップ/ダウン出来ること


クラウド

クラウドとは、ユーザ自身が、Web画面などを返して、コンピューター、ネットワーク、各種サービスを自由に組合せて必要なシステムやサービスを組み立て、それをネットワーク経由で利用できること。