2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What is your definition of efficient? $\endgroup$ – D.W. Feb 16 '14 at 8:17
  • $\begingroup$ I think O(n) is possible but I'd like to be able to do it I'm as few operations as possible (assuming X is sorted). $\endgroup$ – Berk U. Feb 16 '14 at 16:27
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.