journey of Froakie (ケロマツの旅路)

Introduction English ver 今日はヒープ構造について書きます。ヒープ構造はデータ構造の一種です。ちょうど大学の自主ゼミグループのセミナー合宿に参加させてもらい、そこでグラフ理論を勉強したので、メモをしておこうと思います。   slide  はこんなのを使いました。 Overview データ構造 二分木 ヒープ 実装 ヒープソート データ構造 ヒープ構造の前に、データ構造について、説明します。データ構造とは、データを保存する手法であります。データ構造は、そのデータについてどのような操作を行いたいかによって、最適なものを選ぶことになります。 ヒープ構造はプライオリティキューと呼ばれれるデータ構造を表す方法です。プライオリティキューで行いたい操作は以下の二つです。 データの追加 最小値の抽出 二分木 まず、グラフを定義します。E と V は集合とし、 $e \in E$、つまりEの要素をedge(枝)と呼びます。また、$v \in V$、つまりVの要素をnodeと呼びます。 g:E->V×V をEからV × Vへの写像とします。この時、.(E,V,g)をグラフを言います。 例えば、次のようなものがあります。 丸いのがそれぞれのnodeで、矢印がedgeになります。 各edgeに対して、始点v1と始点v2を対応させるのが写像gの役目です。 根付き木とは次のような木のことです。 これはnode1からnodeが二つずつどんどん派生していっています。 特に、次のような木を 二分木 といいます。 特徴は、ノードが上からなおかつ左から敷き詰められています。一番上のノードを根といいます。また、例えば2を基準にすると、1は2の親、4,5は2の子、3は2の兄弟、8,9,10,11,12は葉と呼ばれます。 ヒープ ヒープ構造はプライオリティキューを二分木で表現したものです。プライオリティキューでやりたいことは次のことでした。 データの追加 最小値の抽出 . では、どのようにこの二つの操作を実現するのでしょうか。 初めにデータの追加について説明します。 1. 二分木の最後に追加す...

Introduction 日本語 ver Today, I will write about heap structure. The heap structure is one of the data structure. My reason of studying heap structure is that I joined seminar of Ritsumeikan Univ. I used this  slide  in seminar of Ritsumeikan Univ. Overview data structure binary tree heap Implementation heap sort Data structure I will explain about data structure before explaining about heap. Data structure is how to keep data. Data structure is selected on the basis of operation which you want to.  Heap belong to data structure called priority queue. priority queue have purpose which  add data pick up minimum data (and remove)  Binary Tree Let, E and V are sets. The element $e \in E$ is called edge. The element $v \in V$ is called node. g:E->V×V is map to V × V from E. (E,V,g) is called graph. For example, The arrows are edge. The circles are node. This is expressed map. It is possible to go to node 3 from 1....

Introduction English ver 今日はMAP推定（事後確率最大化法）について書きました。MAP推定ではベイズの定理を使います。データが少ないとき、最尤推定の結果をあまり信用できない話は、最尤推定の時に書きました。この時、MAP推定では自分の事前に持っている情報を取り入れることができます。 概要 ベイズの定理 MAP推定 共役分布 MAP推定の例 ベイズの定理 ベイズの定理は $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ です。 ただし、 $P(A|B)$ はBが起こった時のAの起こる確率です。 詳しくは  http://takutori.blogspot.com/2018/04/bayes-theorem.html  を見てください。 Map推定 MAP推定ではベイズの定理を使います。MAP推定は事後確率が最大になるようなパラメータを選びます。 いま、$x_1,x_2,...,x_n$というデータを$\theta$というパラメータを持つ分布から得られたとする。この時$P(\theta|x_1,x_2,...,x_n)$を求めたい。 ここで、ベイズの定理を使う。 $$P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}$$ ここで、$P(\theta)$は$\theta$の事前分布である。 $x_1,x_2,...,x_n$はそれぞれ独立であるので、 $$P(x_1,x_2,...,x_n | \theta ) = \Pi_{i=1}^n P(x_i|\theta)$$. よって、マップ推定は $$\theta^{\star} = \arg \max_{\theta} \frac{\Pi_{i=1}^n P(x_i|\theta) P(\theta)}{P(x_1,x_2,...,x_n)}$$ となる。 $P(x_1,x_2,...,x_n)$という値は$\theta$には依存しない。よって、定数であり、最適化に定数は関係ないので、排除すると、MAP推定は次のようになる。 $$\th...

Introduction 日本語 ver Today, I will explain MAP estimation(maximum a posteriori estimation). MAP estimation is used Bayes' thorem. If sample data is few, we can not belive value by Maximum likelihood estimation. Then, MAP estimation is enable to include our sense.  Overveiw Bayes' theorem MAP estimation Conjugate distribution Bayes' theorem  Bayes' theorem is $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ $P(A|B)$ is Probability when B occur. Please go on  http://takutori.blogspot.com/2018/04/bayes-theorem.html to know detail of Bayes' theorem. Map estimation Map estimation is used Bayes' theorem. Map estimation estimate parameter of population by maximuzing posterior probability. Now, suppoce we get data $x_1,x_2,...,x_n$ from population which have parameter $\theta$. Then, we want to $P(\theta|x_1,x_2,...,x_n)$. Here, we use Bayes' theorem. $$P(\theta|x_1,x_2,...,x_n) = \frac{P(x_1,x_2,...,x_n | \theta ) P(\theta)}{P(x_1,x_2,...,x_n)}...

問題 English ver 次のようなクエ リーをプロシージャーの中で使いたかった。 SET @user_variable = FLOOR(RAND()*10); INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET @user_variable; これはランダムに行を入れ替えたテーブルの上から@user_variable番目の行のcolumns_nameに1を入れることをしたかった。しかし、うまくいかなかった。その原因はLIMITやOFFSETは後ろにユーザー変数を持ってこれないことにあった。 解決法 次のようにするとうまくいく。 SET @user_variable = FLOOR(RAND()*10); PREPARE SET_STMT FROM 'INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET ?;';  EXECUTE SET_STMT USING @user_variable; 結論、やりたい操作を''で囲って上のようなことを書けばLIMITでもOFFSETでもうまくいく。 Reference http://techtipshoge.blogspot.com/2011/10/limit.html

Problem 日本語 ver I want to use this query in PROCEDURE. SET @user_variable = FLOOR(RAND()*10); INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET @user_variable; This query want to substitute 1 for the @user_variable 'th line of columns_name, but this query does not work. A cause is that LIMIT and OFFSET does not user variable. Solution SET @user_variable = FLOOR(RAND()*10); PREPARE SET_STMT FROM 'INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET ?;';  EXECUTE SET_STMT USING @user_variable; Conclusion, if you want to use user variable with LIMIT or OFFSET, use PREPARE STATMENT. Reference http://techtipshoge.blogspot.com/2011/10/limit.html

Introduction English ver 今日は写像の連続性の定義を位相を用いて行います。 こちらの記事 では位相の定義、開集合、開集合が位相の公理を満たすことを示しました。しかし、写像の連続性の定義は行いませんでした。この記事ではそれをやっていきます。重要なことであり、証明を書きます。 概要  開集合 $\epsilon-\delta$論法 開集合による写像の連続性の定義 同値の証明 開集合 (X,d)を距離空間とします。 $A \subset X$:開集合 $$\iff$$ $$\forall x \in A,~~\exists \epsilon > 0, ~~s.t.~~ B(x,\epsilon) \subset A$$ ここで、$$B(x,\epsilon):= \{y\in A| d(x,y) < \epsilon\}$$ この定義は位相の公理を満たすので位相として距離空間に入れることができます。そのことは前回の記事で書きました。 $\epsilon-\delta$ 論法 $\epsilon-\delta$論法について確認します。この論法は学部一年生で習うと思います。 f:X-> Y:写像で、 fが$x=x_0$で連続とは $$\iff$$ $$\lim_{x \rightarrow x_0} f(x) = f(x_0)$$ $$\iff$$ $$\forall \epsilon > 0,~~\exists \delta >0 ~~s.t~~ d(x,x_0) < \delta \implies d(f(x),f(x_0)) < \epsilon $$ 開集合を用いた写像の連続性の定義 Define1.0 $(X,\mathbb{O}_X),(Y,\mathbb{O}_Y)$を位相空間とします。 $f:X \rightarrow Y$が$x=x_0$で連続 $$\iff$$ $$f(x_0) \in \forall V:\textrm{open set} \subset Y~~,f^{-1} (V) \subset X ~~\textrm{is open set}$$ ここで、$\mathbb{O_X}...