An Algebraic Approach for High-level Text Analytics

A semiring is a set $R$ with two binary operations addition $\oplus$ and multiplication $\odot$, such that, 1) $\oplus$ is associative and commutative and has an identity element $0\in R$; 2) $\odot$ is associative with an identity element $1\in R$; 3) $\odot$ distributes over $\oplus$; and 4) $\odot$ by 0 annihilates $R$.

(Golan, 2013) A semiring $R$ is partially ordered if and only if there exists a partial order relation $\leq$ on $R$ satisfying the following conditions for all $a,b\in R$:

• •

  If $a\leq b$, then $a\oplus c\leq b\oplus c$;

• •

  If $a\leq b$ and $0\leq c$, then $a\odot c\leq b\odot c$ and $c\odot a\leq c\odot b$.

The Text Associative Array (TAA) $\mathbf{A}$ is defined as a mapping:

$$\mathbf{A}:K_{1}\times K_{2}\to R$$

where $K_{1}$ and $K_{2}$ are two key sets (named row key set and column key set respectively), and $R$ is a partially-ordered semiring (Definition 2.2). We call $K_{1}\times K_{2}$ “the dimension of $\mathbf{A}$”, and denote $\mathbf{A}.K_{1}$, $\mathbf{A}.K_{2}$ and $\mathbf{A}.K$ as the row key set, column key sets, and set of key pairs of $\mathbf{A}$, respectively.

Given two TAAs $\mathbf{A},\mathbf{B}:K_{1}\times K_{2}\to R$, the addition operation $\mathbf{C}=(\mathbf{A}\oplus\mathbf{B}):K_{1}\times K_{2}\to R$ is defined as,

$$\mathbf{C}(k_{1},k_{2})=(\mathbf{A}\oplus\mathbf{B})(k_{1},k_{2})=\mathbf{A}(k_{1},k_{2})\oplus\mathbf{B}(k_{1},k_{2}).$$

Define $\mathbb{0}_{K_{1},K_{2}}$ as a TAA where $\mathbb{0}_{K_{1},K_{2}}(k_{1},k_{2})=0$ for $\forall k_{1}\in K_{1},k_{2}\in K_{2}$. $\mathbb{0}_{K_{1},K_{2}}$ serves as an identity for addition operation on key set $K_{1}\times K_{2}$.

Given two TAAs $\mathbf{A},\mathbf{B}:K_{1}\times K_{2}\to R$, the Hadamard product operation $\mathbf{C}=(\mathbf{A}\odot\mathbf{B}):K_{1}\times K_{2}\to R$ is defined as,

$$\mathbf{C}(k_{1},k_{2})=(\mathbf{A}\odot\mathbf{B})(k_{1},k_{2})=\mathbf{A}(k_{1},k_{2})\odot\mathbf{B}(k_{1},k_{2}).$$

Define $\mathbb{1}_{K_{1},K_{2}}$ as a TAA where $\mathbb{1}_{K_{1},K_{2}}(k_{1},k_{2})=1$ for $\forall k_{1}\in K_{1},k_{2}\in K_{2}$. $\mathbb{1}_{K_{1},K_{2}}$ serves as an identity for Hadamard product on key set $K_{1}\times K_{2}$.

Given two TAAs $\mathbf{A}:K_{1}\times K_{2}\to R$ and $\mathbf{B}:K_{2}\times K_{3}\to R$, the array multiplication operation $\mathbf{C}=(\mathbf{A}\otimes\mathbf{B}):K_{1}\times K_{3}\to R$ is defined as,

$$\mathbf{C}(k_{1},k_{3})=(\mathbf{A}\otimes\mathbf{B})(k_{1},k_{3})=\bigoplus_{k_{2}\in K_{2}}\mathbf{A}(k_{1},k_{2})\odot\mathbf{B}(k_{2},k_{3}).$$

Given two key sets $K_{1}$ and $K_{2}$, and a partial function $f:K_{1}\hookrightarrow K_{2}$, the array identity $\mathbb{E}_{K_{1},K_{2},f}:K_{1}\times K_{2}\to R$ is defined as a TAA such that

$$\mathbb{E}_{K_{1},K_{2},f}(k_{1},k_{2})=\begin{cases}1,&\text{if }k_{1}\in\text{dom }f\text{ and }k_{2}=f(k_{1});\\ 0,&\text{otherwise}.\end{cases}$$

Specifically, if $\text{dom }f=K_{1}\cap K_{2}$ and $f(k_{1})=k_{1}$ for $\forall k_{1}\in K_{1}$, $\mathbb{E}_{K_{1},K_{2},f}$ is abbreviated to $\mathbb{E}_{K_{1},K_{2}}$.

Given two TAAs $\mathbf{A}:K_{1}\times K_{2}\to R$ and $\mathbf{B}:K_{3}\times K_{4}\to R$, their Kronecker product $\mathbf{C}=\mathbf{A}\circledast\mathbf{B}:(K_{1}\times K_{3})\times(K_{2}\times K_{4})$ is defined by

$$\mathbf{C}((k_{1},k_{3}),(k_{2},k_{4}))=\mathbf{A}(k_{1},k_{2})\odot\mathbf{B}(k_{3},k_{4}).$$

Given a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$, its transpose, denoted by $\mathbf{A}^{\mathsf{T}}$, is defined by $\mathbf{A}^{\mathsf{T}}:K_{2}\times K_{1}\to R$ where $\mathbf{A}^{\mathsf{T}}(k_{2},k_{1})=\mathbf{A}(k_{1},k_{2})$ for $k_{1}\in K_{1}$ and $k_{2}\in K_{2}$.

Given a text corpus, a document term matrix is defined as a TAA $\mathbf{M}:D\times T\to R$ where $D$ and $T$ are the document set and term set of a text corpus.

Given a document $d$, the term index matrix is defined as a TAA, $\mathbf{N}:T_{d}\times I\to\{0,1\}$ where $T_{d}=\{d\}\times T$ is the set of terms in document $d$ and $I=\{1,\cdots,I_{d}\}$ is the index set ($I_{d}$ is the size of $d$). Specifically, for $(d,t)\in T_{d}$ and $i\in I$,

$$\mathbf{N}((d,t),i)=\begin{cases}1,&\text{if }i\text{-th word of document }d\text{ is }t;\\ 0,&\text{otherwise}.\end{cases}$$

There are two types of term vectors. 1) Given a set of terms $T$ of a document $d$, the term vector is defined as a TAA $\mathbf{V}:\{d\}\times T\to R$. 2) Given a set of terms $T$ for a collection of documents $D$, $\mathbf{V}:\{1\}\times T\to R$ is a term vector for the corpus $D$.

Given a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$ and two projection sets $K_{1}^{\prime}\subseteq K_{1}$, $K_{2}^{\prime}\subseteq K_{2}$, we define the extraction operation as

$$\Pi_{K_{1}^{\prime},K_{2}^{\prime}}(\mathbf{A})=\mathbb{E}_{K_{1}^{\prime},K_{1}}\otimes\mathbf{A}\otimes\mathbb{E}_{K_{2}^{\prime},K_{2}}^{\mathsf{T}}.$$

Let $\mathbf{B}=\Pi_{K_{1}^{\prime},K_{2}^{\prime}}(\mathbf{A})$, we have $B(k_{1},k_{2})=A(k_{1},k_{2}),\text{ for }\forall(k_{1},k_{2})\in K_{1}^{\prime}\times K_{2}^{\prime}$.

Given a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$, suppose $K_{2}^{\prime}$ is another column key set and there exists a bijection $f:K_{2}\to K_{2}^{\prime}$. The column rename operation is defined as

$$\rho_{K_{1},K_{2}\to K_{2}^{\prime},f}(\mathbf{A})=\mathbf{A}\otimes\mathbb{E}_{K_{2},K_{2}^{\prime},f}.$$

Similarly, given another row key set $K_{1}^{\prime}$ and a bijection $f:K_{1}\to K_{1}^{\prime}$, the row rename operation is defined as

$$\rho_{K_{1}\to K_{1}^{\prime},K_{2},f}(\mathbf{A})=\mathbb{E}_{K_{1}^{\prime},K_{1},f^{-1}}\otimes\mathbf{A}.$$

The subscript $f$ can be omitted if the bijection is clear, e.g., $|\text{dom }f|=1$. In addition, the row rename operation and column rename operation can be combined together as $\rho_{K_{1}\to K_{1}^{\prime},K_{2}\to K_{2}^{\prime}}(\mathbf{A})$. Our rename operator is more general than the rename operation of relational algebra since it supports both row key set and column key set renaming.

Given a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$ and a function $f:R\to R$, define the apply operator by $\mathbf{Apply}_{f}(\mathbf{A}):K_{1}\times K_{2}\to R$ where,

$$\mathbf{Apply}_{f}(\mathbf{A})(k_{1},k_{2})=f(\mathbf{A}(k_{1},k_{2})),\forall(k_{1},k_{2})\in K_{1}\times K_{2}.$$

Given a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$ and an indicator function $f:R\to\{0,1\}$, define the filter operation on $\mathbf{A}$ as

$$\mathbf{B}=\mathbf{Filter}_{f}(\mathbf{A})=\sigma_{f}(\mathbf{A}):K_{1f},K_{2f}\to R,$$

where $K_{1f}\times K_{2f}=\{(k_{1},k_{2})|(k_{1},k_{2})\in K_{1}\times K_{2}\text{ and }f(\mathbf{A}(k_{1},k_{2}))=1\}$, and $\mathbf{B}(k_{1},k_{2})=\mathbf{A}(k_{1},k_{2})$.

Given a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$, for any $k\in K_{1}$, we extract a TAA $\mathbf{V}=\Pi_{\{k\},:}(\mathbf{A})$ of dimension $\{k\}\times K_{2}$. Since $R$ is a partially-ordered semiring (Definition 2.2), the value set $\{\mathbf{V}(k,x)|\forall x\in K_{2}\}\subseteq R$ inherits the partial order from $R$, which implies an order $\mathbf{V}(k,x_{1})\leq\mathbf{V}(k,x_{2})\leq\cdots\leq\mathbf{V}(k,x_{|K_{2}|})$. Define $\mathbf{Idx}(k,x_{i})=i$, then the sort by column operation is defined as

$$\mathbf{Sort}_{2}(\mathbf{A}):K_{1}\times K_{2}\to\{1,\cdots,|K_{2}|\},$$

where $\mathbf{Sort}_{2}(\mathbf{A})(k,x)=\mathbf{Idx}(k,x)$. Similarly, we have sort by row operation defined as

$$\mathbf{Sort}_{1}(\mathbf{A}):K_{1}\times K_{2}\to\{1,\cdots,|K_{1}|\}.$$

When the column key dimension or row key dimension is 1 (e.g., for a term vector), $\mathbf{Sort}_{1}$ or $\mathbf{Sort}_{2}$ is abbreviated to $\mathbf{Sort}$.

Given two TAAs $\mathbf{A}:K_{A1}\times K_{A2}$ and $\mathbf{B}:K_{B1}\times K_{B2}$, if $(K_{A1}\times K_{A2})\cap(K_{B1}\times K_{B2})=\emptyset$, then merge operation can be applied on them, and it is defined as,

$$\mathbf{C}=\mathbf{Merge}(\mathbf{A},\mathbf{B}):K_{1}\times K_{2}\to R$$

where $K_{1}=K_{A1}\cup K_{B1}$ and $K_{2}=K_{A2}\cup K_{B2}$, and

$\displaystyle\mathbf{C}(k_{1},k_{2})=\begin{cases}\mathbf{A}(k_{1},k_{2}),&\text{if }(k_{1},k_{2})\in K_{A1}\times K_{A2};\\ \mathbf{B}(k_{1},k_{2}),&\text{if }(k_{1},k_{2})\in K_{B1}\times K_{B2};\\ 0,&\text{otherwise.}\end{cases}$

Given an elementwise binary operator $\mathbf{OP}$ on associative arrays, e.g., $\oplus$ and $\odot$, a term vector $\mathbf{V}:\{1\}\times T\to R$ and a document-term matrix $\mathbf{M}:D\times T\to R$, the expand operator is defined as

$$\mathbf{Expand}_{\mathbf{OP}}(\mathbf{V},\mathbf{M})=\rho_{\{1\}\times D\to D,T\times\{1\}\to T}\left(\mathbf{V}\circledast\mathbb{1}_{D,\{1\}}\right)\,\,\mathbf{OP}\,\,\mathbf{M}.$$

This operator implicitly expands the term vector $\mathbf{V}$ to generate another associative array $\mathbf{M^{\prime}}:D\times T\to R$ where $\mathbf{M^{\prime}}(d,t)=\mathbf{V}(1,t),\forall d\in D\text{ and }\forall t\in T$, and then applies $\mathbf{OP}$ on $\mathbf{M^{\prime}}$ and $\mathbf{M}$.

Given an associative array $\mathbf{A}:K_{1}\times K_{2}\to R$, the flatten operation is defined by $\mathbf{Flatten}(\mathbf{A}):\{1\}\times(K_{1}\times K_{2})\to R$ where

$$\mathbf{Flatten}(\mathbf{A})(1,(k_{1},k_{2}))=\mathbf{A}(k_{1},k_{2})\text{ for }\forall(k_{1},k_{2})\in K_{1}\times K_{2}.$$

Given a term-index matrix $\mathbf{N}:(\{d\}\times T)\times I\to R$, and a non-negative integer $n$, define the left shift operator by $\mathbf{LShift}_{n}(\mathbf{N}):(\{d\}\times T)\times I\to R$ where

	$\displaystyle\mathbf{LShift}_{n}(\mathbf{N})$	$\displaystyle=\mathbf{LShift}_{1}(\mathbf{LShift}_{n-1}(\mathbf{N}))\text{ and }$
	$\displaystyle\mathbf{LShift}_{1}(\mathbf{N})((d,t),i)$	$\displaystyle=\begin{cases}\mathbf{N}((d,t),i+1),&\text{if }i<|T|;\\ 0,&\text{if }i=|T|;.\end{cases}$

Suppose there are two term-index matrices with the same index set $I$, $\mathbf{N}_{1}:(\{d\}\times T)\times I\to R$ and $\mathbf{N}_{2}:(\{d\}\times T)\times I\to R$, the union operation on $\mathbf{N}_{1}$ and $\mathbf{N}_{2}$ is defined by

	$\displaystyle\mathbf{Union}(\mathbf{N_{1}},\mathbf{N_{2}})$	$\displaystyle=\rho_{(\{d\}\times T)\times(\{d\}\times T)\to\{d\}\times(T\times T),I\times I\to I}$
		$\displaystyle\qquad\qquad\left(\Pi_{:,\{(i,i)|i\in I\}}(\mathbf{N}_{1}\circledast\mathbf{N}_{2})\right).$

Suppose $\mathbf{N}=\mathbf{Union}(\mathbf{N}_{1},\mathbf{N}_{2})$, then

$\displaystyle\mathbf{N}((d,(t_{1},t_{2})),i)=\begin{cases}1,&\text{if }\mathbf{N}_{1}((d,t_{1}),i)=1\text{ and }\mathbf{N}_{2}((d,t_{2}),i)=1;\\ 0,&\text{otherwise}.\end{cases}$

The sum operation takes a TAA $\mathbf{A}:K_{1}\times K_{2}\to R$ and an integer which can take the value of 0, 1 or 2 as inputs and will have different semantics based on the integer value:

	$\displaystyle\mathbf{B}:\{1\}\times K_{2}$	$\displaystyle=\mathbf{Sum}_{1}(\mathbf{A})\text{ where }B(1,k_{2})=\bigoplus_{k_{1}\in K_{1}}\mathbf{A}(k_{1},k_{2});$
	$\displaystyle\mathbf{B}:{K_{1}}\times\{1\}$	$\displaystyle=\mathbf{Sum}_{2}(\mathbf{A})\text{ where }B(k_{1},1)=\bigoplus_{k_{2}\in K_{2}}\mathbf{A}(k_{1},k_{2}).$