Past exam of the advanced topics in statistical machine learning course of the University of Oxford / 2025 / 2 / a

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii
- iii a
  - Solution iii

i

Solution

In this setting a positive-semidefinite kernel is an inner-product similarity: there exist a real Hilbert space

H

and a feature map

φ : X \to H

such that

k (x, x^{'}) = ⟨ φ (x), φ (x^{'}) ⟩_{H} .

The feature map may be infinite-dimensional. Equivalently,

k

is symmetric and every finite kernel matrix is a positive semidefinite matrix. The equivalence follows by forming the canonical feature space of a positive-semidefinite kernel and taking its Hilbert space completion.

ii

Solution

For every

m \geq 1

, every choice

x_{1}, \dots, x_{m} \in X

, and every coefficient vector

α \in R^{m}

, the required condition is

i, j = 1 \sum m α_{i} α_{j} k (x_{i}, x_{j}) \geq 0 .

Thus

α^{T} K α \geq 0

for the kernel matrix

K

. For a feature map, this follows from

\sum_{i, j} α_{i} α_{j} ⟨ φ (x_{i}), φ (x_{j})⟩ = ∥ \sum_{i} α_{i} φ (x_{i}) ∥_{H}^{2} \geq 0.

In kernel methods, the term positive-definite kernel commonly uses this non-strict inequality. Strict positive definiteness is the stronger requirement that the expression be positive for distinct inputs and every nonzero

α

; it is not required here.

iii

Solution

The closure property of positive-semidefinite kernels gives three constructions, each seen directly from the feature maps

φ_{1}, φ_{2}

.

Nonnegative sums: $k = α k_{1} + β k_{2}$ , for $α, β \geq 0$ . Its feature map is $(α φ_{1} (x), β φ_{2} (x))$ in the Hilbert space direct sum; expanding its inner product gives $k$ .
Pointwise products: $k (x, x^{'}) = k_{1} (x, x^{'}) k_{2} (x, x^{'})$ . In the Hilbert tensor product, use $φ (x) = φ_{1} (x) \otimes φ_{2} (x)$ : the inner product of two such elementary tensors is the product of their two inner products.
Input-dependent weighting: $k (x, x^{'}) = a (x) k_{1} (x, x^{'}) a (x^{'})$ for any real-valued function $a$ . Its feature map is $a (x) φ_{1} (x)$ , so signs of $a$ are allowed. Nonnegative scalar multiplication is the special case of constant $a$ ; the weighting factor $a (x) a (x^{'})$ is itself a rank-one positive-semidefinite kernel.

Another useful consequence is pullback: if

h : X \to Z

and

k_{0}

is a positive-semidefinite kernel on

Z

, then

k_{0} (h (x), h (x^{'}))

has feature map

φ_{0} \circ h

.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version