Hw 23-1, 23.2-4
想不到這麼快到了學期末，作業總成績要拿滿分似乎不是太難，只要有按時寫按時交
問題應該是考試，必須把除了作業以外的題目作熟才行，否則很難應付考試的變化。
然後，我說，為什麼不考多次一點呀。
2016年11月29日 星期二
2016/11/29 TOEFL
今天彈了一首風中奇緣的主題曲XDD
然後聊了一堆有的沒的, 像是movie Avatar
還有阿拉伯女孩的"超不"女權主義思想
I feel that her speaking is improving along with time, unlike me :(
And she said coming to the US broadened her vision.
That's not her original expectation,
but now she thinks it's is really helpful and even necessary.
I totally understood and couldn't help admiring her.
But I won't find a guy with green card to get married just because of that. XD
And she said coming to the US broadened her vision.
That's not her original expectation,
but now she thinks it's is really helpful and even necessary.
I totally understood and couldn't help admiring her.
But I won't find a guy with green card to get married just because of that. XD
Maybe I need another one to chat with,
I mean, like, language exchange, to catch up.
- - -
Section 2: TOEFL TPO 02 (from http://toefl.kmf.com/speaking/tpo-1)
TPO 02
Question 4
audience effect
1.
Put on shoes faster
2.
Learn Type faster
Question 5
Field trip
exhibition
1.
find a replacement
2. exhibition
first
2016年11月28日 星期一
2016/11/28 Pervasive Computing
今天開始分組上台報告
報告所涵蓋的內容大致如下:
老師會非常頻繁的打斷.問問題, 很像是在叮他研究生的報告
問題大致上都是長這樣:
報告所涵蓋的內容大致如下:
- 研究目的, 待解決問題
- 研究方法, 使用技術
- 使用的資料集(資料量,potential 問題)&前處理方式
- 實驗結果
老師會非常頻繁的打斷.問問題, 很像是在叮他研究生的報告
問題大致上都是長這樣:
- 用的資料有沒有問題? 是否有一些bias會造成結果不夠公正客觀?
- 使用技術是否可以達成研究目的? 為什麼用這個技術不用另外那個技術?
- 考驗講者對實驗流程和結果分析的理解程度 (就是在檢驗你有沒有認真看paper)
把paper看熟, 充分討論, 預想可能被問的問題, 這樣到時應該就ok
2016年11月26日 星期六
2016年11月25日 星期五
Formal Language_Assignment 1
其實作業都有解答了, 何必叫我們交呢?
1. hint: dfa的特色就是, 所有的{a,b}都要畫出來(即使是無意義的not-accepted),也就是一個state 都必須split出兩條線, 一條a一條b, 不能多也不能少
所以就連sink也要畫一條線寫a,b指向自己喔!!
(a)少畫了!!
2. hint:
(1) dfa不允許λ (2)dfa每條路都一定要走出去
8.
Pumpimg Lemma複習:
已知一個regular language L 有以下性質,
有一個數字m(此數字通常指dta的state數目)
若有一個string w屬於L且規定 |w| >= m
那麼w可以被拆成x,y,z三部分, let w=xyz
其中 |xy| <= m (規定的,這樣等下才能套用pigeon hole) 且 |y|>0 (y一定至少要一個字元)
則一個正規語言會滿足 : { w^i = x y^i z | i是任意正整數 } 全部必須屬於L
若違反了它, 就不是正規語言
Q. 證明L={a^nb^n}不是regular
(1) 假設L為regular
(2) 取一個m, 令m=n
(3) 因為|xy| 必須要<= m, 所以y落在a^n的區間
(4) 令y=a, x=a^5, z=a^(m-6)b^m
(5) w^i = x (y^i) z
(6) 當i>1時, 不符合language a^nb^n的形式, 違反Pumpimg Lemma, 所以L不是regular
所以簡單來說就是,
必須先找一個符合language格式的string w, 再取一個假設的正整數m
並且要保證 w的長度大於等於m, 再想辦法將w切成x,y,z 3部分, 改寫成wi = x y^i z的形式
最後只要能找到一個 i >=0 使得wi不符合 language的string格式,
就可以說它違反Pumpimg Lemma, 所以L不是regular
1. hint: dfa的特色就是, 所有的{a,b}都要畫出來(即使是無意義的not-accepted),也就是一個state 都必須split出兩條線, 一條a一條b, 不能多也不能少
所以就連sink也要畫一條線寫a,b指向自己喔!!
(a)少畫了!!
2. hint:
(1) dfa不允許λ (2)dfa每條路都一定要走出去
8.
Pumpimg Lemma複習:
已知一個regular language L 有以下性質,
有一個數字m(此數字通常指dta的state數目)
若有一個string w屬於L且規定 |w| >= m
那麼w可以被拆成x,y,z三部分, let w=xyz
其中 |xy| <= m (規定的,這樣等下才能套用pigeon hole) 且 |y|>0 (y一定至少要一個字元)
則一個正規語言會滿足 : { w^i = x y^i z | i是任意正整數 } 全部必須屬於L
若違反了它, 就不是正規語言
Q. 證明L={a^nb^n}不是regular
(1) 假設L為regular
(2) 取一個m, 令m=n
(3) 因為|xy| 必須要<= m, 所以y落在a^n的區間
(4) 令y=a, x=a^5, z=a^(m-6)b^m
(5) w^i = x (y^i) z
(6) 當i>1時, 不符合language a^nb^n的形式, 違反Pumpimg Lemma, 所以L不是regular
所以簡單來說就是,
必須先找一個符合language格式的string w, 再取一個假設的正整數m
並且要保證 w的長度大於等於m, 再想辦法將w切成x,y,z 3部分, 改寫成wi = x y^i z的形式
最後只要能找到一個 i >=0 使得wi不符合 language的string格式,
就可以說它違反Pumpimg Lemma, 所以L不是regular
2016/11/25 Machine Learning
有沒有"說一套做一套"的最佳典範?????!!!!!!
不是說觀念比較重要 推導細節不重要嗎???!!!!
那你的題目怎麼都是計算推導阿!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
怕影響GPA 目前正在考慮退選了....QQ
- - -
今天繼續上Ch6 Gaussian Process的Classification部分
Ch7.1 Maximum Margin Classifiers
不是說觀念比較重要 推導細節不重要嗎???!!!!
那你的題目怎麼都是計算推導阿!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
怕影響GPA 目前正在考慮退選了....QQ
- - -
今天繼續上Ch6 Gaussian Process的Classification部分
Ch7.1 Maximum Margin Classifiers
2016/11/25 Algorithm
今天上22.3~22.4
22.3
DFS有四種edge類型, 分別是Tree,Back,Forward,Cross edge四種, 它有其priority
灰: 已有起始時間, 沒有結束時間(已起始, 未結束)
黑: 已結束
白: 未走到
當你由灰看到白, 那是tree edge
當你由灰看到灰, 是Back edge (其祖先尚未結束)
當你由灰看到黑, 可能是 Forward edge 或 Cross edge
比較起始時間, 較晚是Forward edge, 較早是Cross edge
以上是對有向圖而言,
對無向圖, 只有Tree,Back edge兩種
因為Back edge基本等同於Forward edge, 定義為Back edge
Cross edge不會存在, (這需要proof)
因為假若Cross edge存在, 表示這兩點在最一開始就是連通的,(因為無向)
那麼怎麼可能之前在拜訪黑點時, 沒有找到現在的這個灰點呢?
by contradiction 得證
22.4
Topological sort是一種排程方法, 描述一種"滿足等待關係"
其方法很簡單, 在做DFS時maintain一個stack, 對每一個結束的node, 當記錄結束時間時, 將此node丟進stack中, 再依序pop出來即是答案(i.e. 結束時間的相反順序)
22.3
DFS有四種edge類型, 分別是Tree,Back,Forward,Cross edge四種, 它有其priority
灰: 已有起始時間, 沒有結束時間(已起始, 未結束)
黑: 已結束
白: 未走到
當你由灰看到白, 那是tree edge
當你由灰看到灰, 是Back edge (其祖先尚未結束)
當你由灰看到黑, 可能是 Forward edge 或 Cross edge
比較起始時間, 較晚是Forward edge, 較早是Cross edge
以上是對有向圖而言,
對無向圖, 只有Tree,Back edge兩種
因為Back edge基本等同於Forward edge, 定義為Back edge
Cross edge不會存在, (這需要proof)
因為假若Cross edge存在, 表示這兩點在最一開始就是連通的,(因為無向)
那麼怎麼可能之前在拜訪黑點時, 沒有找到現在的這個灰點呢?
by contradiction 得證
22.4
Topological sort是一種排程方法, 描述一種"滿足等待關係"
其方法很簡單, 在做DFS時maintain一個stack, 對每一個結束的node, 當記錄結束時間時, 將此node丟進stack中, 再依序pop出來即是答案(i.e. 結束時間的相反順序)
2016年11月24日 星期四
2016年11月22日 星期二
2016/11/23 Algorithm
Ch21 Ackermann's function, g函數, 是一個成長率極高的函數, 它的反函數就是一個almost constant
Ch22 review graph, data structure of graph storage, BFS, DFS,
...
2016/11/22 TOEFL
Fang一早起來看起來很想睡的樣子 XD
所以我彈唱了一首 Bizarre Love Triangle給她聽
雖然彈得很不怎樣 (因為是我的晚上 我也很想睡 )
但她很捧場 說她醒了 還說早晨聽到很romantic XDD
今天練習了3題:
- - -
3. Read the passage and answer the question
The university has decided to cancel the student health center on campus.
The reason is that a new hospital has been opened recently in the local
community. Because the new hospital is very close to the campus and most
students can have convenient access to it, and also because the new hospital
comes with a lot of first class medical equipment, which the student health
center lacks, the student health center’s existence is not justified any more.
Also, the money saved by canceling the student health center will be used to
amplify the library storage
The woman expresses her opinion of the school’s cancellation of the
student health center. State her opinion and explain the reasons she gives for
holding that opinion. (60s)
2016年11月17日 星期四
Algorithm hw#10
| hw1 | hw2 | hw3 | hw4 | hw5 | hw6 |
| 70 | 100 | 100 | 100 | 85 | 100 |
| hw7 | hw8 | hw9 | hw10 | hw11 | hw12 |
| 95*0.7 =67 | 100 | ? |
還差2次
Prob21-1,21-3
2016/11/18 Algorithm
今天上課2hrs
結束ch17, 開始ch21 data structure for disjoint set, 這章並不難
應用: 找出connected component
Original Disjoint
Make() => O(1) *n
Find() => O(1) *f
Union() =>worst O(n) *(n-1)
=>worst O(n^2)
Weighted Disjoint
Make() => O(1) *n
Find() => O(1) *f
Union() =>O(nlgn)
=>worst O(m+nlgn)
where m=n+f+(n-1), n:#Make f:#Find, m: #(Make,Find,Union)
結束ch17, 開始ch21 data structure for disjoint set, 這章並不難
應用: 找出connected component
Original Disjoint
Make() => O(1) *n
Find() => O(1) *f
Union() =>worst O(n) *(n-1)
=>worst O(n^2)
Weighted Disjoint
Make() => O(1) *n
Find() => O(1) *f
Union() =>O(nlgn)
=>worst O(m+nlgn)
where m=n+f+(n-1), n:#Make f:#Find, m: #(Make,Find,Union)
Machine Learning hw#2
出了出了~~~~QQ
https://drive.google.com/open?id=0B57k_NHxboqhSFN0RUNiVGkwUEk
截止日期：2016/12/02 23:59
目前策略是先用sklearn寫一次跑答案, 再想辦法把它改成無sklearn的版本
助教說明錄音檔(.aac)
https://drive.google.com/open?id=0B57k_NHxboqhSVFCNnpDbWk1Vms
2016/11/17 Formal Language
今天的課程內容十分重要
- - -
8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受
9.1
所謂algorithm就是一個會停的turing machine
圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。
圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)
| Machine | Language |
| finite state automata(nfa) | Regular |
| pushdown automata(npda) | Context-Free (CF) |
| turing machine | Recursively enumerable (RE) |
- 何謂deterministic?
指所有alphabet可能路徑, 最多都只有一條
例如 alphabet = {a,b}
每個state最多只會有一條a, 一條b
- 何謂halt?
在TM中, halt states 指的是到達了一個transition state沒有定義的state, 那麼就會終止了
2016/11/17 Formal Language
8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受
9.1
所謂algorithm就是一個會停的turing machine
圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。
圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)
2016年11月16日 星期三
2016/11/15 TOEFL practice
2016.11.15
Section
one: A memorable trip.
Section two: TOFEL
exercise
1. Choose one of your favorite methods to relax and explain why it is
your favorite.
Please include specific details in your explanation. (45s)
2. Some students prefer the internet-based teaching. Others prefer to
study in traditional classrooms. Which method of studying do you prefer or why?
(45s)
2016/11/16 meeting+Deep Learning
- LSTM (Long-short-term network)
- http://colah.github.io/posts/2015-08-Understanding-LSTMs/
- 因為RNN會有隨時間記憶遞減的現象, 因此有LSTM作為解法
- 可以 記得 or 忘記 or Input or Output
- Forget gate
- Input gate
- Output gate
- Memory network
- 用storage section儲存資料,用NN做分類讀取資料區
- 可應用在類似閱讀測驗
- 存起每個句子, 透過一個score function篩選出對問題最有用的句子
- Attention
- More…
- Neural Tuning Machine
- Neural Programmer
- Diffentail Neural computer
2016年11月15日 星期二
2016年11月14日 星期一
Formal Language 7.3 自讀
因為11/10期中考周沒去上課, 在此自己讀, 補起一些進度
7.1 介紹什麼是pda (pushdown automata)
它是導入一個Stack來儲存automata的資訊
使得automata本來是infinite的(無限多個), 變成finite(有限個)
進而可以用來表示context-free的語言
(原本的dfa和nfa都只能表示regular的語言, context-free比regular範圍更廣)
7.2 說明npda (non-deterministic pushdown automata)的建構和性質
理論 Thm7.1: 所有context-free的語言, 都可以被npda所接受
這節的題目, 主要是給你一個Grammar, 要你建構出一個npda
答案都只有用transition states表示 (但我個人習慣一定要畫圖, 才比較好思考)
Grammar --> Language --> 畫圖 --> 寫出transition states
如果遇到不能輕易看出language結構的Grammar, 會很難下手畫圖
就要試著將它轉成Greibath Normal Form, 這樣就可以跳過畫圖的步驟, 輕鬆寫出transition state
Grammar --> Greibath Nomal Form --> 寫出transition states
不過像是Chomsky Normal Form我想應該ok, 因為它比Greibath Normal Form更簡單
忘記這兩個Normal Form的話, 請複習一下6.2
可以參考這個網站, 裡面有提到這些Normal Form的設計目的
文法結構一旦改寫成 Chomsky Normal Form ， Parse Tree 就是一棵二元樹，得以設計高效率的資料結構與演算法。
7.3 說明在context-free L裡, deterministic的定義為何?
(翻譯: 什麼能算是dpda(deterministic pushdown automata)?什麼是npda?)
根據Def. 7.3: dpda的條件有兩個
(1)一個狀況(一種(q,a,b)的transition)只能有一條路可以選擇
(2)結束點( (q,空字元,b)的transition set 非空 )的結束字元一個state只有一種, 後面不會拖尾
2016年11月11日 星期五
Algorithm hw#9
17.2-3
9.1-1
deadline 11/18
9.1-1
參考:
- http://www.roading.org/algorithm/introductiontoalgorithm/%E7%AC%AC%E4%B9%9D%E7%AB%A0%E4%B9%A0%E9%A2%98%E9%80%89%E5%81%9A.html
- https://sites.google.com/site/clrssolutions/home/chapter09
17.2-3
參考:
寫了1.5hr
2016/11/11 Algorithm
今天繼續上ch17 Amortized Analysis
17.4 Dynamic Table
這節主要講一個動態的陣列, 它的容量會隨儲存量的多寡, 而有size上的自動變化
雖然看起來這種"動態"好像要花不少時間,
但它可以證明, 透過本章的"先付款"方法
(假設中線是最prefer的狀態, 超過中線付$2, 低於中線付$1)
可以控制每一步成本約是O(1),
其中Insert的成本小於等於3, Delete的成本小於等於2
而存款永遠都是正的(圖Figure 17.4)
17.4 Dynamic Table
這節主要講一個動態的陣列, 它的容量會隨儲存量的多寡, 而有size上的自動變化
雖然看起來這種"動態"好像要花不少時間,
但它可以證明, 透過本章的"先付款"方法
(假設中線是最prefer的狀態, 超過中線付$2, 低於中線付$1)
可以控制每一步成本約是O(1),
其中Insert的成本小於等於3, Delete的成本小於等於2
而存款永遠都是正的(圖Figure 17.4)
2016/11/11 ML midterm
- 考六題，都是推導題。沒有直接出課本例題，也沒有出作業，出的是手寫講義上的推導。
- 考題被收回去。
- 以第四章出的比率最重(有兩題)，這應該代表第四章最重要，但是第四章卻是最後(上週)講，也花最少時間講。
- 這次根本是在比誰的小抄抄得比較齊全。小抄無敵重要。要好好作。
- 這堂課是困難版的統計。在修統計課遇到的問題，這裡也通通遇到了。所以本質上它是門數學課。
- 要預習，要複習，只懂觀念沒有用。講義要自己推導一次。
- 沒有考好。只能指望期末考救分數了。QQ
- 下次比較知道怎麼準備了。...基本上就是全部都考數學推導。所以那些跟老師問計算細節的同學是對的，在學校裡要應付考試要拿高分，就是要鑽牛角尖。
- 其實我比較喜歡"考多次，每次佔分不高"的模式，我可以比較熟悉考試模式，即使第一二次沒考好，後面也有機會拉回來。對我這種常常要不到考古題的邊緣人，這還蠻重要的。而且也不會造成學期初很閒，學期末快忙炸的極端狀況。
小抄:
2016年11月9日 星期三
Machine Learning應考策略
其實完全無策略XD
無考古題, 完全不知道會怎麼考,
目前只知道會從課本例題出(ch1-4一章一題?),可能會再加一題作業吧
可以帶a4小抄,考ch1-ch4, 大約5題
假如全部都出推導題 我就完了QQ
希望可以出觀念題 這樣還有救
說真的光是上課聽懂已經很吃力了
觀念的建立已經是那麼困難
更不要說觀念背後的數學推導, 也只知道個大概
並沒有把他實際算過一次
(我應該更認真些的..希望不要走到把某科二退的命運)
這禮拜完全沒有心情上課, 遍佈式和正規都翹掉了
- - -
川普當選之後突然有動力畢業了 = =
- - -
重點:
Ch1. Entropy & KL-divergence
Ch2. Prior-Likelihood-Posterier (最後面放棄QQ)
Ch3. Regression
Ch4. Classification
Ch3. Regression
Ch4. Classification
2016年11月8日 星期二
2016/11/9 Algo midterm
Algo Midtrem考試策略
事前準備:
其實我沒有花很多時間念
以這個老師的個性, 我推測不會考太多重複或過於類似的題目
所以念考古題應該會有用, 但也僅止於對考試模式的熟悉
雖然說細節扣分扣很重, 可是對我這種沒念得很細的人來說
反而是解題方向比較重要
換言之, 我覺得題目有"先看過, 先想過"
這件事情可能比花時間在追究細節還重要得多
畢竟是演算法"設計"
設計理念比表達方式重要
根據考古題的配分如下:
25% ch1-4 (big-O和解recurrence, 這個地方的分數一定要把握住)
30% ch6-9 (Sorting, 這裡會出現一些不在課本內的應用問題, 但是不算難!重點在分析time)
25% ch15-16 (DP和greedy, 這裡出現的多是課本後的例題, 但是很難, 不太容易想到)
10% hw 二選一 (個人覺得不會出太過複雜hw題,畢竟只是要考我們是否是自己寫的)
10% self-taught (ch10-12, 不難但是要看過, 否則沒分)
由此可以看出拿分的重點在25% ch1-4+10% hw
其他部分都要靠臨場,
10% self-taught則要靠運氣
- - -
考試策略:
- - -
以下為考古題題目&自己練習的解答
- 根據有一堂助教講解課的補充, ch16 greedy可能會考跟OBST有關的問題
- 作業題: 作業要做, 但不要走火入魔, 只有10%
- Bonus: 應該考ch10-12自己讀部分, 但其實重要的只有ch12, 考你有沒有讀而已
- Design的部分非常重, 幾乎占了50%以上, 無法穩穩拿分, 要靠臨場反應
- 睡飽
其實我沒有花很多時間念
以這個老師的個性, 我推測不會考太多重複或過於類似的題目
所以念考古題應該會有用, 但也僅止於對考試模式的熟悉
雖然說細節扣分扣很重, 可是對我這種沒念得很細的人來說
反而是解題方向比較重要
換言之, 我覺得題目有"先看過, 先想過"
這件事情可能比花時間在追究細節還重要得多
畢竟是演算法"設計"
設計理念比表達方式重要
根據考古題的配分如下:
25% ch1-4 (big-O和解recurrence, 這個地方的分數一定要把握住)
30% ch6-9 (Sorting, 這裡會出現一些不在課本內的應用問題, 但是不算難!重點在分析time)
25% ch15-16 (DP和greedy, 這裡出現的多是課本後的例題, 但是很難, 不太容易想到)
10% hw 二選一 (個人覺得不會出太過複雜hw題,畢竟只是要考我們是否是自己寫的)
10% self-taught (ch10-12, 不難但是要看過, 否則沒分)
由此可以看出拿分的重點在25% ch1-4+10% hw
其他部分都要靠臨場,
10% self-taught則要靠運氣
- - -
考試策略:
- 字寫得少而清楚, 能用數學表達盡量用數學表達
- 多花時間理解題目和想演算法, 少花時間寫字
- 任何演算法, 都要寫出(1)作法 (2)說明正確性, 以及(3)時間複雜度
- 每一個chapter都有它的核心精神和概念, 想演算法的時候, 注意跟chapter主題的連結
- 想的時候, 盡量簡化問題,不要複雜化問題
- 細節可以最後再補, main idea要先有
- - -
以下為考古題題目&自己練習的解答
2016年11月7日 星期一
知道得太少或太多
等餐中，打個文章。
現在在準備期中考，常常覺得自己有個問題，那就是知道得太多。例如說，知道自己即使把這個題目算很熟，對未來也沒有太大作用。 然後就有點失去動機，失去耐心。
可是，如果不願意去鑽牛角尖，就沒辦法拿到漂亮的分數。 我懷念我一年前剛開始修課的時候。那時候什麼都不知道，也就什麼都新奇有趣。
我常常覺得，有時候知道得少一點是好事。想想，假如你小時候知道自己要背房貸車貸，每天要被老闆照三餐罵，又在鬼島環境領低薪，還會期待長大嗎?
或者，知道成績不代表實力，出社會後嘴炮的重要往往又更勝於實力，我們還會想要在課業上努力嗎?
懷念單純，在一個不夠單純的年紀。
儘管天性複雜，卻嚮往能活得簡單。
2016年11月6日 星期日
Algorithm hw#8
Ex. 16.1-4
Ex. 16.3-6
- - -
這次作業比較簡單(Ex都比Prob簡單)
所以2個小時就寫完
其中16.1-4有參考:
- - -
- - -
| hw1 | hw2 | hw3 | hw4 | hw5 | hw6 |
| 70 | 100 | 100 | 100 | 85 | 100 |
| hw7 | hw8 | hw9 | hw10 | hw11 | hw12 |
| 70以下 | ? |
還差3次
2016年11月4日 星期五
Algorithm hw#7
Prob. 15-5
Ex. 15.4-5
繳交期限是 11/04 下午五點前
本次作業遲交, 會打7折...@@
太晚開始念了, 覺得應付期中考有點來不及
明天早上要去清大交作業和拿回改完的hw6
Ex. 15.4-5
繳交期限是 11/04 下午五點前
本次作業遲交, 會打7折...@@
太晚開始念了, 覺得應付期中考有點來不及
明天早上要去清大交作業和拿回改完的hw6
Ex 15.4-5
這題首先要了解什麼是Longest Common Subsequence （ LCS ）演算法:
這個演算法主要是用動態規劃(DP)去做, 可以找出"兩段序列"的"最長共同子序列"
應用在像是DNA比對等領域
本題要求出一個序列的"最長單調遞增"子序列
做法是將該序列S進行sorting(O(nlogn))得到S',
再將S與S'去跑LCS(O(n^2))即可求得
參考網址:
Prob 15-5
這題題目很長,我先參考了LCS教學視頻和Edit Distance教學視頻:
還有參考這個pdf
大概心理有個底之後才開始寫, 然後大概寫了2-3個小時
2016年11月3日 星期四
2016/11/4 Algorithm+期中考考古助教講解
Ch17 Amortized Analysis
17.1 The aggregate method: 均攤成本的概念, T(n)/n
17.2 The accounting method: 訂一個規律的付款方式, 只要保證戶頭裡有錢
17.3 The potential method: 由存款變化決定該怎麼付錢
- - -
11:00-12:00 助教講解考古題
考試只會出最多兩題作業, 而且是二選一作答, 10%
其餘散布在各章節
----
Prob6-7
17.1 The aggregate method: 均攤成本的概念, T(n)/n
17.2 The accounting method: 訂一個規律的付款方式, 只要保證戶頭裡有錢
17.3 The potential method: 由存款變化決定該怎麼付錢
- - -
11:00-12:00 助教講解考古題
考試只會出最多兩題作業, 而且是二選一作答, 10%
其餘散布在各章節
----
Prob1
Prob1-3
Prob3
Prob3-5
Prob6
Prob6-7
Prob7-8
2016/11/4 Machine learning
下週考試可以帶a4小抄,考到ch4, 大約5題
從作業.textbook例題出，考試題目不會超出課本範圍
- - -
hw1 -- 98
竟然有抓抄襲, 很可怕,
因為我1,2題有參考晨晨的
3,4題的code也有給晨晨, 只是我後來整個大改寫
所以交出去的code長得已經完全不一樣了
我個人是覺得, 紙本部分他不會抓抄襲, (因為沒有自動比對程式)
只有程式題才有機會被抓, 被抓到直接*0.3, 粉可怕
但是其實我們都有互相討論阿....只是code還是要自己寫過
覺得這門課以後還是不要直接share答案, 不管是被shared, 還是share給別人
話說這門課怎麼這麼硬... 硬度根本是其他三門的總和
每次禮拜五都覺得壓力頗大
- - -
今天把ch4在三小時內通通上完
根本就是在趕課阿
ch4講classification的數學原理
比較重要的是logistic regression和它的Laplace近似
logistic regression是指函數輸出時, 有用一個sigmiod function去做轉換
這跟在regression裡提到的sigmoid基底函數不同
logistic regression基本上不是Regression, 而是一個Classification問題
Regression的輸出是連續, 不是label型態, 也比較容易找得到close form
Regression和Classification最大的差別,
在於Classification還有外加一個輸出函數(可以想像成是類神經網路的激活函數)
Regression沒有
但兩者都可以對X取基底函數
logistic regression的Laplace近似其實就是用二次微分的泰勒展開式去逼近一個高斯分布
從作業.textbook例題出，考試題目不會超出課本範圍
- - -
hw1 -- 98
竟然有抓抄襲, 很可怕,
因為我1,2題有參考晨晨的
3,4題的code也有給晨晨, 只是我後來整個大改寫
所以交出去的code長得已經完全不一樣了
我個人是覺得, 紙本部分他不會抓抄襲, (因為沒有自動比對程式)
只有程式題才有機會被抓, 被抓到直接*0.3, 粉可怕
但是其實我們都有互相討論阿....只是code還是要自己寫過
覺得這門課以後還是不要直接share答案, 不管是被shared, 還是share給別人
話說這門課怎麼這麼硬... 硬度根本是其他三門的總和
每次禮拜五都覺得壓力頗大
- - -
今天把ch4在三小時內通通上完
根本就是在趕課阿
ch4講classification的數學原理
比較重要的是logistic regression和它的Laplace近似
logistic regression是指函數輸出時, 有用一個sigmiod function去做轉換
這跟在regression裡提到的sigmoid基底函數不同
logistic regression基本上不是Regression, 而是一個Classification問題
Regression的輸出是連續, 不是label型態, 也比較容易找得到close form
Regression和Classification最大的差別,
在於Classification還有外加一個輸出函數(可以想像成是類神經網路的激活函數)
Regression沒有
但兩者都可以對X取基底函數
logistic regression的Laplace近似其實就是用二次微分的泰勒展開式去逼近一個高斯分布
2016/11/3 Formal Language
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/note.htm
關於作業講解, 我目前還欠4-2, 4-3, 6-2, 6-3 沒有錄
以及這次的 Assignment1
- - -
今天講了6-1~7-1
6-1 講簡化一個context-free grammar的方法
6-2 介紹兩個context-free grammar的Normal Form, 分別是Chomsky和Greibach
6-3 講CYK algorithm
7-1 介紹什麼是push-down automata (npda)
- - -
前言
- Chap 6 Simplification of Context-Free Grammars and Normal Forms
- Methods for Transforming Grammars [ pdf ] HW6.1 [ pdf ]
- Two Important Normal Forms [ pdf ] HW6.2 [ pdf ]
- A membership Algorithm for Context-Free Grammars [ pdf ] Sol_6.3 [ pdf ]
- - -
關於作業講解, 我目前還欠4-2, 4-3, 6-2, 6-3 沒有錄
以及這次的 Assignment1
今天講了6-1~7-1
6-1 講簡化一個context-free grammar的方法
6-2 介紹兩個context-free grammar的Normal Form, 分別是Chomsky和Greibach
6-3 講CYK algorithm
7-1 介紹什麼是push-down automata (npda)
- - -
前言
- given w, G, 判斷一個w是否屬於L(G), 這個過程叫做parsing
- context-free grammar <-> push-down automata
Ch 6.1
簡化一個context-free grammar的方法包含以下三步驟:
簡化一個context-free grammar的方法包含以下三步驟:
- remove empty string
- substitution method
- remove useless sentence(無限loop,走不到final的那些)
關於這個簡化過程,我有打算錄一下視頻介紹, 因為很trivail很容易忘
Ch6.2
Chomsky Normal Form: 所有grammar都符合A->BC or A->a的形式
Greibach Normal Form: 所有grammar都符合A->ax的形式 (很像s-grammar)
Ch6.3 CYK algorithm (用到演算法中的Dynamic Programming)
Ch7.1 push-down automata (npda)
這個很有趣, 我也有打算錄一下視頻, 講一下課本2個例題
不然也可以用key word "push-down automata"去google一下
Ch6.2
Chomsky Normal Form: 所有grammar都符合A->BC or A->a的形式
Greibach Normal Form: 所有grammar都符合A->ax的形式 (很像s-grammar)
Ch6.3 CYK algorithm (用到演算法中的Dynamic Programming)
Ch7.1 push-down automata (npda)
這個很有趣, 我也有打算錄一下視頻, 講一下課本2個例題
不然也可以用key word "push-down automata"去google一下
2016年11月2日 星期三
2016/11/2 meeting_deep learning
今天老師沒來...
- - -
Generative Model
- Representation表徵(與feature不同)
- Brain,Mind,Machine(MIT-Edx) 哲學角度看AI (strong/weak)
- summer school machine learning 2016
- 得到事物很好的Representation(表徵), 再用此Representation做修改.組合, 再generate出新的.從沒看過的新事物
- Autoencoder
壓縮並還原
- RBM/Pixel RNN
自動補照片空缺, 用前面的N個pixel推測出後面的pixel
- Variational Inference
- Generative Adseratial Network(GAN)
2016年11月1日 星期二
2016/11/2 Algorithm
今天第一堂課沒有上到@@
第二堂開始上ch17 Amortized Analysis
http://mropengate.blogspot.tw/2015/06/algorithm-amortized-analysis.html
它是一個成本平均化的概念
例如有一台印表機每印500張就要換紙
第500張換紙的時間成本顯然要加進第1~499張的時間成本去均攤
那為何要用Amortized Analysis呢?
因為在某些特定的case下,
(例如像前述的印表機問題,久久才出現一次鉅額成本)
用Amortized Analysis比起best case或worst case的分析更準
第二堂開始上ch17 Amortized Analysis
http://mropengate.blogspot.tw/2015/06/algorithm-amortized-analysis.html
它是一個成本平均化的概念
例如有一台印表機每印500張就要換紙
第500張換紙的時間成本顯然要加進第1~499張的時間成本去均攤
那為何要用Amortized Analysis呢?
因為在某些特定的case下,
(例如像前述的印表機問題,久久才出現一次鉅額成本)
用Amortized Analysis比起best case或worst case的分析更準
Formal Language HW5-1 解題
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Chap-5.1.pdf
http://people.cs.nctu.edu.tw/~rjchen/FormalGrad-2016/Sol_5.1.pdf
7.(a)
7.(d)
7.(f)
8(a)
8(e)
8(h)
13.
20.
23.(skip)
訂閱：
意見 (Atom)