I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows:
Say we are given $N$ ordered data points on the real line: $x_1,\ldots,x_N \in \mathbb{R}$ such that $x_1 < x_2 < \ldots < x_N$.
Each of the points $x_i$ has a label $y_i \in \{0,1\}$. We are asked to predict this label using a decision stump classifier, $h(x;t) = \mathbb{1}[x>t]$. The decision stump classifier predicts $\hat{y}_i = 1$ if $x_i > t$. Thus, the accuracy of this classifier depends on the threshold parameter $t$.
I am looking for an efficient algorithm to determine the value of $t$ that maximizes the number of correctly classified points. That is, solve the problem:
$$\max_{t\in\mathbb{R}} A(t)=\sum_{i=1}^N \mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t] + \mathbb{1}[y_i=1]\mathbb{1}[x_i>t]$$ Some insights:
Since there are $N$ data points, we only need to consider $N+1$ values of $t$. These are values that lie in the $N+1$ intervals $(-\infty,x_1), [x_1,x_2),\ldots, [x_{N-1},x_N), [x_N,\infty]$.
When $t < \min_{i}x_i$, the decision stump predicts $\hat{y}_i=1$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]}=N^+$.
When $t \geq \max_{i}x_i$, the decision stump predicts $\hat{y}_i=0$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]}=N^-$.
The number of correctly classified points $A(t)$ can be decomposed as $B(t)+C(t)$, where $$B(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t]}$$ is the number of correctly classified points with negative labels and $$C(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]\mathbb{1}[x_i>t]}$$ and the number of correctly classified points with positive labels. Note that $B(t)$ is monotonically increasing in $t$ while $C(t)$ is monotonically decreasing in $t$.