## 2 Text Mining Application  
Let \(\mathbf{T}\) be a finite text collection (for example a collection of mail or news items). We denote the size of the set \(\mathbf{T}\) by \(|\mathbf{T}|\). We will be concerned with two subsets of \(\mathbf{T}\):  
1. \(\mathbf{R}\)-the set of \"relevant\" texts (text not labeled as spam),
2. \(\mathbf{F}\)-the set of texts that contain a \"feature\" (word or term for example). We denote complements of the sets by \(\overline{\mathbf{R}}\), \(\overline{\mathbf{F}}\) respectably (_i.e._, \(\mathbf{R}\cup\overline{\mathbf{R}}=\mathbf{F}\cup\overline{\mathbf{F}}= \mathbf{T}\)), and consider the relative size of the four sets \(\mathbf{F}\cap\overline{\mathbf{R}}\), \(\mathbf{F}\cap\mathbf{R}\), \(\overline{\mathbf{F}}\cap\overline{\mathbf{R}}\), and \(\overline{\mathbf{F}}\cap\mathbf{R}\) as follows:  
\[ \begin{array}{l}x_{11}(\mathbf{T})=\frac{|\mathbf{F}\cap\overline{\mathbf{R }}|}{|\mathbf{T}|},\ \ x_{12}(\mathbf{T})=\frac{|\mathbf{F}\cap\mathbf{R}|}{|\mathbf{T}|}\\ \\ x_{21}(\mathbf{T})=\frac{|\overline{\mathbf{F}}\cap\overline{\mathbf{R}}|}{| \mathbf{T}|},\ \ x_{22}(\mathbf{T})=\frac{|\overline{\mathbf{F}}\cap\mathbf{R}|}{| \mathbf{T}|}\end{array}  \tag{2}\]  
Note that  
\[0\leq x_{ij}\leq 1,\text{ and }x_{11}+x_{12}+x_{21}+x_{22}=1\]  
The function \(f\) is defined on the simplex (_i.e._, \(x_{ij}\geq 0\), \(\sum x_{ij}=1\)), and given by  
\[f(x_{11},x_{12},x_{21},x_{22})=\sum_{i,j}x_{ij}\log\left(\frac{x_{ij}}{(x_{i1 }+x_{i2})(x_{1j}+x_{2j})}\right) \tag{3}\]  
where \(\log x=\log_{2}x\) throughout the paper. We next relate empirical version of information gain Equation (3) and the information gain (see e.g., [12]). Let \(Y\) and \(X\) be random variable with know distributions  
\[P(Y=y_{i}),\ i=1,\ldots,n,\text{ and }P(X=x_{j}),\ j=1,\ldots,m\]  
Entropy of \(Y\) is defined by  
\[H(Y)=-\sum_{i=1}^{n}P(Y=y_{i})\log P(Y=y_{i}) \tag{4}\]  
Entropy of \(Y\) conditional on \(X=x\) denoted by \(H(Y|X=x)\) is defined by  
\[-\sum_{i=1}^{n}\frac{P(Y=y_{i},X=x)}{P(X=x)}\log\frac{P(Y=y_{i},X=x)}{P(X=x)} \tag{5}\]Conditional entropy \(H(Y|X)\) and information gain \(IG(Y|X)\) are given by  
\[ \begin{split} H(Y|X)=\sum_{j=1}^{m}& P(X=x_{j})H(Y|X=x_{j})\\ &\text{and}\\ IG(Y|X)=H(Y)-H(Y|X)\end{split}  \tag{6}\]  
Information gain is symmetric, indeed  
\[ \begin{split}& IG(Y|X)=\\ &\underset{i,j}{\sum}& P(Y=y_{i},X=x_{j})\log\frac{P(Y=y_{i},X=x_{j})}{P(X=x_{j})}\\ &-\underset{i}{\sum}& P(Y=y_{i})\log P(Y=y_{i})=\\ &\underset{i,j}{\sum}& P(Y=y_{i},X=x_{j})\log\frac{P(Y=y_{i},X=x_{j})}{P(Y=y_{i})P(X=x_{j})}\\ &=IG(X|Y)\end{split} \]  
Due to convexity of \(g(x)=-\log x\), information gain is non-negative  
\[ \begin{split} IG(Y|X)&=\underset{i,j}{\sum}& P(Y=y_{i},X=x_{j})g\left(\frac{P(Y=y_{i})P(X=x_{j})}{P(Y=y_{i},X=x_{j})} \right)\\ &\geq g\left(\underset{i,j}{\sum}& P(Y=y_{i},X=x_{j}) \frac{P(Y=y_{i})P(X=x_{j})}{P(Y=y_{i},X=x_{j})}\right)\\ &=& g\left(\underset{i,j}{\sum}& P(Y=y_{i})P(X=x_{j})\right)=-\log 1=0\end{split} \]  
It is easy to see that Equation (3) provides information gain for the \"feature\". As an example, we consider \(n\) agents installed on \(n\) different servers and a stream of texts arriving at the servers. Let \(\mathbf{T}_{h}=\{\mathbf{t}_{h1},\ldots,\mathbf{t}_{hw}\}\) be the last \(w\) texts received at the \(h^{th}\) server, with \(\mathbf{T}=\bigcup\limits_{h=1}^{n}\mathbf{T}_{h}\). Note that  
\[x_{ij}(\mathbf{T})=\sum_{h=1}^{n}\frac{|\mathbf{T}_{h}|}{|\mathbf{T}|}x_{ij}( \mathbf{T}_{h})\]  
_i.e._, entries of the global contingency table \(\{x_{ij}(\mathbf{T})\}\) are the average of the local contingency tables \(\{x_{ij}(\mathbf{T}_{h})\}\), \(h=1,\ldots,n\). For the given \"feature\" and a predefined positive threshold \(r\) we would like to verify the inequality  
\[f\left(x_{11}(\mathbf{T}),x_{12}(\mathbf{T}),x_{21}(\mathbf{T}),x_{22}( \mathbf{T})\right)-r>0\]  
while minimizing communication between the servers. Note that Equation (3) is a nonlinear function.