Kerasを使ってwords embedding

### Embeddingとは?
自然言語処理におけるEmbeddingとは、「文や単語、文字など自然言語の構成要素に対して何らかの空間におけるベクトルを与えること」

There are various ways to vectorize text
– Words represented by each word as a vector
– Characters represented by each character as a vector
– N-grams of words/characters represented as a vector

### One-Hot Encoding
taking a vector of the length of the vocabulary with the entry for each word in the corpus

cities = ['London', 'Berlin', 'Berlin', 'New York', 'London']
print(cities)

$ python3 one-hot.py
[‘London’, ‘Berlin’, ‘Berlin’, ‘New York’, ‘London’]

label encode

from sklearn.preprocessing import LabelEncoder

cities = ['London', 'Berlin', 'Berlin', 'New York', 'London']

encoder = LabelEncoder()
city_labels = encoder.fit_transform(cities)
print(city_labels)

$ python3 one-hot.py
[1 0 0 2 1]

Using OneHotEncoder

from sklearn.preprocessing import LabelEncoder
from sklearn.preprocessing import OneHotEncoder

cities = ['London', 'Berlin', 'Berlin', 'New York', 'London']

encoder = LabelEncoder()
city_labels = encoder.fit_transform(cities)
encoder = OneHotEncoder(sparse=False)
city_labels = city_labels.reshape((5, 1))
array = encoder.fit_transform(city_labels)
print(array)

$ python3 one-hot.py
[[0. 1. 0.]
[1. 0. 0.]
[1. 0. 0.]
[0. 0. 1.]
[0. 1. 0.]]

### Word Embeddings
The word embeddings collect more information into fewer dimensions.
To map semantic meaning into a geometric space called embedding space.
famous e.g. “King – Man + Woman = Queen”

from keras.preprocessing.text import Tokenizer
// 省略
tokenizer = Tokenizer(num_words=5000)
tokenizer.fit_on_texts(sentences_train)

X_train = tokenizer.texts_to_sequences(sentences_train)
X_test = tokenizer.texts_to_sequences(sentences_test)

vocab_size = len(tokenizer.word_index) + 1 # adding 1 because of reserved 0 index

print(sentences_train[2])
print(X_train[2])

$ python3 split.py
Of all the dishes, the salmon was the best, but all were great.
[11, 43, 1, 171, 1, 283, 3, 1, 47, 26, 43, 24, 22]

for word in ['the', 'all', 'happy', 'sad']:
    print('{}: {}'.format(word, tokenizer.word_index[word]))

the: 1
all: 43
happy: 320
sad: 450

sklearnのCountVectorizerはwordのvector
kerasのTokenizerはwordのvalues

pad_sequences

from keras.preprocessing.sequence import pad_sequences

maxlen = 100

X_train = pad_sequences(X_train, padding='post', maxlen=maxlen)
X_test = pad_sequences(X_test, padding='post', maxlen=maxlen)

print(X_train[0, :])

$ python3 split.py
raise TypeError(“sparse matrix length is ambiguous; use getnnz()”
TypeError: sparse matrix length is ambiguous; use getnnz() or shape[0]

何やと。。。

[kernel]割り込み

効率のよい方法は、リクエストを送った後、より有益な他の仕事をしながら、 リクエストが完了した時点でデバイスから割り込みを受けるという方法
CPU の物理ピンのいくつかは、そのピンに電圧の変化が生じると、CPU の現在の処理が中断され、割り込みを処理をする特別なコードである割り込み処理コード(interrupt handling code)の実行が開始されるように設計されている
それらのピンのひとつはインターバルタイマーに接続され、千分の一秒ごとに割り込みを受けられるようになっていて、それ以外のピンが SCSI コントローラのような システム上の他のデバイスに接続されている
ハードウェア割り込みが発生すると、CPU は、現在実行中の命令の実行を停止し、 割り込み処理コードそのものか、あるいは割り込み処理コードへと分岐する命令のどちらかを含んだメモリ内のある場所へとジャンプ
割り込みに優先順位を付けているので優先順位の高い割り込みは起こり得る
Linux は、一群のポインタを使って、システムの割り込み処理ルーチンのアドレスを持つ各データ構造体を参照する

[kernel]マルチプロセッサ

物理メモリを共有して管理するメモリ共有型並列コンピューティング方式のこと
特定のCPUに非対称的に割り付けられた処理に依存することなく、全てのCPUに対して対称的、均一的に処理が割り付けられた並列処理方式
二つ目以降のCPUの起動は、一つ目のCPUがカーネル初期化関数(start_kernel関数)の一番最後に呼び出す関数 smp_init関数にて行われる
二つ目以降のCPU上で動作する初期化プロセスは処理が終了するとそのままアイドルプロセスへと変化する。その後は、スケジューラによりプロセスが割り当てらられるのを待ち続ける

[kernel]ネットワーク(TCP/IP)

IP:16.42.0.9

ネットワークアドレス:16.42
ホストアドレス:0.9

サブネットアドレス:16.42.0
ホストアドレス:9

IPアドレスはネットワーク管理者によって割り当てられる
16.42.0と16.42.1というようにサブネットを変える

IPアドレスはIPパケットに含まれている
送信元、送信先のIPはIPヘッダに含まれる
同一のIPサブネットのホスト間では直接IPパケットを送信できるが、それ以外はゲートウェイに送信

TCPはパケットの送受信のためにIPを使用する
IPアドレスだけでなく、アプリケーションのポート番号も指定しなければならない

### linuxのnetwork
Network Application: user
Socket Interface: BSD Socket, INET Sockets
Protocol Layer: TCP, UDP IP
Network Devices: PPP, SLIP, Ethernet

TCPパケットは番号付けされているので、送信されたデータが正しく受信されたか確認する

### BSD Socket Interface
UNIX, INET, AX25(アマチュア無線)、IPX、APPLETALK, X25
Soket type: Stream, Datagram, Raw, Reliable Delivered Messages, Sequenced Packets, Packet

### INET Sockets
インターネットアドレスファミリーをサポート
システムコールで新規ソケットを作成する際は、アドレスファミリ、ソケットタイプ、プロトコルに関する識別子を渡す

INET BSD ソケット上でコネクションを確立
ふたつのアプリケーション間で仮想サーキットを構築する
TCP セグメントには、コネクション情報、開始セグメントのシーケンス番号(sequence number)、接続を開始したホスト側が処理できるセグメントの最大サイズ(maximum segment size, MSS)、送信および受信の際のウィンドウサイズ(window size)、等が含まれる

待機(listen)状態のソケット上のaccept操作ルーチンは、その socket データ構造体から、新規のsocketデータ 構造体を複製

### IP層
socket buffer:ソケットバッファもしくは sk_buff を使用してプロトコル間やネットワークデバイスとの間でデータを受け渡し
head, data, tail, end
sk_buff: push, pull, put, trim

[kernel]ファイルシステム

記憶装置上のデータに対し、ファイルという形式を通し一貫したアクセス手順を提供、バイトストリーム
ファイルにiノードと呼ばれるデータ構造を割り当てて管理する
各iノードはそのファイルの属性やファイルの実体が置かれている2次記憶装置上のブロック番号などを管理している

目的のファイルのパス名を指定してシステムコールを発行すると、ファイル記述子と呼ばれるユニークな番号が返却される
ファイル記述子の0, 1, 2は特別なファイル記述子として扱う、標準入力、標準出力、標準エラー

ファイルアクセスを高速化するために、各種データをメモリ上にキャッシュする
ページキャッシュはファイルデータそのものをキャッシュ、先行読み出し機能も備えている

仮想ファイルシステム(VFS)をサポートしている
ext2, ext3, iso9660, nts, RPC

### ローカルファイルシステム
ローカルファイルシステムは、ホストに直結された2次記憶装置を利用するためのファイルシステム
Linux標準のファイルシステムExt2のほかに、さまざまなOSが利用しているファイルシステム形式にも対応

### ネットワークファイルシステム
ネットワークの先にある遠隔マシンが持つファイルシステムを、自ホストのローカルファイルシステムのように利用できる仕組

### 擬似ファイルシステム
記憶装置上にあるファイル以外のものを、さもファイルであるかのように見せかけるファイルシステム

### Linux標準ファイルシステムExt2
UNIXが誕生した当時のファイルシステムに、BSDのFFS(Fast File System)の考え方を一部取り込んだような構造

### ジャーナリングファイルシステムExt3
Ext2ファイルシステムにジャーナリングを付加したファイルシステム
耐故障性を高めることと、システムの異常終了後のファイルシステム復旧を高速化するために導入

### ブロック型デバイス
実際の入出力処理を行うのがブロック型デバイスドライバ

[kernel]ページング

Pagingとは記憶装置をページと呼ばれる小さな単位に分割して割り当てを行うアルゴリズム群であり、仮想記憶のベースとなる設計
論理メモリから物理メモリ空間への対応づけはページテーブルという構造体で実現する

kmalloc(), kfree()
カーネルが連続した物理メモリ領域を確保するために使用。物理メモリ上に連続した領域を確保することで、空間的局所性が得られ、TLBを最大限活用できるため高速
malloc(), vfree()

– 実メモリ管理
Buddyシステムは、隣り合った空き領域を結合し、より大きな空き領域を作り出そうとする
Slabアロケータは、フラグメントの発生を最小限に抑えることと、メモリキャッシュ利用効率を考慮したメモリ管理方式

– 仮想記憶
仮想空間の機能によって、物理的に分散したページを集めて、連続した仮想空間に割り付ける

尋常ではないな、勉強すればするほど、どんどん自信を失ってくわ。。。なんだこれは。。

[kernel]ネットワークドライバ

Linuxのデバイスには
– キャラクタデバイス: バイト単位のデータ通信
– ブロックデバイス: ブロック単位のデータ通信
– ネットワークデバイス: ブロック単位のデータ通信
L /dev以下にはマウントされない
L システムコールのインターフェースが異なる
L デバイスからも非同期的にカーネルアクセスが発生する

ネットワークドライバに最低限必要な機能は、デバイスの取得及び各種設定、パケット送信、パケット受信

$ dmesg | grep eth0
[ 1.390857] e1000 0000:00:03.0 eth0: (PCI:33MHz:32-bit) 02:43:0e:00:05:fc
[ 1.393083] e1000 0000:00:03.0 eth0: Intel(R) PRO/1000 Network Connection
[ 3.305024] e1000 0000:00:03.0 enp0s3: renamed from eth0

ん、eth0にe1000が当たってる?
$ modinfo e1000
filename: /lib/modules/4.15.0-101-generic/kernel/drivers/net/ethernet/intel/e1000/e1000.ko
version: 7.3.21-k8-NAPI
license: GPL
description: Intel(R) PRO/1000 Network Driver
author: Intel Corporation, srcversion: 10A45E43BF63AE653A22C94

デバイスファイルは/devにある
fd0 フロッピードライブ
fd1 フロッピードライブ
sda ハードディスク
sdb ハードディスク
sda1 最初のハードディスクの最初のパーティション
sdb7 2番目のハードディスクの7番目のパーティション
sr0 CD-ROM
sr1 CD-ROM
ttySO シリアルポート0
ttyS1 シリアルポート1
psaux PS/2 マウスデバイス
gpmdata 擬似デバイス
cdrom
mouse
null 書き込まれたものを全て消す
zero 無限に0を読み出せる

[kernel]システムコール

カーネルはハードウェアの提供する機能を全て利用できるが、それ以外のプログラムはハードウェアの機能の中で利用できないものがある。非特権モードで動作しているプログラムがカーネルに依頼する方法がシステムコール

e.g.
ネットワークを利用した通信、ファイル入出力、新しいプロセス生成、プロセス間通信、コンテナの生成など
fopen(), fclose(), fread(), fwrite()

システムコールの目的
– ハードウェアを操作するシンプルなインターフェイスの提供
– アプリケーションが安全かつセキュアにOSのリソースを利用できる

### アプリケーションがシステムコールを呼び出す仕組み
– 実行するシステムコールを指定する番号をレジスタにセット
– システムコールに引き渡す引数をレジスタにセット
– システムコールを発動するインストラクションを実行

.intel_syntax noprefix
.global main

main:
	push rbp
	mov rbp, rsp
	push 0xA216948 // hi
	mov rax, 1
	mov rdi, 1
	mov rsi, rsp
	mov rdx, 4
	syscall
	mov rsp, rbp
	pop rbp
	ret

$ gcc -o hi hi.s
$ ./hi
Hi!

x86-64
1. raxにsystem call numberをセット
-> 0 read, 1 write, 2 open, 57 fork
2. システムコールに渡したい引数をレジスタにセット
-> rdi, rsi, rdx, r10, r9, r8に引数を格納していく
3. syscallのインストラクションを呼び出す

[kernel]ページテーブル

page table
– OSの中の仮想記憶システムで仮想アドレスと物理アドレスを対応づけるために使われる
– 仮想アドレスはそれにアクセスするプロセスによって実行されるプログラムによって使われ、実際には物理アドレスはRAMサブシステム等のハードウェアによって使われる
– それぞれのプロセスのメモリは物理メモリの色々な領域に散らばっているか、HD等のストレージに移されている

アドレス空間は4Kiバイトに分割され、この塊をページという、物理メモリはフレームと呼ぶ
仮想記憶システムは、仮想アドレスを物理アドレスに変換することで、ページとフレームにマッピングする
TLBはページとフレームのマッピングを格納し、全体の性能を向上させる

CPU <-> MMU(page table) <-> Memory
※MMUはMemory Management Unit
仮想アドレスのうち、上位はMMUに変換し、下位はそのままメモリに送られる

$ objdump -f main

main: file format elf64-x86-64
architecture: i386:x86-64, flags 0x00000150:
HAS_SYMS, DYNAMIC, D_PAGED
start address 0x00000000000005a0

この、start address 0x00000000000005a0が仮想アドレス

### 物理メモリの構造
カーネルテキスト(カーネルの実行可能なコード領域)、カーネルデータ(カーネルが使用する変数領域)、ユーザページ

### 仮想記憶システム
アプリケーションがアクセスするアドレスは、 直接物理メモリのアドレスへ変換されずに、アドレス変換表を利用して、 間接的に物理メモリにアクセスする

静的領域とは、プログラム開始時にメモリに確保され、プログラムが終わるまで解放されないメモリ領域
局所領域とは、関数開始時にメモリに確保され、その関数の終了時に解放されるメモリ領域
ヒープ領域とは、上記の二つと異なり、確保するタイミングも解放されるタイミングも任意

[C言語]カーネル

Unix系では新しいプロセスはfork()により生成されexec()系の関数により新たなプログラムに書き換わる
プログラムを実行する為のライブラリ関数としてexeclp()やexecvp()などがある
execveシステムコールが発行されるとカーネルの仕事となる
– 実行ファイルを読み込み、仮想メモリ上にマッピングする
– argc/argv[]、BSSの初期化、環境変数の引き渡しなどを行う
– 実行ファイル上のエントリポイントから実行を開始する

※カーネルを読み込むには5年程度の技術と時間がかかる
カーネルの大部分はC言語で書かれているが、CPU固有の処理部分はアセンブラ言語で書かれている

## カーネルのディレクトリ
Documentation ドキュメント
arch アーキテクチャ依存
block ブロック入出力層
crypto 暗号化
drivers デバイス・ドライバ
firmware ファームウェア
fs VFS(Virtual File System)とファイル・システム
include カーネル用のヘッダ・ファイル
init 起動と初期化(initialization)
ipc プロセス間通信(interprocess communication)
kernel カーネルの中心部分
lib ヘルパ
mm メモリ管理(memory management)
net ネットワーク
samples サンプルコード
scripts カーネルのコンパイルに必要なスクリプト
security Lnux Security Module
sound サウンド・サブシステム
tools カーネル開発用のツール
usr 起動直後にユーザ空間で実行されるプログラム(initramfs)
virt 仮想化インフラ

C言語ではcrt(C RunTime startup)というアセンブリで記述されたプログラムが一番最初に実行される
OSの開発ではこのcrtを環境に合わせて用意する