# Stock Market Prediction Using Microblogging Sentiment Analysis and Machine Learning
## 2 Background
### Classification Algorithms
Decision rules can be derived only after the tree has been created [30]. In more detail, given some training vectors \(x_{i}\in R^{n}\), \(i=1,\ldots,l\) and a label vector \(y\in R^{l}\), a decision tree recursively partitions the feature space in a way that the samples with the same labels or similar target values belong to the same group. Let the data at node \(m\) be represented by \(Q_{m}\) with \(n_{m}\) samples. For each candidate split \(\theta=(j,t_{m})\) that consists of a feature \(j\) and threshold \(t_{m}\), partition the data into \(Q_{m}^{left}(\theta)\) and \(Q_{m}^{right}(\theta)\) subsets (6):  
\[ \begin{split} Q_{m}^{left}(\theta)=\{(x,y)|x_{j}<=t_{m}\}\\ Q_{m}^{right}(\theta)=Q_{m}\setminus Q_{m}^{left}(\theta)\end{split}  \tag{6}\]  
The quality of a candidate split of node \(m\) is then calculated, utilizing an impurity function \(H()\) for classification problems (7). \[G(Q_{m},\theta)=\frac{n_{m}^{left}}{n_{m}}H(Q_{m}^{left}(\theta))+\frac{n_{m }^{right}}{n_{m}}H(Q_{m}^{right}(\theta)) \tag{7}\]  
Then, select the respected parameters that minimize the impurity (8):  
\[\theta^{*}=\text{argmin}_{\theta}G(Q_{m},\theta) \tag{8}\]  
Finally, recurse for subsets \(Q_{m}^{left}(\theta^{*})\) and \(Q_{m}^{right}(\theta^{*})\) until the point that the maximum depth allowed, \(n_{m}<\text{min}_{samples}\) or \(n_{m}=1\). Random Forest (RF) is an ensemble learning approach comprising numerous arbitrary generated DTs. Random Forest seeks the greatest feature from an arbitrary feature subset, with the goal of using it as a criterion for dividing the nodes. RF solves the problem of over-fitting and delivers higher accuracy predictions than regular DTs [31]. The Multilayer Perceptron (MLP) is a deep artificial NN and supervised learning approach. MLP is made up of numerous layers of input nodes connected by a directed graph that connects the input and output layers. The signal is fed into the input layer, and the prediction is made by the output layer. The purpose is to estimate the best relationship between the input and output layers [32]. Given a set of training examples \((x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{n},y_{n})\) where \(x_{i}\in\mathbf{R}^{n}\) and \(y_{i}\in\{0,1\}\), a one-hidden layer one-hidden neuron MLP learns the function \(x_{i}\in\mathbf{R}^{n}\) where \(x_{i}\in\mathbf{R}^{n}\) and \(W_{2},b_{1},b_{2}\in\mathbf{R}\) are model parameters. \(W_{1},W_{2}\) represent the weights of the input layer and hidden layer, respectively, while \(b_{1},b_{2}\) show the bias added to the hidden layer and the output layer, respectively. \(g(\cdot):R\to R\) is the activation function, set by default as the hyperbolic tan according to (9). \[g(z)=\frac{e^{z}-e^{-z}}{e^{z}+e^{-z}} \tag{9}\]  
For binary classification, \(f(x)\) passes through the logistic function \(g(z)=1/(1+e^{-z})\) to retrieve output values between zero and one. A threshold is set to 0.5, assigning samples of outputs larger or equal 0.5 to the positive class, and the remainder to the negative class. The MLP loss function for classification is the Average Cross-Entropy, which in binary case is calculated according to (10). \[Loss(g,y,W)=\frac{1}{2n}\sum_{i=0}^{n}||g_{i}-y_{i}||_{2}^{2}+\frac{\alpha}{2n}|| W||_{2}^{2} \tag{10}\]  
In a gradient descent, the gradient \(\
abla Loss_{W}\) of the loss concerning the weights is calculated and subtracted from \(W\) according to (11), where \(k\) is the iteration step and \(\epsilon\) stands as the learning rate with a greater value from zero. The algorithm terminates when the maximum number of iterations is reached, or when the gain in loss is less than a particular, very small threshold. \[W^{k+1}=W^{k}-\epsilon\
abla Loss_{W}^{k} \tag{11}\]