迷途塵世的書僮筆記: 10月 2016

2016年10月31日星期一

2016年10月30日星期日

Algorithm hw#6

hw1	hw2	hw3	hw4	hw5	hw6
70	100	100	100	85	?

只要集滿7次100分~~從此作業就可以不用交~~就行了吧!

那我還差4次

這次hw6感謝有人神救援~~~寫得飛快

Prob 8.3
Ex 9.3.8

2016年10月29日星期六

Machine Learning hw#1

due day延到10/30

PRML全書電子檔
hw1 題目

hand-in solution:
hw1 prob3&4 report (程式題)

code:
1. Prob3 without sklearn (hand-in)
2. Prob4 without sklearn (hand-in)
3. Prob3 with sklearn
4. Prob4 with sklearn

- - -

Q: python的套件sklearn是可以使用的嗎?
A:

不知道妳要用sklearn哪部分，但不能直接使用 sklearn 的 regression 功能，基本上 model 建立部份禁止使用，若像 load data format 之類（etc. Scipy.loadmat() )功能話，則可以使用。
TA

- - -

本次作業因為一開始不知道sklearn能不能用
兩種版本都寫了

所謂的without sklearn (sklearn是一種toolkit)
指的就是"直接用數學式子"算出機器學習的答案
這個過程然比較折磨

這次作業的程式題我總共重寫三次, 修修改改一個禮拜
我一開始是without sklearn寫了一個版本
後來遇到瓶頸, 寫不下去
覺得需要用sklearn先知道答案,
就用sklearn再寫一次 (code當然簡潔很多)
原本打算就這樣交了
後來知道sklearn不被允許使用
又回過頭去再改成without sklearn的版本

最後的答案with和without sklearn的有一點點小誤差
不過還算可以接受

3-2題原本在sklearn裡可以用Lasso求解
without sklearn的情況下, 就只好照著題目的描述, 不加regularization項
而只是單純針對各attribute求算RMS, 再取最小的

比較奇怪的是,
兩種做法我都有將weight function列出來,
|weight|較大的基底函數也嘗試列出來
但是with和without sklearn的結果似乎都不相同?

總之是很紮實的一份作業, 有應用, 有推導
也加深了我對課堂內容的吸收和了解

2016年10月27日星期四

2016/10/28 Machine Learning

今天上完chap3 + ch4-1
期中考應該考到第四章

2016/10/28 Algorithm

今天開始上ch16 Greedy
Greedy和DP有重複的條件, 就是必須具有overlapping subproblem
但Greedy多加一條, 必須滿足Greedy property,也就是取的ak必須是local optimal
介紹了像是背包問題等範例

發回hw5

11:00~11:30 助教講解 (record)
講了個秤重問題, DP的應用

期中考考到ch16

2016/10/27 Formal Language

花了一小時複習上一堂課的內容
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

- - -

Parsing and Ambiguity [ pdf ] HW5.2 [ pdf ]

Context-Free Grammars and Programming Languages (Skipped)

Chap 6 Simplification of Context-Free Grammars and Normal Forms

Methods for Transforming Grammars [ pdf ] HW6.1 [ pdf ]

- - -

參考網址: http://www.csie.ntnu.edu.tw/~u91029/Language.html
發現這網址不錯, 講得蠻細的!

- - -

ch 5-1

Parsing: 判斷一個string是不是屬於一個Grammar

題型: 給一個Grammar, 寫出Language的表示方式
一套 Language 可以設計許多種不同的 Grammar 。
Grammar 理論上必須剛好生成 Language 之內的所有字串、永不生成 Language 以外的所有字串。

Left/Right-most derivation: 最左/右邊的variable先做
Derivation(Parse) Tree:

First node should be root(S)

every leaf should be terminal.(a,b...)

every internal node should be variable(A,B...)

leaf can allow variable

Partial Derivation Tree:

sub-tree of Derivation Tree

- - -

ch 5-2

s-grammar: 滿足A->ax形式, 且任何(A,a)pair都只出現一次的grammar

參考 : http://cs.stackexchange.com/questions/1958/relation-between-simple-and-regular-grammars
A Simple Grammar (s-grammar) is one in which every production is of the form $A \to a B_{1} B_{2} . . . B_{n}$ where $a$ is a terminal and all $B_{i}, i \geq 0$ are non-terminals, and there is only one production with any pair $⟨ A, a ⟩$ .

Ambiguous

我們可以「剖析 Parse 」一個字串，逐字對應至 Grammar 、確立語法，進而判斷原本字串是不是 Language 當中的字串。
字串對應到文法時，有兩種以上的對應方式，那麼此文法就稱作「曖昧文法 Ambiguous Grammar 」。

- - -

Formal Language 四大類型

Regular Language
Context-free Language: 一個上下文無關文法，有許多條衍生規則。規則裡面是符號、字元、箭頭。「上下文無關」是指符號不會連帶上下文一起衍生。也就是每條規則的左式，只有一個符號，而不會連帶其他符號和字元。
Context-sensitive Language
Unrestricted Language

四種語言規律，由規律嚴謹到規律寬鬆排列，前者是後者的特例。

其中 Regular Language 與 Context-free Language ，由於規律十分嚴謹，所以得以設計效率極高的演算法、擁有實務價值。

例如 Regular Language 用於字串匹配、用於驗證字串格式。例如 Context-free Language 用於設計程式語言、用於檢索網頁資料。

- - -

2016年10月25日星期二

2016/10/26 Algorithm

今天上完ch15 DP，
並介紹幾個應用範例，包括rod cutting等。
DP是一種由小到大逐步解問題的bottom-up方法，剛好跟recursive的top-down概念相反。
DP問題在數學上可以化成DAG圖找最大最小路俓的問題來解。

老師似乎很討厭人家上課用手機。但我們連meeting都在滑了，現在這個時代實在很難脫離這些電子設備的，我是覺得沒有這麼嚴重。不過認真說起來，他的課確實設計精良，有認真上課的話也很難分心。看來我也不該在上課時用筆電了。

2016年10月24日星期一

2016/10/24 Pervasive Computing

今天介紹了好幾篇paper
講得很雜, 我也有點不知道該怎麼整理@@"

2016年10月23日星期日

<改變世界的九大演算法> 心得

原文作者：John MacCormick
譯者：陳正芬
出版社：經濟新潮社
出版日期：2014/08/07

這本書我借了快兩個月，有一頁沒一頁的看，然後終於被催還了。XDD

這本算是資訊領域很好的科普書。它提到的演算法都是每天被普羅大眾所使用、解決真實世界的具體問題的偉大演算法。書裡用深入淺出的例子，說明這些演算法運作的原理。

那它選了哪九大演算法呢？

1. Text indexing (ch2)
2. PageRank (ch3)
3. 公鑰加密 (ch4)
4. 錯誤更正碼 (ch5)
5. Pattern Recognition (ch6)
6. 資料壓縮(ch7)
7. 資料庫transaction(ch8)
8. 數位簽章(ch9)
9. 如果存在會很了不起的演算法XD

- - -

以下為個別介紹：

1. Text indexing (ch2)
這是搜尋引擎相關的演算法。
(1) Word-location trick：存網頁中每個字的位置，就可以運用位置的鄰近與否，來判斷搜尋的相關性。
(2) 元詞技法：在標題的文字，權重提高，來判斷搜尋的相關性。

2. PageRank (ch3)
這是也搜尋引擎相關的演算法。
PageRank是Google引擎當初之所以能打敗其他搜尋引擎、獨領風騷的原因。它運用的是超連結技法，把一個網站的超連結視為投票，被投票越多的網站權重越高，而權重越高的網站投出去的票越有價值。整個系統可以用矩陣相乘算到一個平衡結果。
但是整個網頁相連的結構很大，算page rank耗時很久，這時採用random walk技法可以得到近似結果。

3. 公鑰加密 (ch4)
這是資安相關的演算法。裡面提到我們要如何透過公開的網路進行秘密通訊。主要技法是採用一個公開的公鑰，雙方各自利用公鑰將自己的訊息處理後公開，取得對方的資訊後，利用對方的資訊再處理自己的資訊。藉由不可逆的運算過程，雙方最後會得到相同的結果。
例: 公鑰basis=2,clock=11, 我:8, 對方: 9
我: (2^8) mod 11 = 3
對方: (2^9) mod 11 = 6
我公開3, 對方公開6
我: (6^8) mod 11 = 4
對方: (3^9) mod 11 = 4
兩人會得到相同的數字4
這是由於11是質數，對2^n其餘數有循環性。這就是為什麼數學上要不斷尋找更大的質數，因為質數越大，加密效果越好。

4. 錯誤更正碼 (ch5)
可靠度相關演算法。就像我們的銀行帳戶或身分證都有最後一碼檢查碼, 錯誤更正是指藉由"重複"或"冗餘"來進行錯誤檢查。其中的"漢明碼"就是一種錯誤更正碼的編碼方式。使用二維的錯誤檢查碼甚至可以直接知道錯誤碼的位置。

5. Pattern Recognition (ch6)
最經典的問題是辨識0~9的數字，可以採用如knn、decision tree等，也可以採用類神經網路。

6. 資料壓縮(ch7)
所謂的無損壓縮(lossless compression)是指找到資料的pattern、儲存pattern來取代儲存資料本身的一種資料壓縮方式。例如:AAAABBB可以存成4A3B。
有損壓縮雖然不是白吃的午餐，但是常常很划算。

7. 資料庫transaction(ch8)
ACID properties可以確保資料庫在交易時是安全的。

8. 數位簽章(ch9)
資安相關的演算法。一個軟體要經過認證, 才能確保來源是安全的。
就像我們再使用信用卡的時候, 需要透過簽名才能確保是本人。
一個契約若由某個人(或是某間公司)所認可, 它必須要能夠通過數位簽章的審核。

例:
訊息:5
假設某A選擇一數字當作鎖: 6, 選擇時鐘尺寸(質數): 11 鑰匙: 2
有一個公家銀行提供某A的時鐘尺寸和鑰匙,
5*6 mod 11 = 8, 這個8即是數位簽章
這時如果有某個人想檢驗這個8是不是某A承諾的,
它只需要將 (8*2) mod 11 = 5
若剛好等同於一開始的訊息5, 即可開鎖

9. 如果存在會很了不起的演算法 (ch10)

什麼是可計算的?
再電腦科學的領域, 這是可以被證明的問題
例如搜尋當機行為的程式不可能存在
這可以by contradiction去證明

讓我想到離散裡,
有個理髮師宣稱他將會幫「不幫自己剪頭髮的人」剪頭髮,
證明這種理髮師不存在。

寫本網誌的目的

首先, 我寫本網誌不是為了紅,
所以並沒有希望瀏覽量會爆量呢XD

其次, 這網誌也不是在鄙視看倌的智商
我寫網誌的目的, 其實並不是為了把自己所學的東西教給各位
我沒有這麼偉大XD

本網誌對於我本人,目的有二:

一. 由於本人忘性很強, 所以要做紀錄

雖然我很想, 但很可能我不會一輩子待在學校,
對於好不容易重燃的學習熱情, 會希望這份心情能有個去處
還有, 雖然不是每個人都如此, 但我一向是靠著寫作在整理思緒
這些細碎的知識是我思想的枝葉, 我需要找個東西來把它固定住.整理起來
這樣這些知識才能真正成為我系統的一部分
錄影/音也只是我整理思緒的一種方式, 想得太快而打字很慢

二. 我希望能找到跟我討論課程內容的人

如果以類神經網路來比喻, 我的大腦結構是屬於layer比較多層的那一種
雖然對於複雜的model可以train得比較好, 但也很容易overfitting
我常常太過專心, 容易專注在某一個不重要的點上然後被卡很久, 藍瘦香菇~~QQ
如果有人可以跟我討論, 很多時候對於我來說是一種注意力的解脫和釋放
不管討論的內容本身有沒有營養, 都可以達成類似的目的
(當然如果能有營養又更好啦, 哈哈..)

再次理清楚目的,
然後希望別人也可以順水推舟地從中獲益
當然最好是可以認真點,比我還進入狀況然後教我啦XDDD
這樣我都靠人罩就好惹多開心wwwwww
不過不強求哈哈

我知道大家都很忙, 常常要累積到考前才肯稍微認真
有人不知道課程網站在哪裡, 甚至一些重要日期也懶得去記
本網誌就當作是做功德好惹~~

2016年10月20日星期四

2016/10/21 Machine Learning

今天講的東西終於跟之前聽過的課程重疊到
所以終於一次聽懂了～～感動

- - -

這門課每次到了下課，就會有一堆同學
像蒼蠅遇到＿一樣圍著老師猛問
而我就是其中一隻大蒼蠅
不過我發問都是問概念　很怕自己對概念有一點點不了解
而不像其他正統學院風的同學　對一些計算細節窮追猛打
老師人很好　從來不會失去耐心
但我承認　對於那些追著計算細節窮追猛打的同學　
佩服之餘也是稍稍有些不耐
我覺得這不符合機器學習這門課的精神
明明老師就是為了節省時間　故意略過細節不講
這樣又逼得老師要再花時間把那些細節拿到課堂上詳細推導一次
或許是工作養成的習慣
對於無意義的追根究柢感到過敏　　
- - -

Ch3 Linear Model for Regression

3.1 Linear Bayes function
3.2 Bias-Vraiance delimma
E(w) = E_D(w) + E_W(w)

2016/10/21 Algorithm

今天講 ch15 Dynamic Programming 上完15.2

2016/10/20 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

· Elementary Questions about Regular Languages [ pdf ] HW4.2 [ pdf ]

· Identifying Nonregular Languages [ pdf ] HW4.3 [ pdf ]

· Chap 5 Context-Free Languages

· Context-Free Grammars [ pdf ] HW5.1 [ pdf ]

Assignment 1 [ pdf ]

- - -

Ch4.2
Ch4.3

The pumping lemma: 在一個有m個state的automata裡, 走m步一定有重複的states(by pigeonhole) -> 我們用這個lemma去證明一個語言不是正規

證明方法通常先取一個長度大於m的例子(這樣等下才能套用lemma), 將這個例子拆成xyz三部分, 其中|xy|<m, 根據 pumping lemma, y是一個cycle, 應該要取幾次方都可以, 所以我們就取y的0~無窮次得到w0, w1, w2,...., 接下來只要證明這其中的某一個w不屬於L(格式不合)就可以

所以最tricky的地方是一開始取的例子,
取例子沒有一定的方法, 所以最好能多做題目,
取例子的原則, 是要取一個"很容易打破規則"的例子

非正規語言有以下特性:

(1)無法寫成正規表示式 ,
像 a^nb^n這種不是rex, 正規表示式的指數部分必須是已知的常數或*

(2)仍然可以用automata表示, 只是絕對是nfa, 不是dfa
如果是dfa, 那就是regular了

(3)最好也最常用的表示法是Grammar,
其Grammar不像regular只限定either right-linear or left-linear(只能二選一)
非正規語言可以允許right-linear和left-linear混雜, 簡稱linear

(4)絕對是infinite
如果是finite, 就可以用dfa表示, 那就是regular了

- - -
Ch5.1
context free, 是範圍更大.更不嚴謹的語言, 例: {a^nb^n}
之前介紹的都是regular, 包含於context free之中

- - -
期中考取消 @@"
作業也不用交
到學期末大概會一試定生死
怎麼會那麼刺激XD

2016年10月18日星期二

2016/10/19 Algorithm

今天上
8.3 Radix Sort

8.4 Bucket Sort

chap9 其他統計量（例如：max,min,medians的取得）

- - -
發回hw3

2016/10/19 meeting_deep learning

慶祝老師10/20生日~~
可是我真的吃不下炸雞, 只吃得下冰淇淋蛋糕
感覺昨天跑的又全都吃回來惹QQ

- - -
今日講題: CNN (Convolutional neural network)

Background

Local connectivity: 以image processing來說, 每個neuron不是抓大picture, 而是抓local的一個局部區域, 看在此局部區域內有沒有出現我們要找的feature, 每個neuron彼此再形成一個layer
Shared weight: neuron間彼此share weight 可以節省neuron

Architecture

原本的一個image, 經過convolution處理, 長寬一次比一此窄, 但一次比一次厚
厚度每一層就代表一個feature, 該layer上的數值即代表該feature的強度
Pooling layer: 把每個局部feature map中最大數值挑出來就好(因為只管有/沒有該feature)

Residual Nets

Deep Residual Learning for Image Recognition (Residual Net ICML)

由底層直接將Gredient直接傳到output層, 容易實作, 且不會有太多層無法training的問題

Identity Mappings in Deep Residual Networks

Application

- - -

《大演算》(The Master Algorithm) 心得

<大演算：機器學習的終極演算法將如何改變我們的未來，創造新紀元的文明？>

原文作者：Pedro Domingos
譯者：張正苓,胡玉城
出版社：三采
出版日期：2016/08/05

這本書非常新，是今年夏天才出版的，用簡單扼要卻又引人入勝的方式介紹了機器學習的歷史發展、五大主要流派各自的觀點和限制，並且提出一個「大演算」(The Master Algorithm)的概念，期許且預言，各理論流派將會進行整合，形成一個The Master Algorithm，並且對我們的未來產生廣泛而深遠的影響。

本書內容淺顯易讀，對於稍有資訊背景的人來說並不會很難懂，能稍有統計或類神經網路的知識又更好一些。

本書提到的五大流派，是指：

1. 符號理論：

數學上，我們習慣將現實的問題轉化成符號，用符號進行邏輯推演，再將推演的結果拿到現實中去驗證。決策樹(decision tree)就是一種將事實化成邏輯符號的例子。

2. 類神經網路：

顧名思義是模擬人腦神經元運作模式的一種技術。將每一神經元化為一個節點，節點之間層層相連(數學上來說是以權重做線性加成，再以一個激活函數對輸出結果做調整)的一種學習器。

此領域在1960年代曾將風光一時，研究者一開始認為可以用它來解決所有複雜問題，最後卻發現它甚至無法解決像是XOR這種簡單、但線性不可分離(Non-linear separable)的問題。

現今隨著deep learning技術發展起來，類神經網路理論亦死灰復燃。這個流派最大的缺點就是無法對它所學習到的東西(也就是各層的weight)進行物理上的解釋，而僅僅是一堆數字，同時也很容易overfitting，但他們在實務上可以取得良好的正確率。

3. 演化論：

遺傳演算法模擬生物學上染色體交配、突變、適者生存的法則，利用電腦母程式產生大量子程式，對不適者加以淘汰，以留下最好的學習法則。

4. 貝氏定理：

簡單貝氏定理(Naïve Bayes)非常基礎卻非常實用，適用性非常廣。一言以蔽之，它試圖用過去的經驗(prior)和目前的事實來預測未來發生的機率(postier)。諷刺的是，它雖然簡單，卻常常比一些複雜的學習法得到更好的成效。這是機率統計的威力所在。

5. 類比推理：

這個流派應用的例子如knn演算法、SVM(支持向量機)，藉由數據資料彼此之間的相似性(similarity)作為分類的判斷依據。

最後它提到機器學習的未來展望。作者認為，機器學習雖會偷走人類的工作，但同時也為人類創造更多的工作。人類可以利用機器學習對現實需求便宜行事，而花費更多心力在以人為本的問題上。

2016年10月17日星期一

2016/10/17 Pervasive Computing

今天是 ski-learn 和 Orange的 lab課
其實沒什麼可寫的

值得一提的是這個吧!

這是用Orange畫出的一張ROC圖,
如果預測的和實際相符, 就會往上走一格
如果預測的和實際不符, 就會往右走一格
換言之, 越彎的線, 是預測越好的分類方法
越接近x=y的直線, 是預測越差的分類方法
將ROC圖的線下面積積分, 可以得到AOC圖, 即是"正確率"的值

- - -

[Hate]
Orange安裝好但是不能開
一直刪掉重裝
....我真的覺得我是安裝軟體的白癡 = =
環境不熟就很難進入狀況的類型
每次裝軟體.熟悉軟體的所花的時間
都比真正做作業.寫project所花的時間多
如果有安裝軟體智障比賽我大概可以拿冠軍了

- - -

2016年10月16日星期日

Algorithm hw#5

雖然寫完了, 但Prob7-4還是有點疑問
我雖然知道tail-recursive那個algo是怎麼運作
但總覺得對於stack depth的部分沒有很通
沒有把它在腦內整合得很好
就是這樣所以才需要討論阿!

- - -

參考答案:

http://clrs.skanev.com/07/problems/01.html

http://clrs.skanev.com/07/problems/04.html

https://github.com/gzc/CLRS/blob/master/C07-Quicksort/problem.md

- - -

- - -

Prob7-1

Algorithm hw#1~4

hw1

hw2

hw3 (點link, shared with EverNote)

hw4 (點link, shared with EverNote)

Formal Language HW4-1 解題

4.1是講rex的closure properties

印象中, 線性代數裡講到封閉性(closeness), 指的是
一個向量空間中的兩個向量
彼此不管怎麼做線性加成, 都不會超出原本的空間, 這種性質稱為closeness

例: u,v屬於S => cu+dv屬於S, where c,d屬於R
一個非空子集合要同時具有向量加法與純量乘法封閉性

- - -
正規語言中的封閉性質
指的是當語言L1和L2滿足regular, 其交集, 聯集, 相乘(concatenation), 補集,取*...的語言也滿足regular

- - -
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/HW4.1.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_4.1.pdf

這小節幾乎都是證明題, 大概看過而已, 沒有很想證...@@"
證明regular的方法不外乎
(1)直接畫出nfa或dfa
(2)做一些數學運算展開, 然後引用正規語言的封閉性質得證

有想法請一起討論

- - -
2.
寫出transition states作化簡
太過trivial, 略

Formal Language HW3-3 解題

終於借到課本..

在解題之前, 先來複習一下Grammar吧!

V: 所有states (被使用在Grammar裡的)
T: alphabet, 例: {a,b}
S: V中的其中一個, 起始state
P: 終止state

- - -

描述正規語言的方法 (1)automata自動機 (2)Rex正規表示式 (3)Grammar
Grammer是其中一種, 換言之, Grammar可以與automata和rex互相轉換

一個Grammar分成left-linear和right-linear

right-linear: (產生的string由左往右堆疊, 就像一般的書寫習慣)
A->xB
A->x

left-linear: (產生的string由右往左堆疊)
A->Bx
A->x

其中A,B屬於V, (A,B是states)
x屬於T* (x是一個字元組合,字串)

- - -
例:
A->aaaB (right-linear)
A->λ
B->λ
等同於 (aaa)*
也可寫成:
A->aaaB
A|B->λ
或:
A->aaaB|λ
B->λ

"|"是"or"的意思

- - -

right-linear所畫出來的automata和寫出來的rex是我們最熟悉.最直覺的那種
left-linear所畫出來的automata, 箭頭方向要相反, input state和final state要互換
rex要每個段落都逆著寫

例:
S->abS|a
我們可以寫出 (ab)*a
若是 S->Sab|a
我們則要寫出 a(ab)*

- - -

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/HW3.3.pdf

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_3.3.pdf

11.

13.(a)

13.(b)

2016年10月13日星期四

2016/10/14 Machine Learning

今晚公布第一次作業
--
今天會把chap2上完,
講T-dist, Gaussian-dist的一些特性, 數學上的一些技巧
Exponential family dist.發展出conjutive prior

再來會上chap3大約1/3
什麼叫sparse? 如何找出sparse的解

上課主要抓main idea, 再透過hw去練習一些細節
hw可以用library但不能一式到位, 思路必須用code表達出來

2016/10/14 Algorithm

開始上chap8 Sorting in Linear Time
hw prob 7-1, 7-4

8.1 lower bond for sorting

Comparision Sort: 數值之間需要依賴"彼此比較"來做排序的一種sorting method. 我們目前教過的所有sorting method中, 只有counting sort不是Comparision Sort, 其他都是
Comparision Sort的下限是n lg(n), 可以用decision tree的方法去證明(樹高>=lg(n!)~n lg(n))
Thus, HeapSort 和 MergeSort 已達到 Comparision Sort的asymptically optimal

8.2 counting sort

T(n)=O(n+k) < O(n lg(n))
k: 資料種類數
此法不適用於種類太多, 分布太發散的數據資料(因為k大=>T(n)大)
Stable(必須由數據資料的後面sort回來才會stable(?))

2016/10/13 Formal Language

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

· 3.3 Regular Grammars [ pdf ] HW3.3 [ pdf ]

· Chap 4 Properties of Regular Languages

· Closure Properties of Regular Languages [ pdf ] HW4.1 [ pdf ]

--------------------------------------------------------------------------------------------------

複習chap3-2

空集合符號(ㄈㄞ)也可以寫進nfa的箭頭中, 意思是此路不通.不允許
和空字串(λ)意義完全不相同, 空字串是無條件通過, pass
將空集合符號寫進去, 有時是為了化成dfa的完整性, 或者寫成正規表示式有時更加方便(?)

chap 3.3 Grammars

right/left-linear: 是context free的一個特例

x: 轉換字元 terminal例: a,b.... 所形成的string

chap4 ragular language的性質

---

昨天沒睡好,今天超想睡....

但是還是覺得,好像沒有很難

不是說Grammar的部分比較難, 為何我沒有這種感覺

先把hw做完, 上課感覺就少了一些樂趣

2016年10月12日星期三

Formal Language HW3-2 解題

我真是個好人~~~

這次作業量也太多

歡迎一起討論

----------------------------------------------------------------------------------------------

10(b).

10(c).

13(a).

13(b).

16. 懶得看 = =

2016/10/12 meeting_deep learning

今天講實作TensorFolw

- - -

雖然有點猶豫要不要寫, 不過還是紀一下流水帳好了XD
(話說這個網誌原本的設定就是流水帳....?!)

- - -

好想買mac, 用windows跑這個真的超麻煩
然後今天真的很謝謝晨晨幫我一起看了很久的問題....
為什麼我硬體這麼弱QQ

2016/10/12 Algorithm

今天結束Ch7 Quick Sort, 提早下課5min XD
今天的重點有兩個:

1. Time complexity analysis
要特別注意, 用recursive tree的方法分析worst case, 只能得到lower bound,
不能得到upper bound, 因為找到一個n^2的case也無法證明它是worst

2. 既然worst case是O(n^2), 為什麼Quick Sort會是最快?
因為它的average case: O(nlogn)雖然跟其他例如merge sort或heap sort一樣
但它的係數c會比其他sorting方法來得小
原因是它pivot一旦選好後, 比pivot大的和小的就從此分開, 不會互相比較到
總體而言比較次數是比較低的
(前提是, 你使用課本的神之演算法!! 老師還特別提醒不要改任何細節,
要不然結果一定跑不出來,
不是遇到special case就當掉, 不然就是要多很多if..else判斷式而拖慢整體速度)

是不是應該來寫一下code驗證一下XDD

- - -
今天終於借到這本:

- - -
我覺得演算法這門課, 重點其實不是它介紹的這些演算法本身
而是藉由分析這些可以達成同一目的的演算法寫法, 藉由trace code
讓我們培養欣賞演算法的品味
我覺得這才是真正重要的

2016年10月10日星期一

Formal Language HW3-1 解題

4,5.

10.

13.

16.

17.

18.

2016年10月7日星期五

Formal Language HW2-3 解題

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/HW2.3.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_2.3.pdf

2.

Formal Language HW2-2 解題

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm

http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/HW2.2.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_2.2.pdf

3.

9. (略)
16. (題目似乎有問題, 略)
18. (沒耐心看完題目, skip)
21.

2016年10月6日星期四

2016/10/7 Machine Learning

期中考可以帶A4小抄
---

上次結束掉ch1, decision theory和information theory在ML的角色
上了Entropy及延伸出來的KL-divergence概念
主要用來測量一個機率分布是不是夠理想, 有多理想
也就是說, 我們所假設的機率分布p(x), 與我們實際觀測到的機率分布q(x)到底差距多遠
---
今天開始上Ch2 Probability Distribution (課程手稿講義p.19)
本次介紹在三種資料下的model, 以及其各自適用的機率分布,
重點在於介紹該如何從先驗機率(prior)推導至後驗機率(posterior)
以及證明各自的先驗(prior)機率模型及後驗(posterior)機率模型會剛好相同,
這也表示, 貝式learning方法可以支援sequential learning

三種資料:
1. {0,1} 整數 -> binomial
2. {....,-2,-1,0,1,2,....} 整數 -> multinomial
3. {3.14159, 1, -1, ....}實數 -> Gaussian

第二種例如text mining, 第三種例如signal
以上所提的三種model: binomial, multinomial, Gaussian指的是likelihood所取用的model
我們發現
type_1的prior取用Beta時,
其"conjugate prior", 也就是posterier, 也會是 Beta;
type_2的prior取用Dirchlet時,
其"conjugate prior", 也就是posterier, 也會是 Dirchlet;
type_3的prior取用Gaussian-Gamma時,
其"conjugate prior", 也就是posterier, 也會是 Gaussian-Gamma;

其公式為:
posterier = likelihood * prior
P( 未知參數 | data, 超參數 )
= P( data |未知參數 ) * P( 未知參數 | 超參數 )
超參數是指一個在計算過程中假設為固定的參數, 也是我們真正可以learn到的東西

整堂課就在進行以上所述的證明,
我們藉由不斷調整prior(簡單一點說, 就是tune機率分布的參數),
以學習到更正確的先驗機率
藉此提高prediction的準確率

其prediction公式為:
p(x=1|data) = 積分 { p(x=1|未知參數) * posterier }
----

2016/10/7 Algorithm

今天把Heap Sort上完上Quick Sort,
基本上, 還在資料結構範圍內
不過用演算法的角度看, 可以看到不一樣的東西

資料結構比較重在告訴妳, 定義是什麼, 它大概是如何運作
演算法則會告訴妳, 它有好幾種運作方法, 各是如何, 然後要用什麼角度去欣賞它

到目前為止還不難, 算是頗有趣~
但是好想要有人可以一起討論啊!
我看到周圍有同學在討論問題都覺得好羨慕 >"<

2016/10/6 Formal Language

今日進度:

2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters [ pdf ] HW2.3 [ pdf ]

Chap 3 Regular Languages and Regular Grammars· 3.1 Regular Expressions [ pdf ] HW3.1 [ pdf ]· 3.2 Connection between Regular Expressions and Regular Languages [ pdf ] HW3.2 [ pdf ]

---
Chap2.3 將nfa化成dfa

nfa可化成dfa, 所以沒有比較powerful, 但nfa可幫助我們思考
畫的時候, 如果原本nfa有k個states, 化成dfa最多有2^k個states
nfa允許 λ, dfa不允許λ
化成的dfa, state label為"原nfa states的部分集合"
如果化成的dfa state set中含有原本是◎的state, 即令此state為◎

---

Chap3 Rex和nfa的互化

Regular Ex. 是另一種Formal Language表示法
rex和autometa可以互換, 但有彼此各自比較適合的case
題型1: rex先化作nfa, 可再進一步化成dfa
題型2. nfa可簡化步驟(箭頭用rex表示), 然後一步一步簡化成rex

--

訂閱：文章 (Atom)

2016年10月31日 星期一

2016年10月30日 星期日

2016年10月29日 星期六

2016年10月27日 星期四

2016年10月25日 星期二

2016年10月24日 星期一

2016年10月23日 星期日

2016年10月20日 星期四

2016年10月18日 星期二

2016年10月17日 星期一

2016年10月16日 星期日

2016年10月13日 星期四

2016年10月12日 星期三

2016年10月10日 星期一

2016年10月7日 星期五

2016年10月6日 星期四