# Two-Stage Dimensionality Reduction for Social Media Engagement Classification
## 3 Proposed Algorithm
### First Stage--Maximizing Separation Probability  
The definition of separation probability is mainly based on the minimax probability machine (MPM) [18], which maximizes the probability of the correct classification of future data points. Let \(x\) and \(y\) denote random vectors in a binary classification problem and suppose that the means and covariance matrices of these two classes are \((\mu_{x},\Sigma_{x})\) e \((\mu_{x},\Sigma_{y})\), respectively, with \(x,\mu_{x},y,\mu_{y},\in\mathbb{R}^{D}(\mu_{x}\
eq\mu_{y})\) and \(\Sigma_{x},\Sigma_{y}\in\mathbb{R}^{D\times D}\). The MPM maximizes the probability \(\alpha\) that two classes lie on two sides of a hyperplane \(\mathbb{H}(w,b)=\{z\|w^{T}z=b\}\), where \(w\in\mathbb{R}^{D},w\
eq 0\), and \(b\in\mathbb{R}\). The hyperplane separates the two classes with a maximal probability with respect to all possible distributions with the given means and covariance matrices. This optimal \(w\) and the corresponding separation probability \(\alpha\) of two classes in the subspace can be derived by solving the following problem [10].  
\[\max\kappa(w)=\frac{|w^{T}(\mu_{x}-\mu_{y})|}{\sqrt{w^{T}\Sigma_{x}w}+\sqrt{w^{ T}\Sigma_{y}w}} \tag{3}\]  
\[\kappa(w)=\sqrt{\frac{\alpha(w)}{1-\alpha(w)}} \tag{4}\]  
\[\alpha^{*}(w^{*})=\frac{\kappa^{*}(w^{*})^{2}}{1+\kappa^{*}(w^{*})^{2}} \tag{5}\]  
In fact, with the class means and covariance matrices of two classes, it is possible to calculate the corresponding separation probability \(\alpha\) to quantify the class separability between them in a certain 1-D subspace \(w\). In this way, this probability is used as a class separability measure to drive the dimensionality reduction problem, where the use of the separation probability can effectively solve the class masking problem.  
Consider a dataset with \(C\) classes, whose conditional distribution of class \(i\) is given by \(p(x\mid\mu_{i},\Sigma_{i})\), where \(\mu_{i}\) represents the mean and \(\Sigma_{i}\) the covariance. In this way, the probability \(\alpha_{ij}\) of separation of classes \(i\) and \(j\) in the subspace \(w\) can be calculated as in Equation (6).  
\[\alpha_{ij}(w)=\frac{\kappa_{ij}(w)^{2}}{1+\kappa_{ij}(w)^{2}} \tag{6}\]  
In this way, substituting Equations (7) and (8) into Equation (6), the probability \(\alpha_{ij}\) can be described as per Equation (9).  
\[k_{ij}(w)=\frac{\left|w^{T}(\mu_{i}-\mu_{k})\right|}{\sqrt{w^{T}\Sigma_{i}w}+ \sqrt{w^{T}\Sigma_{j}w}} \tag{7}\]  
\[\Sigma_{ij}=(\mu_{i}-\mu_{j})(\mu_{i}-\mu_{j})^{T} \tag{8}\]  
\[\alpha_{ij}(w)=\frac{w^{T}\Sigma_{ij}w}{w^{T}\Sigma_{ij}w+(\sqrt{w^{T}\Sigma_ {i}w}+\sqrt{w^{T}\Sigma_{j}w})^{2}} \tag{9}\]  
The problem is then solved by finding the optimal 1-D subspace \(w\in\mathbb{R}^{D}\), where the sum of the separation probabilities of all pairs of classes is maximized, which can be represented in the form of Equation (10).  
\[\max J_{\text{DR-MSP}}(w)=\sum_{1\leq i\leq j\leq C}\alpha_{ij}(w) \tag{10}\]  
By observing that \(\alpha_{ij}(w)\) is homogeneous with respect to \(w\), we can add the normalization constraint on Equation (10). The optimal subspace \(w^{*}\) is given below in Equation (11) andcalculated as described in Algorithm 1 once it consists of applying a gradient descent algorithm.  
\[w^{*}\in\operatorname*{argmax}J_{\text{DR-MSP}}(w) \tag{11}\]  
```
0: Original dataset \(\{X,Y\}=\{(x_{i},y_{u})\}_{i=1}^{n}\) and target dimension \(d\).
0: Optimal subspace \(W^{*}\).
1: Calculate the means \(\mu_{i}\) and the covariance \(\Sigma_{i}\) for \(i=0,1,2,\ldots,C\).
2: Set \(A_{0}=I\) and \(W_{0}\) as empty.
3:for\(r=1\) to \(d\)do
4: Step 1
5: Update \(v\) following \(v^{(t+1)}=v^{(t)}+\gamma^{(t)}\frac{\partial}{\partial v}J_{\text{DR- MSP}}(v)\).
6: Step 2
7:\(w_{r}\gets A_{r-1}v^{*}\)
8:\(w_{r}\leftarrow\frac{w_{r}}{\|w_{r}\|}\)
9:\(W_{r}\leftarrow(W_{r-1},w_{r})\)
10: Step 3
11: If\(r<d\)then\(A_{r}\leftarrow(I-w_{r}w_{r}^{T})A_{r}\)
12:endfor
```  
**Algorithm 1**\(d\)--Dimension Reduction via Maximum Separation Probability