Chris Bishop introduces the multi-class linear discriminant functions (a.k.a. linear machine) in PRML as follows (p. 183):

enter image description here

In proving the convexity of decision regions, it's assumed that $y_k(\cdot)$ is linear in $\mathbf{x}$. If I recall, a linear function $f(x)$ must preserve vector addition, i.e. $f(x+y) = f(x) + f(y)$

But according to the definition of $y_k$,

$$y_k(\mathbf{x} + \mathbf{y}) = \mathbf{w}_k^\top \mathbf{x} + \mathbf{w}_k^\top \mathbf{y} + w_{k0} \neq \mathbf{w}_k^\top \mathbf{x} + w_{k0} + \mathbf{w}_k^\top \mathbf{y} + w_{k0} = y_k(\mathbf{x}) + y_k(\mathbf{y}) $$

I understand $y_k$ is linear in the expanded input $\tilde{\mathbf{x}} = (1, \mathbf{x})$ with the dummy input $1$, but I don't see how it's linear in $\mathbf{x}$ (it's clearly affine), so I didn't follow (4.12) and the argument that each decision region (in the original input space $\mathbf{x}$) is convex. Oh and what does "singly-connected" mean here?


1 Answer 1


Affinity is clearly enough for (4.12) to hold. Since

$$\hat{\mathbf{x}}=\lambda\mathbf{x}_A + (1-\lambda)\mathbf{x}_B $$

then, multiplying LHS & RHS by $\mathbf{w}^T_k$ and adding $w_{k0}$, we get

$$\mathbf{w}^T_k\hat{\mathbf{x}}+w_{k0}=y_k (\hat{\mathbf{x}})=\lambda\mathbf{w}^T_k\mathbf{x}_A + (1-\lambda)\mathbf{w}^T_k\mathbf{x}_B + w_{k0}$$

Writing $w_{k0}=(\lambda+1- \lambda)w_{k0}$ we have $$y_k (\hat{\mathbf{x}})=\lambda\mathbf{w}^T_k\mathbf{x}_A + (1-\lambda)\mathbf{w}^T_k\mathbf{x}_B+(\lambda+1- \lambda)w_{k0}=\lambda(\mathbf{w}^T_k\mathbf{x}_A +w_{k0})+(1-\lambda)(\mathbf{w}^T_k\mathbf{x}_B+w_{k0})=\lambda y_k(\mathbf{x}_A)+(1-\lambda) y_k(\mathbf{x}_B)$$

Which is (4.12).

Concerning your other question: roughly speaking, a singly connected set $S \subseteq \mathbb {R}^n $ is a set such that every closed curve fully included in $S $ can be continously deformed to a point in $S $ without ever going out from $S $. Intuitively this means that the set has no holes. Here we actually proved that the set is convex, i.e., that each segment whose extremes are in $S$ , is completely included in $S $. However a convex set is singly-connected because if there was a hole, then you could draw a segment across the hole, whose extremes were in $S$, but which wouldn't be completely included in $S$. For more details and/or proofs on the topology of subsets of $\mathbb {R}^n $, you may ask on the Mathematics SE site.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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