image n! $(log n)!$ is <font color="#f00">not</font> polynomially bounded $(log log n)!$ is polynomially bounded and for any real number x ≥ 0 and integers a, b 0, url

本文主要介紹演算法 DP 問題中其中一個常出現的題目 Matrix Chain 實際上如何計算，以及稍微解釋建 table 時背後的意義。 如果對於文中的截圖有興趣，可參考最下方的 Reference。 另外，這篇文章是為了我考研究所的妹妹寫的 :D 這次寫完這篇筆記，回顧一年前考試時的內容已經比當時更熟悉。發現這件事讓我很開心，也很希望能像以前一樣不斷更新筆記，只不過研究所實在是太忙了QQ 或許要等到去工作以後才有辦法吧 XD 總之，現在有辦法更新的東西大概只有 github 了，我的頁面主要放一些學校的作業和筆記，有興趣的朋友可以來我的 github 串串門子～ Pseudocode code

整理這一系列文章，主要是為了加強我自己對 ML 的理解。雖然有點花時間，但是覺得用自己的話重新把東西講一遍，常常能夠發現一些原本自以為懂，但其實概念模糊的地方。 建立在這樣的出發點，內容大部分是我每讀完一段後大致的課本原話翻譯（有時候可能省略部分例子或是一些額外的描述），有些是我了解大概的意思，加上回想過去所學後整理出的理解，除此之外，也有網路上到處看看後做的整理。 關於網路資源，如果只有一兩句話就不會特別註明，但如果有參考較多的地方會在最下方「參考資料」處留下連結。 總之是綜合各方面的東西做出來的筆記，因此可能有誤，歡迎指出～ 另外，在撰寫這一系列筆記的一學期過後，我修了台大林軒田老師的機器學習，發現所有這些筆記裡最有幫助的部分應該只有機率，其他老實說用不太上（或過於簡單）XDD

Fibonacci Heap Pasted Graphic 2 Definition 由很多個 rooted tree 組合而成，而每棵 tree 都具 Min Heap property <font color = "snake">root list</font>: 用Circular doubly linked list 串連所有的 root <font color = "snake">Child list</font>: 用Circular doubly linked list 串連所有的 child 用Circular doubly linked list的好處：

這篇筆記主要用來記錄 $113$ 學年度上學期，黃文良老師的「訊號處理和機器學習之數學基礎」課程筆記和課本閱讀的整理。 因為開學後感覺時間或許沒有那麼多，不知道能更新多少，紀錄筆記的方式也不會像寫 ML 筆記時那麼詳細，但筆記的作法仍然和當初類似，每篇筆記會對應課本同一小節的內容，課本主要用的是： :::info Boyd and Vandenberghe 的 Convex Optimization ::: 點課本名稱的連結，能下載課本和 lecture slides。

Convex Optimization 筆記說明 Ch1 Introduction 1.1 Mathematical Optimization 1.2 Least-squares and linear programming

背景 前面一節我們有講到，我們可以將 sample 中的 $N$ 個 data points，每個具 $d$ 個 features，用 matrix $X$ 表示： \begin{equation} X = \begin{bmatrix} X_1^1 & X_2^1 & ... & X_d^1 \ X_1^2 & X_2^2 & ... & X_d^2 \ . & \ . & \

README Ch1: Introduction 1.1 What is Machine Learning? 1.2 Examples of Machine Learning Applications 1.3 Notes Ch2: Supervised Learning 2.1 Learning a Class from Examples 2.2 Vapnik-Chervonenkis Dimension

我們在 $6.1$ 的 Introduction 中有提到，feature extraction 有兩種常用的 method： Principal Component Analysis (PCA) linear discriminant analysis 兩者都是利用 linear projection。在像這樣的 projection methods 中，我們想要做的是： :::info 找到一個 mapping，在喪失的資訊最小化的情況下，將原本在 $d$-dimensional space 中的 original inputs，map 到另一個小於 $d$ 的 $k$-dimensional space。 :::

本篇文章的內容為筆記「補充：Exploratory Data Analysis」的延續，在那篇筆記裡，最後當我們在講 outliers 時，因為篇幅太長，所以我們只講了課本的 univarite 的情形。 當時我們說，利用 box-plot 或是其他的 graphical technique，我們可以用看的就能找出 outliers，但是這樣的方法只適用於 univariate data。 當我們的 data 是 multivariate 時，我們是沒有辦法用看的就找出哪些是 outliers，挑出 outliers 的工作也就變得複雜許多。 實務上，當我們的 variable 數 $d>2$ 時，就很難去辨認 outliers。 在這篇筆記裡，我只會簡單講一下 multivariate case 的情況下我們大致上可以怎麼做，舉簡單的例子，停在大概有點概念的程度。如果有興趣深入看看，參考資料的兩篇文章一篇介紹了如何用 python 來計算 MD，另一篇為 multivariate outliers detection 的論文，這篇論文前半部分還是很容易懂的，後半部我就沒看了，總之有興趣可參考！

課本中的向量皆用粗體，以往我都是省略直接用 $x$ 表示，看得懂就好，但現在符號比較多，為避免混淆，還是決定將向量都標上向量符號。 本節內容為以前我們學過的 univariate normal distribution 推廣到 multivariate 的情形。 首先，recall 我們在 univariate case 裡如何去定義一個 random variable $X$ 具 normal distribution，我們當時說，只要 $X$ 的 pdf 滿足： \begin{equation} p(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}} \end{equation}

前一節的 Introduction 裡面我們有提到，feature selection 的一種做法叫做 subset selection。在 subset selection 中，我們的目標是從原本所有的 features 裡面，挑出一個最好的 subset。 什麼叫「最好的 subset」呢？ :::info The best subset ++contains the least number of dimensions++ that ++most contribute to accuracy++. ::: 至於剩下的 features，我們就直接捨棄掉。

不管是在 regression 或 classification 裡： :::warning 任何 regressor / classifier 的 complexity，都 depends on input (feature / attribute) 的數量。 ::: 在前面第五章裡，我們在討論 multivariate data 時，都是令每個 data point 為： \begin{equation} \vec{x} = [,x_1,...,x_d],

判斷 Performance 的前提： 要決定一個系統要用哪種 allocation method，需要先判斷這個系統比較多是需要 sequential access 還是 random access Contiguous allocation <font color = "red">需要事先宣告大小</font> ==support sequential access, random access== 不管是 sequential access 還是 random access，contiguous allocation 只需要一次 access 就能取得一個 block。因為我們可以直接把一個檔案的起始位置放在 memory 裡面，所以我們很容易可以計算任何第 i 個 Block 的位址，然後就能直接去讀取那個 block。 Contiguous allocation 適合 small files

在 <font color = "snake">multivariate linear regression</font> 中，我們會假設 output ==$r$== 可以被寫成一個 ++linear function++，也就是我們的 ++input variables $x_1,...,x_d$ 的 weighted sum，再加上 noise++。 其實在統計學的術語裡面，這應該要叫作 <font color = "snake">multiple regression</font>，<font color = "snake">multivariate</font> 是用在當我們有 multiple outputs 的情形。 總之，如果我們把上面文字的描述透過數學表示，即為： image 接下來，就像我們在筆記「4.6 Regression」中講過的，為了要 fit 這些 polynomial functions $g(\vec{x}^t|w_0,...,w_d)$ to data sets，也就是說：

binary features 在一些應用裡，我們的 attributes（即 features）為 discrete，為 $n$ 種不同的值中的其中一種。 舉例來說，某種 attribute 可能會是： $\text{color} \in {\text{red, blue, green, black}}$ $\text{pixel} \in {\text{on, off}}$ 我們來假設一個 attribute $x_j$ 是 binary（Bernoulli）的情形：

本節的內容不多，基本上都是前一節： 筆記「5.5 Multivariate Classification」 的整理與延伸，因此如果有沒特別說明的地方，基本上回頭看這篇筆記，就可以在裡面找到答案 :) discriminant function 在 simplicity 和 generality 之間的 tradeoff 在前一小節最後整理的表格裡，也就是這張表： image

我們以前學過： 在 classification 的問題裡，我們希望透過 sample 的 data 來對每個 class 找出一個適合的 function（叫做 discriminant function），來使得當我們有新的 input 時，我們可以代入這些 functions 裡，並藉由找出最大的 output 來決定要把這個新的 input 分類到哪個 class。 最初我們的討論都建立在 input 只是某個值（一維）的情況下，而在這個小節裡，我們要做的是延續前幾節對 multivariate 的介紹，來看看一個 $d$ 維的 random vector 要怎麼去做 classification。 也就是說，當 feature 很多時，要怎麼去分類我們的 input？ normal class conditional densitiy 定義

寫這篇的時候生病中，腦袋不清楚，忘記很多內容已經在其他筆記寫過了，不過反正也很簡短，就當作是重點整理好了。 不過 conditional distribution 的內容應該是沒有寫過，主要也是誤了講這個才回顧了一堆重複的內容，其他已經會了的話，可以跳著看這部分。 兩篇和這篇內容有重疊的筆記，可以交互參考： A.2.2 Joint Distribution and Density Functions 補充： Joint distribution functions 背景知識：joint / marginal distribution

本節內容完全對應參考資料中的網頁，基本上都是定義和證明，用來補充其它筆記中的定義、定理的證明。 證明我寫的基本上和網頁中的差不多，只是比較詳細，少數那裡省略沒證的我有自己證在這裡。 基本上都是數學，所以就保留使用英文了。 1 Random Vector random vector mean, variance 定義 <font color = "snake">Random vector</font> 也就是我們第五章中一直在用的 <font color = "snake">multivariate random variable</font>，它的 mean 和 variance 定義如下：