# Is a linear discriminant function actually "linear"?

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

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?

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.