1A2B

2015年8月15日星期六

Machine Learnng 1.1 -- Perceptron -- 什麼是 machine learning 問題

如果有上過林軒田老師的課，他在課堂的一開始一定會先提到 perceptron learning algorithm (PLA)。這是一個最簡單，最好應用，涵蓋範圍可以很廣，但效果卻不會太差的演算法。我想在真正提到SVM之前，先用PLA來給大家進一步熟悉machine learning的問題。

我在上一個段落有說到machine learning的概念，這樣的概念我們可以用一個比較一般性的描述來表示。

為了找到未知的公式 $f: X \rightarrow Y$ ，我們必須要從資料集(Data set) $ D: (x_1,y_1) (x_2,y_2) ... (x_n,y_n) $ 中，利用演算法 $A$ 產生一個假說集 (Hypothesis set) $H: h_1(x), h_2(x) ...$ ，並想辦法從 $H$ 中挑一個我們心目中最接近 $f(x)$ 的假說，一般而言我們會用$g(x)$來表示那個從$H$雀屏中選的那個。

/* 以下廢話

上面那一段用白話文來說就可以講一大堆了，以前在看大學工數課本的時候，都覺得外國人寫的書廢話好多，我只要看得懂公式就好，不過這幾年下來，我有時候會覺得學數學的重點就是，可以從公式中領會出那些廢話。公式是一個結論，是思想的精華，不過對數學而言，我們需要花很多時間來思考問題，界定問題，這樣才能真正應用在這個世界上。

先來看 $f$ ，什麼叫做未知的公式，其實可以把它看作是一個最終目標，這樣的目標可以是一個判斷，一種預測，甚至是比較抽象的想法。比如說：

這張相片中有沒有人臉? (二元分類問題)
輸入：圖片
輸出：true / false

身高175公分的人走一步的距離大概是多少？ (回歸問題)
輸入：身高
輸出：步長

這位網路商城的使用者可能會喜歡哪種廣告？(比較抽象的問題)。
輸入：歷史紀錄
輸出：可能喜歡的廣告

這些問題是無法憑空找出答案的，不管是人也好，機器也好，要找出這些問題的答案都必須經過學習過程。學習就是透過資料、教材或範本找到答案，也就是說從一群資料中萃取出我們要的東西，那個萃取出來的公式一般我們會用 $g$ 來表示。

換句話說，這件事可以拆成兩件事來看 1)要如何利用手上的資料找出 $g$ ，並且 2)確保 $g$ 跟 $f$ 很接近。

1) 如何利用手上的資料找出 $g$:
這時後 $A$ 就出場了，我們可以用很多種方法來找 $g$，每一種都是 $A$ 的子集，這些方法作用在資料上，就會出現其對應的假說 $h$ ，每一種方法至少會有一種假說(註)，這些假說的集合就表示為 $H$。

每個 $h$ 的功用就是越來預測資料，資料是由一群這樣的東西 $ D: (x_1,y_1) (x_2,y_2) ... (x_n,y_n) $所組成的，其中的 $x$ 就是所謂的特徵，也就是上面的 "輸入" ，可以是圖片，可以是身高，可以是歷史紀錄或是任何想用來學習的特徵；而 $y$ 就是 "輸出"，也有人把他們叫做 "標籤" ，他標示著我們想要電腦學習的結果，也就是我們會希望那個好的 $h$ 會出現，並且讓所有的 $h(X)$ 都接近甚至等於 $Y$。

註：一般來說，我們會把同一種方法，但使用不同的參數的結果，定義為不同的 $h$，換句話說，一個 $a$ (俗稱演算法)，可能會產生多個 $h$。

2) 如何確保 $g$ 跟 $f$ 很接近:
在 $H$ 裡面，要知道其中的好壞很簡單，就是把所有在 $D$ 中的 $x_1, x_2, x_3 ...$ 都帶到 $h_i$, ( $i=1,2, ... ,n$ $假設有H中有n個假說$ ) 裡面，然後再將每一個輸出 $h_i(x_1)$, $h_i(x_2)$, $h_i(x_3)$, 與 $y_1, y_2, y_3...$ 比較錯誤率最低的，在小心 overfit(註) 的情況下，我們可以說 $g$ 接近 $f$，只要有類似的資料進來，我們就可以用手上的 $g$ 來完成 $f$ 所描述的問題。

註：overfit 是過度學習的意思，一般而言可以看做是不只有用的資料本身，連雜訊也完全學習。也就是說，雖然可以百分之百呈現當前的資料，但往往這個找到的 $g$ 是沒有應用價值的。

以上廢話 */

這就是我所知道的machine learning的問題，簡單用一句話來說明就是，如何從資料中找到我們心中想知道的答案。

2015年5月23日星期六

Python 慣用語

Good tips on writing in "native" python language.

http://seanlin.logdown.com/posts/239883-python-idioms

2015年5月22日星期五

穿戴式裝置的卡路里計算

最近整理了一些論文，主要的目的是該怎麼從穿戴式裝置算出卡路里。

這邊有一個假設，穿戴式裝置中的MEMS感測器只有加速計(accelerometer)，加速計可以做成計步器，而計算出的步數就可以拿來推卡路里。

以下是簡單的想法

加速計==> 計步器 ==> 步頻、步距、步數 ==> 卡路里

我們先來看卡路里的計算；在沒有心跳計的情況下，一般都用運動當量(METs)來推算。METs(kcal/kg/hr) 的定義是每公斤的人每小時運動可以消耗的卡路里，這是很多研究員做實驗出來的數據，他可以當作運動強度的參考值；換句話說就是，METs越大的運動，可以讓從事那個運動的人消耗越多卡路里，公式如下：

卡路里(kcal) = METs*體重(kg)*運動時間(hr)

在目前的應用情境裡面，我假設穿戴式裝置只能偵測走路或是跑步，所以METs的變化就會隨著速度而改變，在我整理了資料以後，歸納了下面速度與METs的關係：

speed(m/min)    METs
54              2.8
67              3
94              4.3
107             5
121             7
134             8.3
161             9.8
188             11
201             11.8
215             11.8
241             12.8
268             14.5
295             16
322             19
349             19.8
376             23

搭配上表，假設體重跟運動時間已知，求卡路里這個問題就可以被簡化成該如何從計步器的值算出移動速度。到這邊我們來一個國中就學過的簡單定義：

$$速度 = \frac{距離}{時間}$$

在運動時間已知的情況下，只要求出距離就可以了。計步器可以告訴我們，總共走的步數，而距離就可以用$$步數\times步距$$來表示，那步距該怎麼求呢？

在一定的速度下，人的步距可以用身高來決定，人越高、腳越長、跨步的距離當然也越長，而這個比例在1993年的時候由Y Hatano提出了一個概算；
$$男性: 步距 = 身高\times0.415$$
$$女性: 步距 = 身高\times0.412$$
不過事實上，步距會跟走路的速度有關，一般來說，速度越快，步距越長。

所以如果要算出精準的卡路里，步距還需要有另外的算法，這部分我會在其他的篇章介紹，在這邊先用身高的定值來計算吧！

到這邊，已經可以大約算出卡路里了，我來重頭整理一遍。

首先我們要從計步器的步數和步距算出總共的移動距離。

有距離以後，就可以跟運動時間相除得到平均速度。

利用平均速度就可以從表中得到這次運動的METs。

有 METs 體重運動時間就可以算出卡路里了。

2015年3月20日星期五

遵循REST原則設計API，卻覺得不滿足，怎麼辦?

突然想起了蘇慧倫的【滿足】，"你滿足了我不滿足~用什麼來彌補~"

設計web API時，遵循REST架構的好處很多，這邊就不多提了，這邊我想紀錄一下自己在設計過程中遇到的一些問題與思維。

借用Ruby on Rails實戰聖經裡的例子:

Helper	GET	POST	PATCH/PUT	DELETE
event_path(@event)	/events/1 show action		/events/1 update action	/events/1 destroy action
events_path	/events index action	/events create action

新增一筆事件時，我們用:

POST /events

要取得多筆事件時，我們用:

GET /events

問題來了，如果我們想要一次新增多筆事件時，該怎麼辦?

2015年2月10日星期二

Howto: methods of creating testing user data for benchmarking ejabberd

This article talks about methods I learnt to create testing users when I setup an ejabberd (XMPP service implemented in Erlang language) and tries to benchmark the performance my new setup.

When talking about the benchmark, the first step is always to have the testing data prepared. In our case, we need to prepare the user accounts with passwords just in order to allow testing clients to log in to the XMPP server and then we can start evaluating the performance by applying different configurations. Unfortunately, if you are using Mnesia as the database backend to store these information and you are unfamiliar with Erlang like I did. You probably don't know how to batch creating users in a short time.

The first and the most naive method to create the test user is to use the command ejabberdctl. This tool comes along with the ejabberd package when you installed (Assume we are using Ubuntu 12.04+/Debian 7) and allows you to talk to ejabberd through command line. One of the function is to to register user

sudo ejabberdctl register <username> <host> <password>

For example, if you want to create an account handsome@1a2b.com with password set as 1a2b. You can execute command

sudo ejabberdctl register handsome 1a2b.com 1a2b

And then it shall create an account for you immediately. But the problem to create account in this way is that it's very slow and you cannot speed up by executing multiple ejabberdctl command concurrently (it will crash). It took roughly 120 seconds to create a thousand accounts (Intel Core i7 2.8GHz, 8GB RAM) which is roughly 8 accounts per second. You can image how long it gonna take if you want to create more.

The second one is to create account by using the in-band registration extension which is supported by ejabberd. To enable the in-band registration, you need to

Modify /etc/ejabberd/ejabberd.cfg
{access, register, [{allow, all}]}.
{registration_timeout, infinity}.
and make sure mod_register is listed in modules.
Restart service: sudo ejabberd restart

And then you can use tsung to create the testing account with the following xml file (tsung is a tool used for testing http/xmpp performances which is also written in Erlang).

---

<?xml version="1.0"?>

<!DOCTYPE tsung SYSTEM "/usr/share/tsung/tsung-1.0.dtd">

</clients>

</servers>

<load>

</arrivalphase>

</load>

</options>

<match do="abort" when="match">error</match>

</request>

</request>

</session>

</sessions>

</tsung>

---
And then execute command: tsung -f create_user.xml start
If things working correctly, then you shall be able to have all user created.
Note, you have to set appropriate thresholds to throttle the concurrent connections established from tsung to ejabberd. Otherwise, part of the registration requests might fail. (and you have to do it all over again)

But still, I prefer the last method I tried to create the user. That is instead of registering XMPP user by using tsung. I ended up with writing a python script which uses xmpppy module to do the in-band user registration.
In this way, it's easy for you to create users with a simple script without worrying about first configuring tsung configuration xml file.

Below is a python code snippet I found at stackoverflow.
---

import xmpp

def register_user(jid, password):

jid=xmpp.protocol.JID(jid)

cli=xmpp.Client(jid.getDomain(), debug=[])

cli.connect()

# getRegInfo has a bug that puts the username as a direct child of the

# IQ, instead of inside the query element. The below will work, but

# won't return an error when the user is known, however the register

# call will return the error.

xmpp.features.getRegInfo(cli,

jid.getDomain(),

sync=True)

if xmpp.features.register(cli,

jid.getDomain(),

{'username':jid.getNode(),

'password':password}):

return 0

else:

print("Error registering: %s\n" % jid)

return -1
---
I modify the code snippet as function and run the function with multiple threads. In this way I can create a large amount of user accounts in a more reliable way and shorter time.

2015年1月20日星期二

Machine Learning 0 -- What is SVM?

前面的課程主要是在講SVM(Support Vector Machine)，本來這篇兩個禮拜前就應該發的，不過很多事讓我一拖再拖，我希望以後可以以兩個禮拜一篇的速度完成，有點像是自己對這個領域的小筆記。

SVM 是一種 Machine Learning 的演算法，照字面上的意思來看，就是"利用 support vector 來分類的 machine"。

在了解這句話之前，我們先來看一個簡單的圖

取樣資料

一般來說，machine learning 的目的是從取樣資料(手上有的看得到的資料)中預測一個可以描述全域資料(不知道長怎樣，不過大概跟取樣資料長得很像)的方程式 $f(x)$，換句話說$f(x)$是學習的最終目標；以上圖為例，我們可以用任意直線、圓錐曲線甚至是不規則圖形來分開他們，每一個圖形都是一個假說(hypothesis)，以$h_i(x)$表示，當我們使用不同的 machine learning 演算法 (或者是使用同一種演算法但不同參數)，就是用不同的選妃標準來選擇一個最適合的假說，被挑選出來的妃子假說我們會讓他進化成皇后$g(x)$，$g(x)$就是我們的預測值，我們會希望$g(x)$非常接近~~世界上最完美的皇后~~$f(x)$。

圖上的三條線都可以分開兩群資料，所以我們都可以把它們看成假說。

現在我們回到那句話："SVM 是利用 support vector 來分類的 machine"。SVM 挑選假說的方式就是去尋找 support vector，並且以 support vector 為基準來分類。這句話從字面上完全無法了解它的意函，所以有另外一個比較通俗的說法:

找到一條可以分類的線，而且這條線所在的區域擁有兩群資料間最大的邊界。

因為很重要所以要說三次

如下圖，如果假說都是直線的話，SVM 就是要找到一條線離左右兩群資料間的區域最大。

中間的區域就像是緩衝區一樣，到左右兩邊的緩衝區越大，就有很大的機會容忍取樣上的誤差。

好啦，現在問題就來了，兩群資料可以分就好幹嘛這麼龜毛，還要找最大的邊界？

其實這很直覺！撇開數學（shatter, vc dimension）不談，要確保 machine learning 出來的結果正確，最重要的就是兩件事，1）取樣的資料要好。2）演算法要挑剔。

對我個人來說，好的取樣資料是最重要的，因為我們不可能把世界上所有的資料都拿來用，所以我們只能取其中有代表性的資料出來算，如果取得不好，就算使用世界上最強的演算法也算不出符合原始資料的結果。就像是要去分析交大學生的習慣，如果全部都在竹軒、女二舍裡面調查的話，就會有交大是女校的錯覺，在這樣的錯覺下，任何對於此資料做出的分析找到的$g(x)$一定會跟$f(x)$相去甚遠。

不過就算是再好的取樣，取出的資料也不能100%代表著母體，而這時候使用演算法就要特別小心。在 machine learning 裡面，演算法決定了$h_i(x)$的產生方式，以及選擇$g(x)$的標準。如果產生$h_i(x)$的方式不挑剔，不管三七二十一，只要能夠把當前這筆資料完美的處理就好，很容易會學過頭了，也就是說好得學壞得也學，連那些誤差都學得淋漓盡致，一般正式的文章裏面都把這個叫做 over fitting。為了避免 over fitting，最簡單的方式就是對演算法設下條件，而SVM的條件就是，要找最大的邊界。

到這邊就是簡單的 machine learning 以及 SVM 的概念。

2015年1月18日星期日

SELinux for Android 簡介

最近在看 SELinux for Android 的資料，發現很少中文的解說，所以想說順便整理一篇。

在了解本篇主題以前，可以先了解一下什麼是 SELinux，我建議可以看這篇網誌，解釋得滿清楚的。

再來，這篇主要的內容會是解釋這個投影片，這是 NSA(美國國家安全局) 對於 SELinux for Android 做的演講。好，正題開始。

SELinux 是要在原本Linux的 DAC (Discretionary Access Control) 上面，加上 MAC (Mandatory Access Control) 的架構。主要的目的是要避免誤用以導致系統損毀，要體驗的話其實很簡單，如果手邊有 root 的 Android 機器的話，可以發現就算用 root 的權限也沒有辦法去修改 system/ 下面的 init*.rc 的檔案內容，這就是因為 SELinux ~~在作祟~~擋住了寫入的權限。

platform/external/sepolicy/domain.te

# Nothing should be writing to files in the rootfs.
neverallow { domain -recovery } rootfs:file { create write setattr relabelto append unlink link rename };

上面那段 policy 的目的是在 domain 中除了 recovery 外，使用被標(labeled)成 rootfs 的檔案(file) 都不被允許(neverallow) 這一長串 { create write setattr relabelto append unlink link rename } 裡面的事情。

再來，我們來看，rootfs 的定義：

platform/external/sepolicy/file_contexts

# Root
/          u:object_r:rootfs:s0

# Data files
/adb_keys               u:object_r:adb_keys_file:s0 #這行不是rootfs
/default\.prop          u:object_r:rootfs:s0
/fstab\..*              u:object_r:rootfs:s0
/init\..*               u:object_r:rootfs:s0
/res(/.*)?              u:object_r:rootfs:s0
/ueventd\..*            u:object_r:rootfs:s0

# Executablesˇ
/charger                u:object_r:rootfs:s0
/init                   u:object_r:rootfs:s0
/sbin(/.*)?             u:object_r:rootfs:s0

# Empty directories
/lost\+found            u:object_r:rootfs:s0
/proc                   u:object_r:rootfs:s0

# SELinux policy files
/file_contexts          u:object_r:rootfs:s0
/property_contexts      u:object_r:rootfs:s0
/seapp_contexts         u:object_r:rootfs:s0
/sepolicy               u:object_r:rootfs:s0

也就是說在這些檔案目錄下的東西，都不被允許 { create write setattr relabelto append unlink link rename }，所以也沒有辦法在shell底下的根目錄新增檔案。而這就是SELinux的定義，可以避免誤用而導致系統損毀。

在看這些 rule 的時候，主要是看兩種檔案，一種是 *.te ，一種是 *_context。*.te 裡面記載著各種 rule；而 *_context 的目的是把檔案貼標籤 (labeling)。以上面的例子來看，rootfs 這個標籤在 domain.te 裡面，被規定了不能 { create write setattr relabelto append unlink link rename } ，而 rootfs 則是在 file_context 裡面跟真實的檔案目錄連結，只要抓到這個原則就很容易看懂這些 policy 之間的關係。

在 source code 裡面，這些檔案通常會被放在兩個地方：

platform/external/sepolicy
device/<vendor>/<product>/sepolicy

platform/external/sepolicy 可ˇ已把它看作是 AOSP 原生的 policy，基本上這些檔案最好不要修改；要修改的話，可以加在 device/<vendor>/<product>/sepolicy 裡面。在 platform/external/sepolicyREADME 有詳細說明該如何修改，說明如下：

Eg.) Suppose the following:
     BOARD_SEPOLICY_DIRS += X Y
     BOARD_SEPOLICY_REPLACE += A
     BOARD_SEPOLICY_IGNORE += X/A

     Directories X and Y contain A.

     The resulting policy is created by using Y/A only, thus X/A was
     ignored.

Example BoardConfig.mk Usage:
From the Tuna device BoardConfig.mk, device/samsung/tuna/BoardConfig.mk

BOARD_SEPOLICY_DIRS += \
        device/samsung/tuna/sepolicy

BOARD_SEPOLICY_UNION += \
        genfs_contexts \
        file_contexts \
        sepolicy.te

最後，投影片裡面還有提到， platform/external/sepolicy 裡面大概有哪些檔案。檔案分成:

*.te

定義一些全域的 rule: domain.te, app.te
宣告 device 與 file 的類型 (type): device.te, file.te
單獨的 rule : e.g. installd.te

*_context

file_contexts: labeling 檔案目錄
property_contexts: labeling init 裡面的 property
seapp_contexts:

mac_permissions.xml

定義特定App的 seinfo，這個 seinfo 會在 seapp_contexs 裡面用到。

有這些架構的概念以後，應該就可以順利地讀懂延伸閱讀裡面的東西。

延伸閱讀：

SELinux concepts: Android 官網的介紹。
An SElinux module:[1] [2] SELimux policy 跟 labeling 的詳解
SELinux Permmision: permission 的介紹

訂閱：文章 ( Atom )

1A2B

網頁

2015年8月15日星期六

Machine Learnng 1.1 -- Perceptron -- 什麼是 machine learning 問題

2015年5月23日星期六

Python 慣用語

2015年5月22日星期五

穿戴式裝置的卡路里計算

2015年3月20日星期五

遵循REST原則設計API，卻覺得不滿足，怎麼辦?

2015年2月10日星期二

Howto: methods of creating testing user data for benchmarking ejabberd

2015年1月20日星期二

Machine Learning 0 -- What is SVM?

2015年1月18日星期日

SELinux for Android 簡介

CC License

網頁

2015年8月15日 星期六

Machine Learnng 1.1 -- Perceptron -- 什麼是 machine learning 問題

2015年5月23日 星期六

Python 慣用語

2015年5月22日 星期五

穿戴式裝置的卡路里計算

2015年3月20日 星期五

遵循REST原則設計API，卻覺得不滿足，怎麼辦?

2015年2月10日 星期二

Howto: methods of creating testing user data for benchmarking ejabberd

2015年1月20日 星期二

Machine Learning 0 -- What is SVM?

2015年1月18日 星期日

SELinux for Android 簡介

CC License

2015年8月15日星期六

2015年5月23日星期六

2015年5月22日星期五

2015年3月20日星期五

2015年2月10日星期二

2015年1月20日星期二

2015年1月18日星期日