inner product of multisets



A multiset 𝒳=⟨X,μ X⟩\mathcal{X} = \langle X,\mu_X\rangle consists of a set XX and a function μ X:U→ℕ\mu_X:U\to\mathbb{N}, where UU is a universal set and μ X(e)>0\mu_X(e) \gt 0 if and only if e∈Xe\in X.

We can add two multisets 𝒳=⟨X,μ X⟩\mathcal{X} = \langle X,\mu_X\rangle and 𝒴=⟨Y,μ Y⟩\mathcal{Y} = \langle Y,\mu_Y\rangle to get

𝒳+𝒴=⟨X∪Y,μ X+μ Y⟩.\mathcal{X} + \mathcal{Y} = \langle X\cup Y,\mu_X+\mu_Y\rangle.

Note that we can write

k𝒳=⟨X,kμ X⟩k\mathcal{X} = \langle X,k\mu_X\rangle

for k∈ℕk\in\mathbb{N}.

We can also define an inner product of multisets via

⟨𝒳,𝒴⟩=∑ e∈𝒳∪𝒴μ X(e)μ Y(e).\langle \mathcal{X},\mathcal{Y}\rangle = \sum_{e\in\mathcal{X}\cup \mathcal{Y}} \mu_X(e) \mu_Y(e).

Note that when 𝒳\mathcal{X} and 𝒴\mathcal{Y} are simply sets, μ X\mu_X and μ Y\mu_Y are the characteristic functions and

⟨𝒳,𝒴⟩=|X∩Y|,\langle \mathcal{X},\mathcal{Y}\rangle = |X\cap Y|,

where |⋅||\cdot| denotes the cardinality of the set.

Using this inner product, we can define the angle between multisets as

cosθ 𝒳,𝒴=⟨𝒳,𝒴⟩⟨𝒳,𝒳⟩⟨𝒴,𝒴⟩.\cos\theta_{\mathcal{X},\mathcal{Y}} = \frac{\langle \mathcal{X},\mathcal{Y}\rangle}{\sqrt{\langle \mathcal{X},\mathcal{X}\rangle \langle \mathcal{Y},\mathcal{Y}\rangle}}.

In particular, when 𝒳=𝒴\mathcal{X}=\mathcal{Y} we have

cosθ 𝒳,𝒴=1cos\theta_{{\mathcal{X}},{\mathcal{Y}}} = 1

and when X∩Y=∅X\cap Y = \emptyset we have

cosθ 𝒳,𝒴=0.cos\theta_{{\mathcal{X}},{\mathcal{Y}}} = 0.

When 𝒳\mathcal{X} and 𝒴\mathcal{Y} are simply sets, the angle between them is given by

cosθ 𝒳,𝒴=|X∩Y||X||Y|.cos\theta_{{\mathcal{X}},{\mathcal{Y}}} = \frac{|X\cap Y|}{\sqrt{|X||Y|}}.

With this notion of addition, the collection of multisets in UU becomes the ℕ\mathbb{N}-module (that is abelian monoid) ℕ U\mathbb{N}^U; this inner product makes it an inner product space analogous to the Banach space ℝ n\mathbb{R}^n.

Machine Learning

The inner product of multisets is closely related to the “bag of words” kernel in machine learning (see n-Cafe).

Last revised on October 28, 2009 at 17:39:46. See the history of this page for a list of all contributions to it.