Word morphing

I assume you’re familiar with image morphing – the process of changing one image into another through a seamless transition. So how would word morphing look like? If we want to do a seamless transition from one word into another, through which words would it pass?

In this post I’ll describe how I employed word2vec’s embeddings and $A^*$ search algorithm to morph between words.

In order to perform word morphing, we’ll define a graph $G$ where the set of nodes $N$ represent words, and there’s some weight function $f : N \times N \rightarrow \mathbb{R}_{\geq 0}$. Given a start word $n_{\text{start}}$ and an end word $n_{\text{end}}$, our goal is to find a path within the graph which minimizes the sum of weights induced by $f$:

$\text{argmin}_{\langle n_1, …, n_k \rangle : k \in \mathbb{N}, n_1, …, n_k \in N, n_1 = n_{\text{start}}, n_k = n_{\text{end}}}\sum_{i=1}^{k-1} f(n_i, n_{i+1})$

Usually when people talk about word morphing they mean searching for a path between $n_{\text{start}}$ and $n_{\text{end}}$ where there’s an edge only between words such that one can be achieved from the other by changing one letter, as can be seen here. In this case, $f(n_1, n_2)$ is 1 when such a change exists, and $\infty$ otherwise.

In this post I’ll show you how to morph between semantically similar words, i.e. $f$ will be related to semantics. Here’s an example to illustrate the difference between the two approaches: given $n_{\text{start}} = \text{tooth}$, $n_{\text{end}} = \text{light}$, the approach of changing one character at a time can result in

tooth, booth, boots, botts, bitts, bitos, bigos, bigot, bight, light

while the semantics approach which will be defined in this post results in

tooth, retina, X_ray, light