Friday, September 22, 2017

AI從頭學(目錄)

AI從頭學(目錄)

2016/12/08

1. AI從頭學
2. Big Data(目錄)
3. Cloud(目錄)



AI從頭學(代序):The Road to Deep Learning 

AI從頭學(一):文獻回顧

AI從頭學(二):Popular Deep Learning Software Tools

AI從頭學(三):Popular Deep Learning Hardware Tools

AI從頭學(四):AD and LeNet

AI從頭學(五):AD and Python

AI從頭學(六):The Net

AI從頭學(七):AD and Python from Jason

AI從頭學(八):The Net from Mark

AI從頭學(九):Back Propagation

AI從頭學(一0):Automatic Differentiation

AI從頭學(一一):A Glance at Deep Learning

AI從頭學(一二):LeNet

AI從頭學(一三):LeNet - F6

AI從頭學(一四):Recommender

AI從頭學(一五):Deep Learning,How?

AI從頭學(一六):Deep Learning,What?

AI從頭學(一七):Shallow Learning 

AI從頭學(一八):Convolutional Neural Network

AI從頭學(一九):Recurrent Neural Network

AI從頭學(二0):Deep Learning,Hot 

AI從頭學(二一):A Glance at Deep Reinforcement Learning 

AI從頭學(二二):Azure Machine Learning - Clustering

AI從頭學(二三):CNN - Kernel Training

AI從頭學(二四):CNN - Kernel Visualizing

AI從頭學(二五):ZFNet

AI從頭學(二六):Aja Huang

AI從頭學(二七):AlexNet

AI從頭學(二八):Network in Network 

AI從頭學(二九):GoogLeNet

AI從頭學(三0):Conv1

AI從頭學(三一):Inception

AI從頭學(三二):DPM

AI從頭學(三三):Weight Decay

AI從頭學(三四):Complete Works

-----

FB社團:AI 

-----

1.1. LeNet實作團(目錄)
1.2. DRL實作團(目錄)
1.3. Lab DRL(目錄)
1.4. 每天來一點 Deep Learning(目錄)
1.5. Python Spark ML(目錄) 

AI從頭學():Highlight

AI從頭學():Highlight

2017/09/05

施工中...

1 最基本的
1.1 CNN
1.2 RNN
1.3 Overview

2. CNN 的應用
2.1 R-CNN
2.2 GAN

3. Reinforcement Learning 強化學習
3.1 Game
3.2 Go

4. RNN的應用
4.1 NTM

5. 正規化與最佳化
5.1 Regularization
5.2 Optimization

6. 自編碼器與受限玻爾茲曼機
6.1 AE
6.2 RBM

7. 各種應用
7.1 Robotics
7.2 Fintech

-----

1.1 CNN

◎ LeNet。第一個「成功」應用於 MNIST 手寫字元集的 CNN。
LeCun, Yann, et al. "Gradient-based learning applied to document recognition." Proceedings of the IEEE 86.11 (1998): 2278-2324.

◎ AlexNet 跟 VGGNet 都引用的論文。第一篇使用 GPU 的 CNN?本篇加寬失敗,VGGNet 加深成功。
Ciresan, Dan C., et al. "Flexible, high performance convolutional neural networks for image classification." IJCAI Proceedings-International Joint Conference on Artificial Intelligence. Vol. 22. No. 1. 2011.

◎ AlexNet
Krizhevsky, Alex, Ilya Sutskever, and Geoffrey E. Hinton. "Imagenet classification with deep convolutional neural networks." Advances in neural information processing systems. 2012.

◎ ZFNet。微調 AlexNet 的參數。特徵可視化。
Zeiler, Matthew D., and Rob Fergus. "Visualizing and understanding convolutional networks." European conference on computer vision. Springer, Cham, 2014.

◎ VGGNet。conv5 分解成兩個 conv3,然後不斷加深。
Simonyan, Karen, and Andrew Zisserman. "Very deep convolutional networks for large-scale image recognition." arXiv preprint arXiv:1409.1556 (2014).

◎ NIN。GoogLeNet 的靈感來源。1 x 1 convolution。
Lin, Min, Qiang Chen, and Shuicheng Yan. "Network in network." arXiv preprint arXiv:1312.4400 (2013).

◎ GoogLeNet 的架構,Inception 的靈感來源。
Arora, Sanjeev, et al. "Provable bounds for learning some deep representations." International Conference on Machine Learning. 2014.

◎ GoogLeNet。
Szegedy, Christian, et al. "Going deeper with convolutions." Proceedings of the IEEE conference on computer vision and pattern recognition. 2015.

◎ GoogLeNet 系列。Inception v2。BN。
Ioffe, Sergey, and Christian Szegedy. "Batch normalization: Accelerating deep network training by reducing internal covariate shift." International Conference on Machine Learning. 2015.
 
◎ GoogLeNet 系列。Inception v3。
Szegedy, Christian, et al. "Rethinking the inception architecture for computer vision." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.

◎ GoogLeNet 系列。Inception v4。結合 ResNet。
Szegedy, Christian, et al. "Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning." AAAI. 2017.

◎ ResNet。繼承 VGGNet 的架構。
He, Kaiming, et al. "Deep residual learning for image recognition." Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.
 
◎ ResNet 的理論基礎。
He, Kaiming, et al. "Identity mappings in deep residual networks." European Conference on Computer Vision. Springer International Publishing, 2016.

◎ DenseNet。
Huang, Gao, et al. "Densely connected convolutional networks." arXiv preprint arXiv:1608.06993 (2016).

-----

1.2 RNN

◎ LSTM
Hochreiter, Sepp, and Jürgen Schmidhuber. "Long short-term memory." Neural computation 9.8 (1997): 1735-1780.
 
-----

1.3 Overview

◎ 如果你懂 CNN 與 RNN 之後,這篇可以看一下。如果不懂,還是可以看,領略一下 Deep Learning 在應用面的「威力」。
LeCun, Yann, Yoshua Bengio, and Geoffrey Hinton. "Deep learning." Nature 521.7553 (2015): 436-444.

◎ 這本「很棒」,也「有點難」。讀論文的時候,可以來參考相關的章節。
Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.

◎ 偏「歷史性」的回顧。不過如果你不懂 CNN、RNN 等,會不知所云。
Schmidhuber, Jürgen. "Deep learning in neural networks: An overview." Neural networks 61 (2015): 85-117.

-----

2.1. R-CNN

◎ Pilot of R-CNN。
Szegedy, Christian, Alexander Toshev, and Dumitru Erhan. "Deep neural networks for object detection." Advances in neural information processing systems. 2013.

◎ R-CNN
Girshick, Ross, et al. "Rich feature hierarchies for accurate object detection and semantic segmentation." Proceedings of the IEEE conference on computer vision and pattern recognition. 2014.

◎ Fast R-CNN。
Girshick, Ross. "Fast R-CNN." Proceedings of the IEEE international conference on computer vision. 2015.

◎ Faster R-CNN。
Ren, Shaoqing, et al. "Faster R-CNN: Towards real-time object detection with region proposal networks." Advances in neural information processing systems. 2015.

◎ YOLO。
Redmon, Joseph, et al. "You only look once: Unified, real-time object detection." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.

◎ SSD。
Liu, Wei, et al. "SSD: Single shot multibox detector." European conference on computer vision. Springer, Cham, 2016.

◎ Mask R-CNN。
He, Kaiming, et al. "Mask R-CNN." arXiv preprint arXiv:1703.06870 (2017).

-----

2.2 GAN

◎ GAN。
Goodfellow, Ian, et al. "Generative adversarial nets." Advances in neural information processing systems. 2014.

◎ Wasserstein GAN - 1。
Arjovsky, Martin, and Léon Bottou. "Towards principled methods for training generative adversarial networks." arXiv preprint arXiv:1701.04862 (2017).

◎ Wasserstein GAN - 2。
Arjovsky, Martin, Soumith Chintala, and Léon Bottou. "Wasserstein gan." arXiv preprint arXiv:1701.07875 (2017).

◎ Wasserstein GAN - 3。
Gulrajani, Ishaan, et al. "Improved training of wasserstein gans." arXiv preprint arXiv:1704.00028 (2017).

-----

3. Reinforcement Learning

◎ RL 的經典書。
Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. (2016): 424.
http://incompleteideas.net/sutton/book/bookdraft2016sep.pdf

-----

3.1 Game

◎ DQN
Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." Nature 518.7540 (2015): 529-533.

◎ A3C 
Mnih, Volodymyr, et al. "Asynchronous methods for deep reinforcement learning." International Conference on Machine Learning. 2016.

◎ UNREAL
Jaderberg, Max, et al. "Reinforcement learning with unsupervised auxiliary tasks." arXiv preprint arXiv:1611.05397 (2016).

-----

3.2 Go

◎ 1994
Schraudolph, Nicol N., Peter Dayan, and Terrence J. Sejnowski. "Temporal difference learning of position evaluation in the game of Go." Advances in Neural Information Processing Systems. 1994.

◎ 1996
Enzenberger, Markus. "The integration of a priori knowledge into a Go playing neural network." URL: http://www. markus-enzenberger. de/neurogo. html (1996).

◎ 2002
Van Der Werf, Erik, et al. "Local move prediction in Go." International Conference on Computers and Games. Springer, Berlin, Heidelberg, 2002.

◎ 2004
Enzenberger, Markus. "Evaluation in Go by a neural network using soft segmentation." Advances in Computer Games. Springer US, 2004. 97-108.

◎ 2008
Sutskever, Ilya, and Vinod Nair. "Mimicking go experts with convolutional neural networks." Artificial Neural Networks-ICANN 2008 (2008): 101-110.

◎ 2014
Maddison, Chris J., et al. "Move evaluation in go using deep convolutional neural networks." arXiv preprint arXiv:1412.6564 (2014).

◎ 2015
Clark, Christopher, and Amos Storkey. "Training deep convolutional neural networks to play go." International Conference on Machine Learning. 2015.

◎ 2016 AlphaGo。
Silver, David, et al. "Mastering the game of Go with deep neural networks and tree search." Nature 529.7587 (2016): 484-489.

-----

4.1 NTM

◎ NTM
Graves, Alex, Greg Wayne, and Ivo Danihelka. "Neural turing machines." arXiv preprint arXiv:1410.5401 (2014).
 
◎ 
Graves, Alex, et al. "Hybrid computing using a neural network with dynamic external memory." Nature 538.7626 (2016): 471-476.

◎ 
Olah, Chris, and Shan Carter. "Attention and augmented recurrent neural networks." Distill 1.9 (2016): e1.

-----

5.1 Regularization

◎ Weight decay。
Krogh, Anders, and John A. Hertz. "A simple weight decay can improve generalization." Advances in neural information processing systems. 1992.
 
◎ Dropout。
Srivastava, Nitish, et al. "Dropout: a simple way to prevent neural networks from overfitting." Journal of machine learning research 15.1 (2014): 1929-1958.

◎ Batch Normalization。
Ioffe, Sergey, and Christian Szegedy. "Batch normalization: Accelerating deep network training by reducing internal covariate shift." International Conference on Machine Learning. 2015.

-----

5.2 Optimization

◎ Overview of optimization
Ruder, Sebastian. "An overview of gradient descent optimization algorithms." arXiv preprint arXiv:1609.04747 (2016).
 
◎ 1 SGD
Bottou, Léon. "Stochastic gradient descent tricks." Neural networks: Tricks of the trade. Springer Berlin Heidelberg, 2012. 421-436.

◎ 2 Momentum
Polyak, Boris T. "Some methods of speeding up the convergence of iteration methods." USSR Computational Mathematics and Mathematical Physics 4.5 (1964): 1-17.

◎ 3 NAG
Sutskever, Ilya, et al. "On the importance of initialization and momentum in deep learning." International conference on machine learning. 2013.

◎ 4 AdaGrad
Duchi, John, Elad Hazan, and Yoram Singer. "Adaptive subgradient methods for online learning and stochastic optimization." Journal of Machine Learning Research 12.Jul (2011): 2121-2159.
 
◎ 5 AdaADelta
Zeiler, Matthew D. "ADADELTA: an adaptive learning rate method." arXiv preprint arXiv:1212.5701 (2012).

◎ 6 RMSProp
Hinton, G., N. Srivastava, and K. Swersky. "RMSProp: Divide the gradient by a running average of its recent magnitude." Neural networks for machine learning, Coursera lecture 6e (2012).

◎ 7 Adam
Kingma, Diederik, and Jimmy Ba. "Adam: A method for stochastic optimization." arXiv preprint arXiv:1412.6980 (2014).

-----

7.1 Robotics


Levine, Sergey, et al. "End-to-end training of deep visuomotor policies." Journal of Machine Learning Research 17.39 (2016): 1-40.

-----

7.2 Fintech

◎ Machine Learning
Cavalcante, Rodolfo C., et al. "Computational intelligence and financial markets: A survey and future directions." Expert Systems with Applications 55 (2016): 194-211.

◎ ANN
Tkáč, Michal, and Robert Verner. "Artificial neural networks in business: Two decades of research." Applied Soft Computing 38 (2016): 788-804.

◎ Deep Learning
Chong, Eunsuk, Chulwoo Han, and Frank C. Park. "Deep learning networks for stock market analysis and prediction: Methodology, data representations, and case studies." Expert Systems with Applications 83 (2017): 187-205.

AI創業日記(目錄)

AI創業日記(目錄)

2017/08/10
 
-----


-----

(一):音樂生理學

Thursday, September 21, 2017

AI創業日記(一):音樂生理學

AI創業日記(一):音樂生理學

2017/09/21

前言:

音樂生理學,從2008到今年2017,前前後後,我也做了超過十一年了!最近為了創業需要,我把做的研究介紹一下,主要是過程的回顧,細節則請參考論文。

-----

Summary:

最早,這個題目是碩士班學弟做的 [1], [2],後來我把數據進一步分析,並且建了幾個模型 [3]-[5]。

博士班,只做幾個模型,稍嫌薄弱。我自己也做了不少實驗,其他的研究成果包含靜止時的 Heart rate variability (HRV),心率變異性分析 [6], [7],各種不同速度的音樂的影響 [8],由於實驗室裡有醫生同學,所以還做了音樂對於植物人的影響 [9], [10]。

另外還有偵測心率的 IC,這個也是學弟做的,我負責投論文 [11], [12]。

-----

Outline

1. Model
2. Rest
3. Tempo
4. Vegetative State
5. ECG Chip

-----

1. Model

2005 乙酉年,我「暫時」離開了電子業,一邊休養生息,一邊想著下一步要怎麼走。

這時好友已經結束國防役的工作,到交大教書。我除了每天騎腳踏車,也經常到交大 meeting。說起來還蠻有緣的,我在業界做過 CD-ROM、MP3、DSC 的 F/W,屬於多媒體的系統整合,好友做的是影音壓縮,屬於核心演算法。下一步,我們則一致看好生醫工程。

學弟做了一個嘗試,他設計了一個音樂實驗,受測者一邊聽音樂,一邊量心電圖,觀察到的實驗結果是:在聽過快而單調的節奏之後,人會感到比平常休息時更放鬆。由於 SDNN (俗稱 HRV,代表循環系統的活性)同時也下降,我把這個現象翻譯成白話,即是:聽完搖滾樂之後會讓人很放鬆,放鬆到快「掛掉」的感覺 [1]。伴隨著實驗還做了一個 proto-type,可以一邊播音樂一邊顯示心跳的波型,是個空殼子,裡面沒有分析用的演算法,不過意思到了 [2]。

我將學弟的分析加上大小鼓的數目,建了一個模型,投上 ISCAS 2009 [3],也考上了博士班。模型後來把鼓聲量化成音量 [4],後來寫了程式把手動建模改成機器建模,並附上統計分析,是我的主要研究 [5]。本論文在 2016年被 Nature 集團的期刊引用。

整個精神如圖1所示。綠色代表音樂訊號。紅色代表人的神經系統與循環系統。白色則代表生理訊號。白話的說法是,你聽了音樂,大腦感受到音樂,然後透過自主神經系統改變心跳、血壓、體溫等。如果你能掌握音樂如何對應到生理訊號,那麼,理論上,你想讓人亢奮或放鬆,等等,都可以透過音樂達成。

提升睡眠品質是其中主要的應用。

-----


Fig. 1. Music physiology [3].

-----

2. Rest

後來我做了不少實驗,觀察休息狀態的心電圖變化。學弟「貓耳」幫忙分析資料,出力甚多 [6], [7]。這部分比較專業,感興趣的人應該不多,就帶過。

-----

3. Tempo

音樂實驗也做了不少,其中一個觀察到一個有趣的現象:假設以 SDNN 代表生理上對音樂的喜好值,則人們偏好稍快的節奏與稍慢的節奏。對應到一般的音樂資料庫,稍快的歌曲跟稍慢的歌曲數目也偏多 [8]。

這給我們一個啟示:音樂的心理感受,是「有可能」透過生理訊號來量化的!

-----

4. Vegetative State

由於實驗室有醫生來讀博士班,他的患者中風後長期昏迷,我幫忙設計了實驗,根據我對音樂的瞭解,選了馬勒的第二號交響曲「復活」,讓患者長期聆聽。幾個月以後,患者家屬把療程改為高壓氧治療。

有點可惜,因為後來分析數據,在實驗後期已經有幾個指標顯示有明顯的改善。這個實驗後來分別投上 ISCAS 2010 [9] 與 EMBS 2011 [10]。也讓另一位同學順利考上博士班。

這邊提了幾次 ISCAS,這個會議論文在系上被認定可算畢業點數的。EMBS 則是生醫工程界最大型的會議。[8] 也是投上 EMBS 2011。

-----

5. ECG Chip

晶片是學弟做的,我則負責投稿,從會議 [11] 一直投到期刊 [12],我也越來越會寫論文。

-----

結論:

寫完這個,可以看到實驗室的生態是分工合作,有人做實驗、開 chip,有人分析數據,有人寫論文。

我在博士班最主要的研究是 [5],研究要商業化、變成一家公司,這又跟拿學位完全不同,且聽下回分解。

-----

References

[1] Lin, Shih-Hsiang, et al. "A study of the relationship between two musical rhythm characteristics and heart rate variability (HRV)." BioMedical Engineering and Informatics, 2008. BMEI 2008. International Conference on. Vol. 2. IEEE, 2008.

[2] Huang, Yu-Chieh, et al. "A biomedical entertainment platform design based on musical rhythm characteristics and heart rate variability (HRV)." Multimedia and Expo, 2008 IEEE International Conference on. IEEE, 2008.

[3] Wang, Hui-Min, et al. "A computational model of the relationship between musical rhythm and heart rhythm." Circuits and Systems, 2009. ISCAS 2009. IEEE International Symposium on. IEEE, 2009.

[4] Wang, Hui-Min, et al. "A physiological valence/arousal model from musical rhythm to heart rhythm." Circuits and Systems (ISCAS), 2011 IEEE International Symposium on. IEEE, 2011.

[5] Wang, Hui-Min, and Sheng-Chieh Huang. "Musical rhythms affect heart rate variability: Algorithm and models." Advances in Electrical Engineering 2014 (2014).

[6] Lee, Yaw-Chern, Hui-Min Wang, and Sheng-Chieh Huang. "Heart Rate Variance and Autonomic Responses in Young Adult Males." Computer Modeling and Simulation (EMS), 2010 Fourth UKSim European Symposium on. IEEE, 2010.

[7] Wang, Hui-Min, and Sheng-Chieh Huang. "SDNN/RMSSD as a surrogate for LF/HF: a revised investigation." Modelling and Simulation in Engineering 2012 (2012): 16.

[8] Shih, Yi-Sen, et al. "Twin-peak effect in both cardiac response and tempo of popular music." Engineering in Medicine and Biology Society, EMBC, 2011 Annual International Conference of the IEEE. IEEE, 2011.

[9] Yen, Brad S., et al. "The relationship between music processing and electrocardiogram (ECG) in vegetative state (VS)." Circuits and Systems (ISCAS), Proceedings of 2010 IEEE International Symposium on. IEEE, 2010.

[10] Lee, Yaw-Chern, et al. "HRV response of vegetative state patient with music therapy." Engineering in Medicine and Biology Society, EMBC, 2011 Annual International Conference of the IEEE. IEEE, 2011.

-----

[11] Wang, Hui-Min, et al. "A±6ms-accuracy, 0.68 mm2, and 2.21 µW QRS detection ASIC." Circuits and Systems (ISCAS), 2010 IEEE International Symposium on. IEEE, 2010.

[12] Huang, Sheng-Chieh, Hui-Min Wang, and Wei-Yu Chen. "A±6ms-accuracy, 0.68 mm2, and 2.21 µW QRS detection ASIC." VLSI Design 2012 (2012): 20.

Python Spark ML(目錄)

Python Spark ML(目錄)

2017/09/04

 
Python Spark ML(一):參加辦法

Python Spark ML(二):Machine Learning

Python Spark ML(三):Decision Tree Survey  

Python Spark ML(四):Decision Tree Survey - 資料補充

Python Spark ML(五):Decision Tree Survey - 問題討論

Python Spark ML(六):Decision Tree Algorithm Survey

Python Spark ML(七):Python Hadoop Spark 

跑步(一00):20圈

跑步(一00):20圈

2017/09/20

熱身2,跑(5*4)。

-----

熱身完就穿上運動鞋,似乎這樣對膝蓋負擔較小。

Monday, September 18, 2017

Python Spark ML(七):Python Hadoop Spark

Python Spark ML(七):Python Hadoop Spark

2017/09/18

本次作業:

閱讀 [2] 之後,將第一章的內容,摘要至 GitHub。可參考 [3] 或其他網路資料。
https://www.facebook.com/groups/pythontw/permalink/10156895096858438/

前言:

針對學員的反應,本活動決定將第一部份決策樹的理論與 Python 實作,移到後面。

目前改為從第二部分,PySpark 在 Windows 的環境架設為主。這個部分有點繁瑣,然而,如果要跑 Spark 的 ML,不先架設環境,也無法進行。

還好書上寫的還蠻清楚仔細的,如果同學交作業的反應還不錯的話,我「大約」一週會來貼一下作業,請同學發表自己的上機心得。

圖一其實是本活動的核心概念,解說已經在 [3] 裡面了。

您想自己解說一遍圖一嗎?:)

-----

課程大綱:

(一)
Decision Tree Theory
Python Decision Tree Lab

(二)
1 ~ 9

一到九章,主要是 Hadoop、Spark、Python 環境的架設。

(三)
10, 11

第十章,RDD,是 Spark MLlib 的資料格式。

(四)
13, 17, 18

Spark MLlib 決策樹二元分類、決策樹多元分類、決策樹迴歸分析。

(五)
19

第十九章,DataFrame,是 Spark ML Pipeline 的資料格式。 

(六)
20, 21, 22

Spark ML Pipeline 決策樹二元分類、決策樹多元分類、決策樹迴歸分析。

(七)
14, 15, 16

Logistic Regression、SVM、Naive Bayes。

(八)
12

Recommender。

-----


Fig. 1. Future of Spark [1].



Fig. 2. Python+Spark 2.0+Hadoop 機器學習與大數據分析實戰 [2]。

-----

References

[1] 使用Python開發Spark 2.0 +Hadoop機器學習與大數據分析 _ Python+Spark+Hadoop 機器學習與大數據分析實戰
http://pythonsparkhadoop.blogspot.tw/2016/10/pythonspark-20-hadoop.html 
 
[2] 書名:Python+Spark 2.0+Hadoop 機器學習與大數據分析實戰,ISBN:9864341537,作者:林大貴,出版社:博碩,出版日期:2016-10-03.
http://pythonsparkhadoop.blogspot.tw/2016/10/pythonspark-20hadoop.html 

[3] Big Data(目錄)
http://hemingwang.blogspot.tw/2017/08/big-data.html

跑步(九九):20圈

跑步(九九):20圈

2017/09/17

熱身2,跑(5*4)。

-----

換到下午跑。果然早上後半段跑不動是因為沒吃早餐就跑。一萬是有點多。

Wednesday, September 13, 2017

Python Spark ML():Decision Tree Algorithm - C4.5

Python Spark ML():Decision Tree Algorithm - C4.5

2017/09/13

施工中...

-----

References

[1] Hssina, Badr, et al. "A comparative study of decision tree ID3 and C4. 5." International Journal of Advanced Computer Science and Applications 4.2 (2014): 13-19.

Python Spark ML():Decision Tree - Missing Values

Python Spark ML():Decision Tree - Missing Values

2017/09/13

施工中...



 -----


Fig. 1. Comparison of classification tree methods [2].
 
-----

w (probability weights) - C4.5
s (surrogate splits) - CART
b (missing value branch) - CHAID
i (missing value imputation), s - CRUISE
m (missing value category) - GUIDE
i (missing value imputation) - GUEST
 
-----

References

[1] Python Spark ML(六):Decision Tree Algorithm Survey
http://hemingwang.blogspot.tw/2017/09/python-spark-mldecision-tree-algorithm.html

[2] Loh, Wei‐Yin. "Classification and regression trees." Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1.1 (2011): 14-23.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.364.9647&rep=rep1&type=pdf 

[3] python_spark_ml homework 4  Decision Tree Syntax · mirage7714_python_spark_ml Wiki · GitHub
https://github.com/mirage7714/python_spark_ml/wiki/python_spark_ml-homework-4:-Decision-Tree-Syntax?fref=gc&dti=197223143437

[4] 决策树会有哪些特性? - 简书
http://www.jianshu.com/p/338939130b24 

[5] 遺漏值 (Analysis Services - 資料採礦) 
https://msdn.microsoft.com/zh-tw/library/cc280406(v=sql.120).aspx

[6] RPubs - R筆記–(10)遺漏值處理(Missing Value)
http://rpubs.com/skydome20/R-Note10-Missing_Value

[7] Tutorial on 5 Powerful R Packages used for imputing missing values
https://www.analyticsvidhya.com/blog/2016/03/tutorial-powerful-packages-imputing-missing-values/

[8] Saar-Tsechansky, Maytal, and Foster Provost. "Handling missing values when applying classification models." Journal of machine learning research 8.Jul (2007): 1623-1657.
http://jmlr.csail.mit.edu/papers/volume8/saar-tsechansky07a/saar-tsechansky07a.pdf

Monday, September 11, 2017

Python Spark ML():Decision Tree Algorithm - ID3

Python Spark ML():Decision Tree Algorithm - ID3

2017/09/11




-----

References

[1] Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106.

[2] Iterative Dichotomiser 3 (ID3) algorithm – Decision Trees – Machine Learning
https://mariuszprzydatek.com/2014/11/11/iterative-dichotomiser-3-id3-algorithm-decision-trees-machine-learning/

[3] AI - Ch14 機器學習(2), 決策樹 Decision Tree _ Mr. Opengate
http://mropengate.blogspot.tw/2015/06/ai-ch13-2-decision-tree.html

[4] ID3(Iterative Dichotomiser 3)算法原理详解 - Abraham Ben - CSDN博客
http://blog.csdn.net/u012897374/article/details/74505024?fref=gc&dti=197223143437

[5] GitHub - Valdecy_Iterative-Dichotomiser-3  ID3 Algorithm - A Decision Tree for Categorical Data with Pruning Methods
https://github.com/Valdecy/Iterative-Dichotomiser-3 

[6] Decision Trees - RDD-based API - Spark 2.2.0 Documentation
https://spark.apache.org/docs/latest/mllib-decision-tree.html

[7] spark_mllib_src_main_scala_org_apache_spark_mllib_tree at master · apache_spark · GitHub
https://github.com/apache/spark/tree/master/mllib/src/main/scala/org/apache/spark/mllib/tree

跑步(九八):20圈

跑步(九八):20圈

2017/09/11

熱身2,跑(5*4)。

-----

Keep going。

Saturday, September 09, 2017

Python Spark ML(六):Decision Tree Algorithm Survey

Python Spark ML(六):Decision Tree Algorithm Survey

2017/09/08

作業六:

請解釋圖2左邊各 features 以及其選項的意義。

作業請以文章的方式將 GitHub 連結回應到本篇文章在 Python Taiwan 的連結處:
https://www.facebook.com/groups/pythontw/permalink/10156862362473438/

-----

前言:

這是 Python Spark ML 的第一週。

這週我花了不少時間看本活動的教科書 [1],以及蒐集、整理網路上的資料 [2]。

當學生的時候,我其實不喜歡寫作業的。現在算是「當」老師吧!我要勉勵大家,規定的作業,「儘量」好好完成。作業的目的,其實是要輔助你好好瞭解一門科目。

套句歌詞:+1 是簡單的,交作業是困難的。很難的東西,如果你能拆成小塊,就簡單多了。

本篇之後,在下一篇之前,我們大概得花不少時間來消化資料。

整個活動有可能超過一年(如果有認真的同學持續交作業)。如果你能順利走過,一年後你就是炙手可熱、企業爭相追逐的「機器學習專家」了!

-----

Outline

一、決策樹的分類。
二、多棵決策樹。 
三、主要的決策樹演算法。
四、決策樹的歷史演進。

-----

一、決策樹的分類(單棵決策樹)。

本活動的主要目的之一是在 Python Spark 的 ML 環境,分別以 RDD / MLlib 與 DataFrame / ML Pipeline 實作:決策樹二元分類、決策樹多元分類、決策樹迴歸分析 [1]。

配合上述之目的,在上次的資料搜尋中 [2],我們知道,決策樹有兩種主要類型 [3]:

1.1. 分類樹。
1.2. 迴歸樹。

其中,分類樹可用於二元分類與多元分類,迴歸樹可用於迴歸分析。

「分類與迴歸樹 Classification And Regression Trees (CART)」此概念在 [14] 中被提出。

-----

二、多棵決策樹 [4]。

2.1. 裝袋算法(Bagging)。
2.2. 隨機森林(Random Forest)。
2.3. 提升樹(Boosting Tree)。
2.4. 旋轉森林(Rotation forest)。

多棵決策樹的方法,並非本活動的主要目的,但部分如隨機森林等在實作中也會遇到。此處先列出作為參考。

-----

三、主要的決策樹演算法。

圖1是 [5] 列出的主要決策樹演算法。配合稍早 [2] 的部分文獻 [3]-[6],我們可以將圖1再補上 MARS [6], [7]。

3.1. ID3 (Iterative Dichotomiser 3)
3.2. C4.5 (Improvement of ID3)
3.3. CART (Classification And Regression Trees)
3.4. CHAID (Chi-square Automatic Interaction Detector)
3.5. MARS (Multivariate Adaptive Regression Splines)

「常用的屬性選擇指標:
1. 資訊獲利(Information gain):ID3、C4.5、C5.0。
2. 吉尼係數(Gini Index):CART。
3. X平方獨立性檢定:CHAID 。」[22]


Fig. 1. Decision tree algorithms [5].


Fig. 2. Comparison of classification tree methods [8].
 
-----

四、決策樹的歷史演進。

4.0.1. AID (Automatic Interaction Detector) - regression tree
4.0.2. THAID (Theta Automatic Interaction Detector) - classification tree

4.1. ID3 - classification tree
4.2. C4.5 - classification tree
4.3. CART - classification tree and regression tree
4.4. CHAID
4.5. MARS

-----

4.0.1 AID

「Historically, the first regression tree algorithm is AID [9], which appeared several years
before THAID. 」[8]
根據 [8],歷史上,最早的迴歸樹演算法是 AID [9],比 THAID 還要早上幾年。

-----

4.0.2. THAID

「The first published classification tree algorithm is THAID [10], [11]. 」[8]
根據 [8],第一個發表的分類樹演算法是 THAID [10], [11]。

-----

4.1. ID3 [12]

「ID3以選擇最大的資訊獲利值作為分類屬性,以熵(Entropy)為基礎 熵用來衡量資料的一致性,當作資訊量凌亂程度(不確定性)的指標,熵越大代表凌亂程度越大 在資料集合S中,屬性A的資料獲利表示為Gain(S,A) 。當Gain值越大,表示屬性A中資料凌亂程度越小,分類資料越佳。因此,Gain值在同層屬性中越大的,該屬性即會作為分割節點 然而,ID3演算法的缺點在於資訊獲利會傾向選擇擁有許多不同數值的屬性(因為會產生許多分支,分支內資訊量少,所以凌亂度低)。照此方式無法得出有意義的決策樹,因此C4.5就此產生」[22]

-----

4.2. C4.5 [13]

「C4.5演算法改進ID3演算法,以獲利比率(GainRatio)最大者作為決定屬性。這方式解決了ID3的缺點,但是會有過度補償的問題,例如可能只是因為某欄位數值變化比其他欄位低很多而已。改善方式是,選擇具有最大獲利比率的欄位,然而該欄位的資訊獲利要跟所考察的所有欄位的平均資訊獲利差不多 另外,C4.5也可以對連續屬性加以處理 C5.0 C5.0為C4.5的改進版,主要針對海量資料的處理,以及增加執行準確度、減少記憶體耗用 C5.0的其他優點還有提高精度、模型易於理解、不需要很長的訓練次數、面對遺漏值時非常穩定等。」[22]

-----

4.3. CART [14]

「C4.5 [13] and CART [14] are two later classification tree algorithms that follow this approach.」[8]

The AID and CART regression tree methods follow Algorithm 1, with the node impurity
being the sum of squared deviations about the mean and the node predicting the sample mean of Y. [8]

根據 [8],CART 同時是分類樹與迴歸樹。見上文。

有關 CART,更多的資料可以參考 [19]-[21]。

「CART(Classfication and Regression Tree) 在節點上採取二分法,故為二元樹,以吉尼係數作為選擇依據 以吉尼係數最小的屬性作為分割屬性」[22]

-----

4.4. CHAID [15]

-----

4.5. MARS

「MARS 是用來解決多元資料問題的新方法,主要是運用數段解釋方程式而加總組合出一個較具彈性的預測模式的觀念,它是一種具彈性的迴歸處理程序,可以自動建立準則模型,並利用這個準則模型來推測其連續和間斷的反應變數 [16]。從名稱來看,就是指多元逐步的迴歸程序,它最適合運用在高維度的問題,也被視為廣義的線性逐步迴歸,或者是經由修正 CART 的方法而改善迴歸配適的執行過程 [17]。目前已被運用在許多不同領域的研究上,其中又以分類判別問題的應用最多,對於預測問題的運用也有愈來愈普遍的趨勢。 」

「MARS 目前較被廣泛運用的領域大部分是資料採礦的區隔問題方面,由於它的要求是以最適合的解釋變數建立起各區間的解釋模型,我們透過這個新的解釋變數建立的程序,可有效的從資料中挖掘出過去一些處理方法難以發現的重要特性及關係 [18]。而其函數中的解釋方程式之個數則是根據其資料本身參數間的交互關係所決定,並經由評估其損適性之判斷標準,同時獲得最佳及最適合的變數組合,如此可用來解決高維度資料的各種問題 [16]。」

-----

結論:

由本次的文獻回顧,我們可以猜測,在 [1] 裡面用的演算法,決策樹二元分類、決策樹多元分類「可能採用」ID3 / C4.5;決策樹迴歸分析「可能採用」CART。

後續將針對此三種演算法深入討論!

C4.5 與 CART 可參考資料科學最熱的十一種演算法 [23], [24]。

-----

References

[1] Python Spark ML(一):參加辦法
http://hemingwang.blogspot.tw/2017/09/python-spark-ml.html

[2] Python Spark ML(三):Decision Tree Survey
https://hemingwang.blogspot.tw/2017/09/python-spark-mldecision-tree-survey.html

[3] 決策樹 - 維基百科,自由的百科全書
https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91 

[4] 決策樹學習 - 維基百科,自由的百科全書
https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91%E5%AD%A6%E4%B9%A0 

[5] 活學活用決策樹(三):運用SAS EM決策樹進行CHAID及CART分析
http://www.sasresource.com/faq389.html

[6] 從決策樹到隨機森林:樹型算法的原理與實現_機器之心 _ 微文庫-微信公眾號文章
https://weiwenku.net/d/101752231 

[7] 資料採礦中的統計預測與分類方法
http://www.stat.ncku.edu.tw/faculty_private/sljeng/Datamining/predict.htm

[8] Loh, Wei‐Yin. "Classification and regression trees." Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1.1 (2011): 14-23.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.364.9647&rep=rep1&type=pdf 

[9] Morgan, James N., and John A. Sonquist. "Problems in the analysis of survey data, and a proposal." Journal of the American statistical association 58.302 (1963): 415-434.

[10] Fielding, A., and C. A. O'Muircheartaigh. "Binary segmentation in survey analysis with particular reference to AID." The Statistician (1977): 17-28.

[11] Messenger, Robert, and Lewis Mandell. "A modal search technique for predictive nominal scale multivariate analysis." Journal of the American statistical association 67.340 (1972): 768-772.

[12] Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106.

[13] Quinlan, J. Ross. "C4. 5: Programs for machine learning (morgan kaufmann series in machine learning)." Morgan Kaufmann (1993).

[14] Breiman, Leo, et al. Classification and regression trees. CRC press, 1984.

[15] Kass, Gordon V. "An exploratory technique for investigating large quantities of categorical data." Applied statistics (1980): 119-127.

[16] Friedman, Jerome H. "Multivariate adaptive regression splines." The annals of statistics (1991): 1-67.

[17] Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. "The Elements of Statistical Learning: Data Mining, Inference, and Prediction." Biometrics (2002).

[18] Steinberg, D., P. L. Colla, and Kerry Martin. "MARS user guide." San Diego, CA: Salford Systems (1999).

[19] https://rafalab.github.io/pages/649/section-11.pdf

[20] http://www.stat.cmu.edu/~cshalizi/350/lectures/22/lecture-22.pdf

[21] http://avesbiodiv.mncn.csic.es/estadistica/curso2011/regm40.pdf  

[22] 程式_ 決策樹演算法筆記 @ Leon's Sketches   痞客邦 PIXNET
http://iamkyc0312.pixnet.net/blog/post/339857156-%E7%A8%8B%E5%BC%8F%7C-%E6%B1%BA%E7%AD%96%E6%A8%B9%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98 

[23] Wu, Xindong, et al. "Top 10 algorithms in data mining." Knowledge and information systems 14.1 (2008): 1-37.

[24] Chen, Tianqi, and Carlos Guestrin. "XGBoost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016.

Python Spark ML(五):Decision Tree Survey - 問題討論

Python Spark ML(五):Decision Tree Survey - 問題討論

2017/09/09

作業五:

請將長篇的回覆,以文章的方式將連結回應到本篇文章在 Python Taiwan 的連結處:
https://www.facebook.com/groups/pythontw/permalink/10156862039173438/

短的意見則直接回應即可!

-----

前言:

Python Spark ML [1] 第一週,有很認真的同學,很認真地交了作業 [2],包含兩個回答 [3], [4]。

在 [2] 所附的參考資料中,[5] 是 MIT 教授的英文線上課程。這個教授的課程,之前我也聽過 SVM,講的非常好。[6] 則是有關決策樹很棒的中文簡介。

因應認真的同學,我特別把他交的作業 highlight 出來,作為課程的一部份,方便大家討論。當然,這個可能很多人都還不熟,包括我在內。我也會趕一下進度再參加討論!

-----

陳敬翔:學生讀了決策樹資料後有找範例(1)來做(純手工計算)。但是當同時使用到 Information Gain(資訊獲得量,針對類別型尺度)及計算 Gini Index(吉尼係數,針對連續型尺度)取得最佳解(切割點)時卻導致建構不出來決策樹;反倒再找了另一個簡單的只有類別型尺度的範例(2),使用相同的公式卻又可以順利建構出決策樹來。如果有學習過決策樹的同學也請不吝解惑,感謝你們:)

-----


Fig. 1. Decision tree example [4].

-----

[1] Python Spark ML(三):Decision Tree Survey
https://hemingwang.blogspot.tw/2017/09/python-spark-mldecision-tree-survey.html

[2] PythonSparkMLBookClub_Homework-PythonSparkML_03 at master · oneleo_PythonSparkMLBookClub · GitHub
https://github.com/oneleo/PythonSparkMLBookClub/tree/master/Homework-PythonSparkML_03

[3] Answer 01
https://github.com/oneleo/PythonSparkMLBookClub/blob/master/Homework-PythonSparkML_03/Homework-PythonSparkML_03-01.md

[4] Answer 02
https://github.com/oneleo/PythonSparkMLBookClub/blob/master/Homework-PythonSparkML_03/Homework-PythonSparkML_03-02.md

[5] Lecture 11  Learning  Identification Trees, Disorder _ Lecture Videos _ Artificial Intelligence _ Electrical Engineering and Computer Science _ MIT OpenCourseWare
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-11-learning-identification-trees-disorder/

[6] AI - Ch14 機器學習(2), 決策樹 Decision Tree _ Mr. Opengate
http://mropengate.blogspot.tw/2015/06/ai-ch13-2-decision-tree.html

Wednesday, September 06, 2017

Python Spark ML(四):Decision Tree Survey - 資料補充

Python Spark ML(四):Decision Tree Survey - 資料補充

2017/09/12

本次沒有作業。

若有任何討論,可以回應至:
https://www.facebook.com/groups/pythontw/permalink/10156873112708438/

-----

Summary:

機器學習 [1],包含許多演算法 [2]。決策樹則屬於監督式學習的一種 [3], [4]。

分類樹可以使用 entropy 與 Gini 作為參考指標 [5]-[8],回歸樹則使用 variance [18]。

決策樹較深入的探討可以參考 [9]-[14],實作可以參考 [15], [16]。

Python 跟 Spark 都有套件支持決策樹 [17], [18]。本活動(Python Spark ML)後續主要會參考 [18]。

-----

p.s. 上次的作業,有不少同學提供了很好的補充材料,我把這些材料整理一下,作為 [19] 的補充。

在此一一標明姓名以謝謝這些認真作答的同學:)

Charles Wang
章銘恒
王仁佑
王得懿
吳政龍
Yu-wei Chen
陳敬翔
Mirage Chung

-----


Fig. 1. Decision tree regression [17].

-----

References

概論:

[1] AI - Ch13 機器學習(1), 機器學習簡介與監督式學習 Introduction to Machine Learning, Supervised Learning _ Mr. Opengate
http://mropengate.blogspot.tw/2015/05/ai-supervised-learning.html

[2] 演算法筆記 - Classification
http://www.csie.ntnu.edu.tw/~u91029/Classification.html

[3] 最直覺的分類--決策樹 _ 幣圖誌Bituzi - 挑戰市場規則
http://www.bituzi.com/2014/12/the-most-intuitive-classification-dicision-tree.html

[4] Behavior tree (artificial intelligence, robotics and control) - Wikipedia
https://en.wikipedia.org/wiki/Behavior_tree_%28artificial_intelligence,_robotics_and_control%29

-----

決策樹的基礎:
 
[5] 决策树的数学原理 - liuzhiqiangruc - ITeye博客
http://liuzhiqiangruc.iteye.com/blog/2289986

[6] 怎样理解 Cross Entropy _ MemoMemoMemo
http://shuokay.com/2017/06/23/cross-entropy/

[7] 綠角財經筆記  什麼是吉尼係數(What is Gini Coefficient )
http://greenhornfinancefootnote.blogspot.tw/2011/09/what-is-gini-coefficient.html

[8] 綠角財經筆記  世界各國的吉尼係數(Gini Coefficients Data)
http://greenhornfinancefootnote.blogspot.tw/2011/09/gini-coefficients-data.html

-----

大學的教材:

[9] Construction of Decision Trees
https://dspace.mit.edu/bitstream/handle/1721.1/5845/AIM-189.pdf?sequence=2 

[10] Simplifying Decision Tree
https://dspace.mit.edu/bitstream/handle/1721.1/6453/AIM-930.pdf?sequence=2 

[11] Decision Tree Learning
http://www.cs.princeton.edu/courses/archive/spr07/cos424/papers/mitchell-dectrees.pdf

[12] The alternating decision tree learning algorithm
https://cseweb.ucsd.edu/~yfreund/papers/atrees.pdf 

-----

深入決策樹:

[13] Why do Decision Trees Work  – Win-Vector Blog
http://www.win-vector.com/blog/2017/01/why-do-decision-trees-work/ 

-----

應用:

[14] Using Decision Trees to predict infant birth weights _ DataScience+
https://datascienceplus.com/using-decision-trees-to-predict-infant-birth-weights/?fref=gc&dti=197223143437

-----

實作:

[15] learn_python_for_a_r_user_day23.md at master · yaojenkuo_learn_python_for_a_r_user · GitHub
https://github.com/yaojenkuo/learn_python_for_a_r_user/blob/master/day23.md

[16] How To Implement The Decision Tree Algorithm From Scratch In Python
https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/

[17] SCIKIT-Decsion Trees
http://scikit-learn.org/stable/modules/tree.html

[18] Spark 2- Decision Tree
https://spark.apache.org/docs/latest/mllib-decision-tree.html

[19] Python Spark ML(三):Decision Tree Survey
https://hemingwang.blogspot.tw/2017/09/python-spark-mldecision-tree-survey.html