9
$\begingroup$

We know that a Taylor polynomial can approximate any continuous function. As @DemetriPananos noticed, Logistic regression seeks to estimate the coefficients for a model and any cut off is imposed post facto. But suppose there's a best possible decision boundary for our data. By "best possible" I mean a decision boundary that perfectly separates two classes.

Assume, for the sake of simplicity, that there is no data points from positive class that overlay data points from negative class (as @Sycorax suggested). For example consider this plot:

enter image description here

The blue line perfectly separates two classes. But the blue line itself doesn't represent a function.

  1. If we were to increase a degree of polynomial in our logistic regression, can we be sure that such a perfect decision boundary would be found for any data that can be perfectly separated?

  2. If the answer to my first question is "yes", then how to prove (or show) it?

$\endgroup$
12
  • 1
    $\begingroup$ $f(x_1, x_2) = (x_1)^2 + (x_2)^2$ is a polynomial, with $f(x_2, x_2) = 1$ forming a decision boundary. $\endgroup$
    – jwimberley
    Oct 26 at 14:44
  • 2
    $\begingroup$ This answer to an unrelated question includes a picture of a decision boundary constructed by quadratic features. stats.stackexchange.com/questions/164048/… $\endgroup$
    – Sycorax
    Oct 26 at 14:54
  • $\begingroup$ @jwimberley, Yes, there is a cut off made by $z = 1$ plane. But how to show that for any data can be found such a cut off, provided we use polynomial of high enough degree? $\endgroup$
    – mathgeek
    Oct 26 at 15:04
  • 1
    $\begingroup$ Perhaps you should edit your question to state precisely what you do mean. Your comments describe a scenario involving "any data," but now you've said you're only considering some very specific cases. Even if we go by the pictures you've shared, it's not clear whether or not there are + examples "hidden under" the yellow circle examples. $\endgroup$
    – Sycorax
    Oct 26 at 15:20
  • 2
    $\begingroup$ This question seems to be based on confusing polynomial functions $p:\mathbb{R}\to\mathbb{R}$ with zeros with polynomial functions $p:\mathbb{R}^2\to\mathbb{R}.$ $\endgroup$
    – whuber
    Oct 26 at 16:43
9
$\begingroup$

Comments to the question suggest the following interpretation:

Given any two non-overlapping finite collections of points $A$ and $B$ in a Euclidean space $E^n,$ does there always exist a polynomial function $f_{A,B}:E^n\to\mathbb R$ that perfectly separates the collections? That is, $f_{A,B}$ has positive values on all points of $A$ and negative values on all points of $B.$

The answer is yes, by construction.

Let $|\ |$ be the usual Euclidean distance. Its square is a quadratic polynomial. Specifically, using any orthogonal coordinate system write $\mathbf{x}=(x_1,\ldots, x_n)$ and $\mathbf{y}=(y_1,\ldots, y_n).$ We have

$$|\mathbf{x}-\mathbf{y}| = \sum_{i=1}^n (x_i-y_i)^2,$$

which explicitly is a quadratic polynomial function of the coordinates.

Define $$f_{A,B}(\mathbf x)=\left[\sum_{\mathbf y\in A}\frac{1}{|\mathbf x-\mathbf y|^2}-\sum_{\mathbf y\in B}\frac{1}{|\mathbf x-\mathbf y|^2}\right]\prod_{\mathbf y\in A\cup B}|\mathbf x-\mathbf y|^2.$$

Notice how $f_{A,B}$ is defined as a product. The terms on the right hand side clear the denominators of the fractions on the left, showing that $f$ is actually defined everywhere on $E^n$ and is a polynomial function.

The function in the left term of the product has poles (explodes to $\pm \infty$) precisely at the data points $\mathbf x \in A\cup B.$ At the points of $A$ its values diverge to $+\infty$ and at the points of $B$ its values diverge to $-\infty.$ Because the product at the right is non-negative, we see that in a sufficiently small neighborhood of $A$ $f_{A,B}$ is always positive and in a sufficiently small neighborhood of $B$ $f_{A,B}$ is always negative. Thus $f_{A,B}$ does its job of separating $A$ from $B,$ QED.

Here is an illustration showing the contour $f_{A,B}=0$ for $80$ randomly selected points in the plane $E^2.$ Of these, $43$ were randomly selected to form the subset $A$ (drawn as blue triangles) and others form the subset $B,$ drawn as red circles. You can see this construction works because all blue triangles fall within the gray (positive) region where $f_{A,B}\gt 0$ and all the red circles fall within the interior of its complement where $f_{A,B}\lt 0.$

Figure

To see more examples, modify and run this R script that produced the figure. Its function f, defined at the outset, implements the construction of $f_{A,B}.$

#
# The columns of `A` are all data points.  The values of `I` are +/-1, indicating
# the subset each column belongs to.
#
f <- function(x, A, I) {
  d2 <- colSums((A-x)^2)
  j <- d2 == 0           # At most one point, assuming all points in `A` are unique
  if (sum(j) > 0)        # Avoids division by zero
    return(prod(d2[!j]) * prod(I[j])) 
  sum(I / d2) * prod(d2)
}
#
# Create random points and a random binary classification of them.
#
# set.seed(17)
d <- 2   # Dimensions                 
n <- 80  # total number of points
p <- 1/2 # Expected Fraction in `A`
A <- matrix(runif(d*n), d)
I <- sample(c(-1,1), ncol(A), replace=TRUE, prob=c(1-p, p))
#
# Check `f` by applying it to the data points and confirming it gives the
# correct signs.
#
I. <- sign(apply(A, 2, f, A=A, I=I))
if (!isTRUE(all.equal(I, I.))) stop("f does not work...")
#
# For plotting, compute values of `f` along a slice through the space.
#
slice <- rep(1/2, d-2) # Choose which slice to plot
X <- Y <- seq(-0.2, 1.2, length.out=201)
Z <- matrix(NA_real_, length(X), length(Y))
for (i in seq_along(X)) for (j in seq_along(Y)) 
    Z[i, j] <- f(c(X[i], Y[j], slice), A, I)
#
# Display a 2D plot.
#
image(X, Y, sign(Z), col=c("Gray", "White"), xaxt="n", yaxt="n", asp=1, bty="n",
      main="Polynomial separator of random points")
contour(X, Y, Z, levels=0, labels="", lwd=2, labcex=0.001, add=TRUE)
points(t(A), pch=ifelse(I==1, 19, 17), col=ifelse(I==1, "Red", "Blue"))
$\endgroup$
5
  • $\begingroup$ Thank you so much! That is just a perfect answer, though it takes some time to digest :) $\endgroup$
    – mathgeek
    Oct 27 at 17:47
  • $\begingroup$ Going through your answer again I came up with a question. Can I interpret it in the following way? Since for a data point $x$ to be in positive class just requires positive value of polynomial $P(x)$ in hypothesis $\frac{1}{1 + e^{-P(x)}}$, then according to the fact that a polynomial of high enough degree can approximate any continuous function, we can come up with a decision boundary of any form, because that polynomial $P(x)$ just needs to spit positive values for our positive class data points and negative values for our negative class data points... $\endgroup$
    – mathgeek
    Nov 1 at 8:40
  • $\begingroup$ ...Assuming there is no overlapping points from different classes, there is always a suitable function $f(x)$ that does its job spitting values of different sign for different classes (no matter what values, they just need to be of different signs). And for $n$ data points you need at most polynomial of degree $n$, since $n$-degree polynomial can always pass through $n$ non-overlapping points. $\endgroup$
    – mathgeek
    Nov 1 at 8:40
  • 2
    $\begingroup$ That is correct. However, constructing such polynomials requires a $O(n^2)$ algorithm, whereas the method I have shown here is $O(n).$ That is one reason I chose it. $\endgroup$
    – whuber
    Nov 1 at 12:55
  • $\begingroup$ Thank you again! :) $\endgroup$
    – mathgeek
    Nov 1 at 13:31
7
$\begingroup$

There are a few problems with your first paragraph which may make your question difficult to answer.

We know that a polynomial can approximate any function.

Can it? If you're referring to a Taylor polynomial, then the function must be smooth. Not every function is a smooth function.

In binary logistic regression we're trying to fit a decision boundary to our data.

This isn't true. Logistic regression seeks to estimate the coefficients for a model

$$ p(x) = \dfrac{1}{1 + \exp(-x^T\beta)} $$

There is no decision boundary here, and any cut off is imposed post facto.

$\endgroup$
3
  • $\begingroup$ Thank you for your comment. I agree, it was my fault to poorly formulate the first paragraph, but what about my question? Can polynomial logistic regression learn any arbitrary decision boundary? $\endgroup$
    – mathgeek
    Oct 26 at 15:00
  • 1
    $\begingroup$ @mathgeek The question is still not really a great one. With finite data, we won't be able to learn the boundary exactly. That being said, we might be able to do "good enough" for some sense of good enough. Polynomials can can form a variety of decision boundaries, so the polynomial might be able to do good enough, but as I alluded to there are a bunch of functions which can not be expressed as a polynomial. $\endgroup$ Oct 26 at 15:20
  • 3
    $\begingroup$ Your first assertion (that polynomials can only approximate "smooth" functions) is incorrect. (In mathematics, "smooth" always means having a sufficient number of derivatives--usually infinitely many.) The Stone-Weierstrass theorem asserts that any continuous function on an interval can be approximated by polynomials. Fourier analysis abounds with polynomial bases that can approximate merely piecewise continuous functions. $\endgroup$
    – whuber
    Oct 26 at 16:41

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.