# AI Final Project Proposal

## Problem Statement and Task Definition
利用人工智慧的方法分析新北市近幾個月停車場的剩餘車位數，預測未來某個時間點下，停車場可能的剩餘車位數。


上圖為「板橋區民生花市平面停車場」於 3/21~3/27 的剩餘車位趨勢（藍色為原始資料，橘色為平滑化後的資料），可以看到資料呈現週期性的起伏，因此推斷這個題目是可以利用人工智慧的技巧進行學習的。

## Description of the challenges
* 這類問題可以使用 MDP 來建模，但由於現實世界中車位趨勢相當複雜，因此不容易找出 MDP 中的狀態、狀態轉換函數等，所以我們偏好使用機器學習的技法讓機器自動找出車位的趨勢與規律。然而，如何將這個問題轉換為機器學習的問題也是一大難題，例如該使用何種架構？輸入、輸出該如何定義？
* 由於政府只有提供即時資料而無歷史資料，因此必須 24 小時都在收集資料而不能中斷，否則資料不完整可能會讓模型學習困難，因此資料收集是困難點之一。此外，政府提供的資料含有許多雜訊，如何處理雜訊也是一個重要的課題。許多停車場車位數會突然上升、突然下降、連續好幾天沒有變化或是起伏劇烈，如此不確定性的資料會使模型學習困難，因此，在將資料餵給模型之前，應先觀察資料並做適當的前處理。因此，如何設計演算法對資料做前處理也是這個專題的一大挑戰。

## Input/Output Behavior with Concrete Examples
設計網頁或互動式界面，使用者可提供停車場名稱及想要預測的時間，模型會根據日期、時間及停車位趨勢，預測該時間下停車場可能剩餘的車位數。

舉例來說，使用者給定「臺北科學城停車場、4/20、13:45」，程式就會將這個資訊餵給模型，並輸出該時間下剩餘停車位可能的範圍與機率。

#### 資料來源
[新北市路外公共停車場資訊 | 政府資料開放平臺](https://data.gov.tw/dataset/122955?fbclid=IwAR0GwfgfuERU7qnNmFcaLfj-dGwnZ8IJCsF_mcIbdcHkDwHU5wXTPLabWdw)
[新北市公有路外停車場即時賸餘車位數 | 政府資料開放平臺](https://data.gov.tw/dataset/122902?fbclid=IwAR01YjU5sP1TFQ5XU7aeJbLTk2KG7ZI5nfuip1P8U4vEmKxbF2V8Ol5dxIM)
[即時路況與停車資訊流通平台](https://traffic.transportdata.tw/Service?Type=ParkingSeat)

## Related works
#### Tutorials
* 股票預測
[GitHub - huseinzol05/Stock-Prediction-Models: Gathers machine learning and deep learning models for Stock forecasting including trading bots and simulations](https://github.com/huseinzol05/Stock-Prediction-Models)
* TensorFlow 提供的時間序列預測教學
[Time series forecasting | TensorFlow Core](https://www.tensorflow.org/tutorials/structured_data/time_series)
#### Papers
詳見 [AI Final Project Discussion Board#Papers](https://hackmd.io/AJE_CAd_TDSop6vtk8GrmA#Papers)。
## Methodology
* LSTM + DNN
此為 Baselines 所提出的方法。給定模型剩餘車位、時間、星期的資料，要求模型輸出 15 分鐘、30 分鐘、45 分鐘... 後的剩餘車位資料。可利用 PyTorch 現有的 LSTM 與 DNN 模型設計。
* 優點：實作容易，而且有許多現成的 LSTM 股票預測模型可以用在這個問題上。
* 缺點：比較傳統的方法，表現上可能不如 SOTA 模型。
* VAR
* ELM
* Informer
此方法將Transformer中的自注意力機制改寫成論文中的ProbSparse self-attention，並利用蒸餾的技巧以及改進版的Decoder，將Transformer成功運用在Long Sequence Time-series Forcasting問題上。
* 優點：解決LSTM在計算長遠未來預測時，MSE的大量上升，以及由RNN造成的推理速度的急速下降。推理時間遠低於LSTM。
* 缺點：即使Informer在Transfermer中訓練效率最高，訓練時間仍高出LSTM不少。
* TCN
此方法主要使用CNN作為基礎，引入Dilated Convolution及Causal Convolution，將CNN改寫成適用於序列型輸入的模型。
* 優點：由於模型以CNN為基礎，相較Transformer系列模型，複雜度低了許多，有更快的訓練收斂速度，以及更好的記憶體利用。
* 缺點：即便在特徵捕捉方面，TCN優於Transformer，但是距離真值還是有一些差距，往往會造成MSE較Transformer差。
* SVR (Support Vector Regression)、KRR (Kernel Ridge Regression)
將預測停車位的問題轉為簡單的迴歸問題。舉例來說，輸入為停車場、時間相關資訊，輸出為停車場車位數。
* 優點：不必用到神經網路，訓練及推理時間快速。可作為簡易預估的方法或分析長期的趨勢。
* 缺點：由於不考慮時間序列的關係，因此無法從時間序列中習得相關資訊（例如近期趨勢）。

## Evaluation Metrics
目前採用 MSE（均方誤差）計算預測車位數與真實車位數的差異作為衡量模型表現的方式。


以這個例子為例，假設此圖為某一個停車場剩餘車位的資料（車位數皆事先縮放至$[-1,1]$），藍色為 Ground Truth，橘色為預測資料。則對於這個停車場來看，均方誤差為 $\frac{1}{2}(d_1^2+d_2^2)$。

未來可能也會採用 MAE（平均絕對誤差）作衡量。MSE 或 MAE 越低，則代表預測與真實值越接近，代表模型表現越好。

## Baselines
### LSTM + DNN
#### Implementaion
[Final Project Proposal - Colaboratory](https://colab.research.google.com/drive/1CGeVF4PVq0BvwZ2x8772xcOWhPMC5F4R?authuser=1#scrollTo=2tHPRYCptDWd)
#### 模型架構

Baselines 採用 LSTM 搭配 DNN 進行時間序列預測，透過給予神經網路某個時間點下的剩餘車位數、時間、星期、停車場資訊（編號），輸出 15 分鐘、30 分鐘、45 分鐘... 後的剩餘車位數。

[此圖](https://i.imgur.com/kLfr4gq.png)為 32 個停車場於驗證資料集上的表現（藍色為剩餘停車位的 Ground Truth，橘色為預測未來 24 小時內的剩餘停車位數）：

此模型已能萃取出不同停車場在不同時段下停車場剩餘車位數的趨勢，但目前資料量還不夠多，因此模型仍有進步空間（但其實這個的表現已經超出預期了！）
### VAR
Vector Autoregression 是 Autoregression(AR) 的多變數版本，這個模型假設現時點的數值與過去的數值存在線性關係，並透過過去的資料線性預測未來資料可能的數值。
### ELM
Extreme Learning Machines 的特點是，相較於傳統前饋神經網路需要人工設置大量參數，這個模型只需要設定網路的結構，不需要設置其他參數，因此較易於使用。雖然這個模型並沒有那麼精準，但學習速度非常快。
### SVR
將預測停車位的問題轉為簡單的迴歸問題。舉例來說，輸入為停車場、時間相關資訊，輸出為停車場車位數，不考慮時間序列的影響。可以利用 [sklearn.svm.SVR](https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVR.html) 實作。

## Time schedule
* 04/18/2022 - 05/08/2022
實作 baselines 中的 VAR 與 ELM 模型
* 05/09/2022 - 05/29/2022
觀察 baselines 的實作結果決定出要使用的模型並實作
* 05/30/2022 - 06/19/2022
（選擇性）嘗試實作其他模型並比較結果
* 06/19/2022 -
統整與分析數據
將作品部署至網頁上或設計操作界面
## Discussion
[AI Final Project Discussion Board](https://hackmd.io/AJE_CAd_TDSop6vtk8GrmA)

## Repo
[lashhw/AI-Final-Project](https://github.com/lashhw/AI-Final-Project)