Determining the optimal threshold value for a one-dimensional decision stump classifier

Question

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$.

Answer 1

There is a straightforward algorithm that runs in $O(N)$ time, by scanning from left-to-right and right-to-left. Basically, it takes advantage of a simple recurrence relation for $B(\cdot)$ and $C(\cdot)$.

Let $t_0,t_1,\dots,t_N$ denote a sequence of $N+1$ candidates for the threshold (i.e., $t_i \in [x_i,x_{i+1})$, etc.), as you articulated in the question. Our job is to find the value of $i$ that maximizes $B(t_i)+C(t_i)$.

I claim we can compute the $N+1$ values $B(t_0),B(t_1),\dots,B(t_N)$ in $O(N)$ time, using a left-to-right scan. This is because, given $B(t_{i-1})$, it is easy to compute $B(t_i)$. In particular, notice that $B(t_i)$ can be written as the summation

$$B(t_i) = \sum_{j=1}^i 1[y_j=0].$$

In other words $B(t_i)$ is the count of how many of the first $y$'s are equal to zero. Thus we get the recurrence relation

$$B(t_i) = B(t_{i-1}) + 1[y_i=0]$$

with the base case $B(t_0)=0$. This allows us to compute all of the $B(t_i)$'s in $O(N)$ time.

We can similarly compute the $N+1$ values $C(t_0),C(t_1),\dots,C(t_N)$ in $O(N)$ time, by scanning from right-to-left. Here we take advantage of a recurrence relation that computes $C(t_i)$ given $C(t_{i+1})$. The details are similar to that for $B(\cdot)$.

The result is that we can compute the sequence of $N+1$ values $B(t_0)+C(t_0),B(t_1)+C(t_1),\dots,B(t_N)+C(t_N)$ in $O(N)$ time. Then it is easy to find the largest value in that list. The running time in total is $O(N)$ time.

I don't think you can do any better than $\Theta(N)$ worst-case running time, since you may need to examine every item (in the worst case). Therefore,the method I have outlined above appears to be asymptotically optimal (up to constant factors).