2
$\begingroup$

Let $\{\mathbf{x}_i, y_i \}$ be a set of binary-labeled samples ($\mathbf{x}_i \in \mathbb{R}^d, y_i \in \{a,b\}, a,b\in\mathbb{R}$). Let $\{ \mathbf{x}'_i, y_i \}$ be also such a set. Define $\mathbf{X} = [\mathbf{x}_1 \dots \mathbf{x}_N]^T , \mathbf{y}=[y_1 \dots y_N]^T$ and similarly for $\mathbf{X}'$. Define $\beta = (\mathbf{X}^T \mathbf{X})^{-1}\mathbf{X}^T \mathbf{y}$ and $\beta' = (\mathbf{X}'^T \mathbf{X}')^{-1}\mathbf{X}'^T \mathbf{y}$. Define $\widehat{\mathbf{y}} = \mathbf{X} \beta$, $\pmb{\varepsilon} = \widehat{\mathbf{y}} - \mathbf{y}$, and similarly for $\widehat{\mathbf{y}'}, \pmb{\varepsilon}'$.

Then how can we prove the following conjecture?

Conjcture. (a) Assume for any $i,j,k$ with $y_i = y_j \neq y_k $, $$ \|\mathbf{x}_i - \mathbf{x}_j \| = \|\mathbf{x}'_{i} - \mathbf{x}'_{j}\|, \qquad \| \mathbf{x}_i - \mathbf{x}_k \| < \| \mathbf{x}'_{i} - \mathbf{x}'_{k} \| $$ Then $\|\pmb{\varepsilon}\| > \|\pmb{\varepsilon}'\|$.

Probability perspective. Now we take a probabilistic perspective. Let $N$ be a natural number. Let $x$ be a random vector such that the above $\mathbf{x}_i$ are the realizations of it. Also define similarly $x'$. Let $y$ be a random vector that models $y_i$. (I.e., $y = \operatorname{label}(x) = \operatorname{label}(x')$.) Define $\widehat{y} = x^T\beta$ and $\widehat{y'} = x'^T\beta'$ where $$ \beta = (\mathbf{X}_n^T\mathbf{X}_N)^{-1}\mathbf{X}_N^T\mathbf{y}_N $$ with $X_n = [\mathbf{x}_1 \cdots \mathbf{x}_N]^T$ for the realizations $\mathbf{x}_i$ of $x$ and $\mathbf{y}_N = [y_1 \dots y_N]^T$ ($y_i = \operatorname{label}(\mathbf{x}_i)$), and $\beta'$ is defined similarly. Define $\varepsilon = \widehat{y} - y$ and similarly for $\varepsilon'$.

Conjecture. (b). Assume $\|\mathbb{E}[x\mid y=0] - \mathbb{E}[x|y=1]\| < \|\mathbb{E}[x'\mid y=0] - \mathbb{E}[x'\mid y=1]\| $ while $ \operatorname{var}(x\mid y=i) =\operatorname{var}(x'\mid y=i)$ for $i=0,1$. Then $$ \operatorname{var}(\varepsilon) > \operatorname{var}(\varepsilon'). $$

(c) The above holds true when $N \to \infty$.

Question. How can I possibly approach this type of problem? What kind of techniques should I consider? Should I ease or changethe problem?

Basically what the conjecture says is that if we increase inter-class distances while preserving intra-class variances, the regression error decreases. Intuitively I think this is quite clear especially for simple linear regression with one feature variable.

Improve this question
$\endgroup$
5
  • $\begingroup$ Conjecture a) looks false to me. Suppose there are no duplicated y's, and each x' = 2x. Then the hypothesis holds but the residuals are the same in the strong sense that epsilon = epsilon'. $\endgroup$
    – user44143
    Commented Oct 13, 2017 at 3:23
  • $\begingroup$ Yes you are right. But that is kind of triviality that I don't want to include. For that actually, we may just change all the $<$ to $\leq$. $\endgroup$
    – le4m
    Commented Oct 13, 2017 at 3:30
  • 1
    $\begingroup$ You might have a look at the eflving problem here projecteuclid.org/download/pdf_1/euclid.ss/1009212246 This subject deals with where you would put the regressors to minimize the prediction error if you could choose where to put them. $\endgroup$
    – user83457
    Commented Oct 13, 2017 at 8:44
  • $\begingroup$ Typically instead of $\varepsilon = \widehat{\mathbf{y}} - \mathbf{y},$ I'd write $\widehat\varepsilon = \widehat{\mathbf{y}} - \mathbf{y},$ letting $\widehat{\,\varepsilon\,}$ be the observable residuals and letting $\varepsilon$ be the true errors. Typically the true errors are independent whereas the observable residuals are constrained so that their sum is zero and the sum of their products with corresponding $x$-values is zero. $\endgroup$
    – Michael Hardy
    Commented Oct 13, 2017 at 20:53
  • $\begingroup$ If the typographical difference between $||a||$ and $\|a\|$ is not conspicuous to you, consider this difference: $$ \begin{align} \|a\|\|b\| & \text{ coded as \|a\|\|b\|} \\ ||a|| ||b|| & \text{ coded as ||a|| ||b||} \end{align} $$ I edited to change $||a||$ to $\|a\|. \qquad$ $\endgroup$
    – Michael Hardy
    Commented Oct 13, 2017 at 20:55

0

Reset to default

You must log in to answer this question.