\chapter{Introduction}

TODO:
\begin{itemize}
	\item przygotowanie repo - godzina
	\item ogłozsenie - godzina
\end{itemize}

SuperMatrix is a general tool for acquisition of lexico-semantic knowledge from large text corpora. It can handle large sparse matrices, compare rows using different Measures of Semantic Relatedness (MSR) \citep{budhirst}. The main requirements for SuperMatrix are: \emph{flexibility} and \emph{efficiency}. Flexibility is necessary for experimenting with different methods of MSR extraction. Efficient processing is also crucial, as statistical methods tends to yield better results with the increasing amount of data. The two requirements are often in opposition, thus we added a possibility of distributed processing using Message Passing Interface (MPI) and/or GNU Parallel. 

For portability reasons we wanted to avoid external dependencies as much as possible.  Only required
components are open-source and cross-platform.  CMake\footnote{\url{http://www.cmake.org/}} is used
for our build system.  SuperMatrix is also heavily dependant on availability of Boost
libraries\footnote{http://www.boost.org/}, Other used software packages are not so crucial for SuperMatrix,
e.g.\ SWIG is needed only for generating Python wrappers, CLUTO for clustering. 

There are several publications that directly describe SuperMatrix:
\begin{itemize}
	\item \bibentry{broda2008supermatrix}
	\item \bibentry{sm1}
	\item \bibentry{BroPiaSMIJDMMMM:11}
\end{itemize}

Several (selected) publications that describe research performed with the help of SuperMatrix:
\begin{itemize}
	\item \bibentry{PiaBro:07IDEAL}
	\item \bibentry{PiaSzpaBro07tsd}
	\item \bibentry{PiaSzpaBro07ltc}
	\item \bibentry{BroPia:IIS08}
	\item \bibentry{BroDerPiaSzpa:LREC08}
	\item \bibentry{DBLP:conf/ai/BrodaPS09}
	\item \bibentry{PawPiaBro09Trewir}
	\item \bibentry{BroPiaSzp:10CC}
\end{itemize}

Special Thanks goes to Tomas Capek for helping in making the SuperMatrix more friendly to end users.

\section{SuperMatrix Features}

The most important features of SuperMatrix are:

\begin{enumerate}
	\item High-level API to sparse matrices allows for handling very large co-incidence matrices (so far tested with
	matrices as large as ~20000 rows by about 300000 columns).
	\item Several Measures of Semantic Relatedness are implemented and ready to use, e.g., Lin's Measure \citep{Lin:98},
	Pointwise Mutual Information \citep{pantelCBC}, Generalised Rank Weight Function \citep{DBLP:conf/ai/BrodaPS09},
	etc.
	\item Ability to assemble measures of semantic relatedness from ready-to-use components (e.g., filters, weighting
	schemes, etc.).
	\item Clustering of objects described by matrices: several clustering algorithm implemented in SuperMatrix: RObust
	Clustering using linKs \citep{guha00rock}, Growing Hierarchical Self-Organising Maps \citep{ghsom}, Clustering by
	Committee \citep{pantelCBC}. 
	\item Ability to interact with CLUTO \citep{Karypis:02} for access to additional clustering algorithms.
	\item Creating matrices for whole documents in Vector Space Model.
	\item Creating words co-incidence matrices:
	\begin{itemize}
		\item for Polish words occurring in text window of fixed and variable (sentence-based) sizes.
		\item for Polish words occurring in lexico-semantic relations expressed as constraints written in WCCL language \citep{wccl}.
		\item for English based using dependency triples extracted by MiniPar \citep{Lin:93}. 
		\item for other languages using simple files with extracted triples of a form \verb|<word, relation, feature>|.
	\end{itemize}
	\item Handling of Polish multiword expressions described by morpho-syntactic constraints \citep{BroDerPia:08ss}.
	\item Written mainly in C++.
	\item Python bindings allows easier access to underling C++ structures.
	\item Generation of WordNet-Based Synonym Tests \citep{freitagetal:05} from Polish and English wordnet for automatic
	testing of measures of semantic relatedness. Generation of two extended versions of WordNet-Based Synonymy Test for
	Polish \citep{PiaSzpaBro07ltc}.
	\item Utility for simultaneously conducting of test on many measures of semantic relatedness and matrices. 
\end{enumerate}

\section{Packages overview}

SuperMatrix has been divided into several modules:

\begin{itemize}
	\item Matrices -- a library for storing and handling matrices.
	
	\item Comparator -- a library enabling computation of similarity between rows of matrices (i.e.,
	between LUs) using different MSRs.
	
	\item Set of tools, including (but not limited to) tools for creation of matrices: LUs by features, 
	tools for evaluating of MSRs, tools for joining different matrices and analysis of
	the matrix content, e.g., manually browsing selected rows and columns from any matrix, 
	including transformed and weighted matrices.
	
	\item Clustering -- package consisting of several clustering algorithms. SuperMatrix can
	interact with CLUTO \cite{Karypis:02} and perform Clustering by
	Committee(CBC) \cite{pantelCBC}, RObust Clustering using linKs (ROCK) \cite{guha00rock} and Growing
	Hierarchical Self-Organising Maps (GHSOM) \cite{ghsom}. We reimplemented ROCK and
	GHSOM with little modification, CBC was reimplemented as well as significantly extended \cite{BroPiaSzp:10CC}.

	\item Set of helper scripts and	SWIG\footnote{Simplified Wrapper and Interface Generator,
	\url{http://www.swig.org/}} wrappers for main classes of the Matrices and Comparator libraries.
\end{itemize}

Single package roughly corresponds to one directory in source code tree.

\section{Installation}
\label{sec:installation}

Requirements:

\begin{itemize}
	\item Boost Libraries\footnote{\url{http://www.boost.org/}}.
	\item CMake 2.6 or later\footnote{\url{http://www.cmake.org/}}.
	\item C++ compiler (preferably gcc 4.3 or later).
	\item Apache log4cxx\footnote{\url{http://logging.apache.org/log4cxx/}}.
\end{itemize}

Optional dependencies:
\begin{itemize}
	\item TaKIPI libraries \footnote{\url{http://plwordnet.pwr.wroc.pl/g419/tagger/}}, namely: Corpus and JOSKIPI
	libraries for processing of Polish texts in IPI PAN Corpus format \footnote{\url{http://korpus.pl/}}. Note, TaKIPI
	in current version (1.8) depends on Morfeusz\footnote{\url{http://nlp.ipipan.waw.pl/~wolinski/morfeusz/}}
	morphological analyzer.
	\item Simplified Wrapper and Interface Generator (SWIG)\footnote{\url{http://www.swig.org/}} for generation of
	Python wrappers.
	\item Minipar\footnote{\url{http://www.cs.ualberta.ca/~lindek/minipar.htm}} parser for creation of co-incidence
	matrices from English documents using dependency tripes.
	\item CLUTO\footnote{\url{http://glaros.dtc.umn.edu/gkhome/views/cluto/}} for using other clustering algorithms than
	provided in SuperMatrix.
	\item Gensim\footnote{\url{http://radimrehurek.com/gensim/}} for using LDA and SVD algorithms.
	\item Corpus2\footnote{\url{http://nlp.pwr.wroc.pl/redmine/projects/corpus2/wiki}}, WCCL\footnote{\url{http://nlp.pwr.wroc.pl/redmine/projects/joskipi/wiki}} and ANTLR\footnote{\url{http://antlr.org}} libraries for building matrices in Polish language.
	\item GNU Parallel\footnote{\url{http://www.gnu.org/software/parallel}} and Python argparse module\footnote{\url{http://pypi.python.org/pypi/argparse}}(while using Python older than 2.7) for \verb|matrix_creator.py| and some other useful python scripts.
	\item Open MPI\footnote{\url{http://www.open-mpi.org}} for programs executed in parallel.
\end{itemize}


\subsection{Linux - Installation of dependencies}

Firstly Python version 2.6 or 2.7 developers package should be installed which are supported by SuperMatrix and later Python setuptools can be installed. Developer version is necessary for SWIG.

\begin{verbatim}
$ sudo apt-get install python2.7-dev
$ sudo apt-get install python-setuptools
\end{verbatim}

Next SWIG must be installed to get Python wrappers in packages which will be installed later.

\begin{verbatim}
$ sudo apt-get install swig
\end{verbatim}

Third step is to install CRF++ and Python wrappers for it. Source code can be downloaded from:
http://crfpp.googlecode.com/svn/trunk/doc/index.html

Before beginning of installation be ensure that g++ is installed.

\begin{verbatim}
# to be sure that g++ is installed
$ sudo apt-get install g++
\end{verbatim}

\begin{verbatim}
$ ./configure 
$ make
$ su
$ sudo make install
$ sudo ldconfig
\end{verbatim}

Next wrappers for CRF++ can be installed.

\begin{verbatim}
$ cd python
$ ./setup.py build
$ sudo ./setup.py install
\end{verbatim}

After CRF++ Corpus2 library can be installed. It require many dependencies which are listed below:

\begin{itemize}
	\item CMake 2.8 (or later; cmake) as well as gcc with C++ support (g++ / gcc-c++)
	\item Boost 1.41 or later (tested with 1.41, 1.42 and 1.47), packages: program\_options, system, filesystem, regex (Ubuntu packages libboost-(...)-dev / Fedora package boost-devel; remember to check the version).
    	\item ICU library (tested with 4.2; Ubuntu package libicu-dev / Fedora package libicu-devel)
    	\item LibXML++ (libxml++2.6-dev / libxml++-devel)
    	\item bison and flex (bison, flex)
    	\item Loki (Ubuntu package libloki-dev / Fedora package loki-lib-devel)
	\item Log4cxx (liblog4cxx10-dev)
	\item Also git might be useful
\end{itemize}

Example of an installation process of dependencies is shown below.

\begin{verbatim}
$ sudo apt-get install cmake libboost1.48-all-dev libicu-dev libxml++2.6-dev 
bison flex libloki-dev liblog4cxx10-dev
\end{verbatim}

When all dependencies will be installed then Corpus2 can be installed also.

\begin{verbatim}
$ git clone http://nlp.pwr.wroc.pl/corpus2.git
$ mkdir corpus2/bin
$ cd corpus2/bin
$ cmake ..
# confirm the default values with ENTER or if Poliqarp will be used 
then firstly switch CORPUS2_BUILD_POLIQARP to ON
# analyse the output, if some required dependencies are missing, install the lacking packages, 
remove CMakeCache.txt file and re-run cmake
$ make
$ sudo make install
$ sudo ldconfig
# optionally make test
\end{verbatim}

Next step is to install Toki, SFST 1.2(Stuttgart Finite State Tools) and MACA respectively.

Toki:

\begin{verbatim}
$ git clone http://nlp.pwr.wroc.pl/toki.git
$ mkdir toki/bin
$ cd toki/bin
$ cmake ..
$ make # or make -j8
$ sudo make install
$ sudo ldconfig
$ cd ../../
\end{verbatim}

SFST 1.2:

\begin{verbatim}
$ git clone http://nlp.pwr.wroc.pl/maca.git
$ cd maca/third_party/SFST-1.2/SFST/src/
$ make 
$ sudo make install
$ sudo ldconfig
$ cd ../../../../..
\end{verbatim}

MACA:

\begin{verbatim}
$ mkdir maca/bin
$ cd maca/bin
$ cmake ..
$ make
$ sudo make install
$ sudo ldconfig
\end{verbatim}

The last part of this installation process before SuperMatrix can be installed is to install WCCL.

\begin{verbatim}
$ git clone http://nlp.pwr.wroc.pl/wccl.git
$ mkdir wccl/bin
$ cd wccl/bin
$ cmake ..
# confirm the default values with ENTER
# analyse the output, if some required dependencies are missing, install the lacking packages, 
remove CMakeCache.txt file and re-run cmake
$ make
$ sudo make install
$ sudo ldconfig
# optionally make test
\end{verbatim}

Now when all dependencies should be already installed SuperMatrix can be installed.

\subsection{Linux - SuperMatrix installation}

\begin{verbatim}
$ git clone http://nlp.pwr.wroc.pl/supermatrix.git
$ cd supermatrix
$ mkdir bin
$ cd bin
$ ccmake ..
\end{verbatim}

Configure build options to your liking, most notably change build type to RELEASE. Hit 'c' to commence the
configuration. After it is done, hit 'g' to generate makefiles and exit ccmake.  If ccmake program is not
available on your system, then use 

\begin{verbatim}
cmake -i ..
\end{verbatim}

Next step involves building and testing

\begin{verbatim}
$ make 
$ make test-all
\end{verbatim}

Look at the output, there should be a few lines containing the following message: \verb|*** No errors detected|.
Now, installing SuperMatrix is straightforward:
\begin{verbatim}
$ make install # with root access 
\end{verbatim}

Finally, update the runtime bindings of dynamic linker:

\begin{verbatim}
$ ldconfig # with root access
\end{verbatim}

Simple installation check can be done by issuing the following command:

\begin{verbatim}
$ wbst_tester --help
\end{verbatim}

The output should print options of one of the utilities included with SuperMatrix.

\begin{verbatim}
$ git clone http://nlp.pwr.wroc.pl/supermatrix.git
$ cd supermatrix
$ mkdir bin
$ cd bin
$ ccmake ..
\end{verbatim}

Configure build options to your liking, most notably change build type to RELEASE. Hit 'c' to commence the
configuration. After it is done, hit 'g' to generate makefiles and exit ccmake.  If ccmake program is not
available on your system, then use 

\begin{verbatim}
cmake -i ..
\end{verbatim}

Next step involves building and testing

\begin{verbatim}
$ make 
$ make test-all
\end{verbatim}

Look at the output, there should be a few lines containing the following message: \verb|*** No errors detected|.
Now, installing SuperMatrix is straightforward:


\begin{verbatim}
$ make install # with root access 
\end{verbatim}

Finally, update the runtime bindings of dynamic linker:

\begin{verbatim}
$ ldconfig # with root access
\end{verbatim}

Simple installation check can be done by issuing the following command:

\begin{verbatim}
$ wbst_tester --help
\end{verbatim}

The output should print options of one of the utilities included with SuperMatrix.

\section{Quickstart Guide}

In this section we will show how to use tools included in SuperMatrix. We
assume that you have SuperMatrix installed and ready to use (see Sec.\
\ref{sec:installation}). If you are interested in working with Python wrappers see Sec.\ \ref{sec:pythontutorial}.

\subsection{Building Matrices}

There are a few ways to build a matrix in SuperMatrix. We will focus on the simplest case: building a matrix
describing words occurring in fixed window context. 

To create co-occurrence matrix we need tagged corpus (or corpora), from which we can generate dictionary of lemmas,
and set of tuples contains two lemmas, relation beetwen them and number of occurrnces. 

The process of creating the matrix is composed of three stages:
\begin{enumerate}
	\item Creating dictionary by saving to file of all words in corpus. 
	\item Generating file(s) with tuples
	\item Build a co-occurrence matrix on the basis of 1. and 2. stage 
\end{enumerate}

This process can be realized separatly for each stage by using aplications in architect2 package or by python
script which handling all these steps.
 
This script called \verb|matrix_creator.py| is running only with configuration file. In this section we describe only
the most important and necessary parameters. All of the options are describe in \ref{ss:architectTools}. Configuration
file consists 4 block of parameters which are connected with applications: \verb|basedict| \verb|builder| 
and \verb|tuplesproc| 

First section with header \verb|[Common]| contains common parameters for all three aplications. 

\lstset{language=Python}
\begin{lstlisting}
[Common]
corpus=/home/user/corpora/exampleCorpus
reader=poliqarp
out_dir=/home/user/out
tagset=kipi
max_jobs=3
\end{lstlisting}

Parameter \verb|corpus| contains path to the corpus. To work with many corpora, we should split pathes by the semicolons. 
Script doesn't support the same parameter in many lines. Next parameter is name of the reader. \verb|out_dir| is a path
to output directory, where matrix, tuples and dictionary will be save. To set number of CPU cores to which program will 
be wroking we have to complete parameter \verb|max_jobs|. Maximum value shouldn't be bigger than number of corpora multiplied 
by number of operators in \verb|[Builder]| section.

Second section has header \verb|[Builder]| and contains parameter for \verb|builder| apllication from package \verb|architect2|.
This program is generating files with tuples. A detailed description can be found in \ref{sec:builderTool}

\begin{lstlisting}
[Builder]
builder_bin=../../../build/tools/architect2/builder/builder
operator=/home/user/operators/subst/adjp.ccl
interval=
append_pos=
\end{lstlisting}

Parameter \verb|builder_bin| is the path to binary file of builder program. If SuperMatrix is correctly installed, parameter should
be set as builder. \verb|operator| contains path to operator file. If we want use multiply operators, we should separate them just
like \verb|corpus| in previous section.

In third section with header \verb|[BaseDict]| are parameters for \verb|basedict| program. It is generating file with dictionary 
of lemmas. A detailed description can be found in \ref{sec:basedictTool}

\begin{lstlisting}
[BaseDict]
basedict_bin=../../../build/tools/architect2/basedict/basedict
posfilters=
pos=
disamb_only=
mintf=
\end{lstlisting}
\verb|basedict_bin| is the path to basedict program.

Fourth section has header \verb|[tuplesproc]| and contains parameters for \verb|tuplesproc| program. This application is creating
co-occurrence matrix. A detailed description can be found in \ref{sec:tuplesprocTool}

\begin{lstlisting}
[Tuplesproc]
tuplesproc_bin=../../build/tools/architect2/tuplesproc/tuplesproc
matrix_name=matrixName
matrix_description=
tokens=
dict=
row_file=
column_file=
relation_file=
relations=
row_min_tf=
col_min_tf=
\end{lstlisting}

Analogously to the previous case \verb|tuplesproc_bin| is path to binary of \verb|tuplesproc| program. \verb|matrix_name| is a name
for the co-occurrence matrix. If we'll set path to dictionary of lemmas in \verb|dict| parametr, script will use it instead generating
its own. 

After setting configuration file we launching script
\begin{lstlisting}
>>> python matrix_creator.py config_file.cfg	
\end{lstlisting}

As result we will get dictionary of lemmas in dict.txt file, tuples files in dictionary tuples (name format is: \verb|corpus_operator.tuples|)
and co-occurrency matrix in the folder with the same name as value of matrix-name parametr in configuration file. 

\subsection{Joining Matrices}

\subsubsection{Overview}
Summator\_v2 is a program used to joining matrices. The program is located in tools/summator\_v2.

\subsubsection{Parameters description}

\begin{tabular}{l l}
--matrix arg		& Matrix to join (specify two or more) \\
--out-dir arg		& Output directory for joined matrix \\
--out-name arg		& Name of joined matrix  \\
--corpus-info arg	& Corpus info (for all matrices) \\
--unit-count arg	& Number of lexical units in corpora \\
--append-TF arg		& Whether to sum TFs or append \\
\end{tabular}

\subsubsection{Usage}
To use summator\_v2 you need two or more matrices two join, output directory and name of output matrix. Also you need to specify information about corpus and number of lexical units in corpora which will be written in info.txt file of output matrix.
\begin{verbatim}
$ summator2 --matrix /path/to/matrix1 --matrix /path/to/matrix2 
--out-dir /home/user/output --out-name joined_matrix 
--unit-count 100000 --corpus-info 'Joined matrix'
\end{verbatim} 

\subsection{Matrices Weighting}
\subsubsection{Overview}\label{ss:weighter}
Weighter is a program used to computing weight matrix for a given similarity function. Program is located in tools/matrix\_weighter.
\subsubsection{Usage}
To use weighter you need input matrix, similiatity function and path to output file.

\begin{verbatim}
$ weighter /home/user/matrix "cmp(simfunction=cosine(),weight=tfidf())"
/home/user/weighted_matrix
\end{verbatim} 

\subsection{WBST testing}
\subsubsection{Overview}
Wbst\_tester is a program used to WBST testing. Program is located in tools/wbst.
\subsubsection{Parameters description}
\begin{tabular}{l l}
--wbst arg		& Files with (E)WBST test \\
--matrices arg		& Directories with matrices \\
--sim arg		& Similarity functions \\
--threads arg (=1)	& Number of threads \\
--outdir arg (=./results)	&  Output directory \\
--flex arg (=subst)	& Flex class of a test \\
--load-ccs arg (=0)	& Should load CCS part of matrices? \\
\end{tabular}
\subsubsection{Usage}

To use wbst\_tester you need files with WBST tests, matrices and similarity functions.
\begin{verbatim}
$ wbst_tester --wbst /home/user/wbst1.csv --wbst /home/user/wbst2.csv
--matrices /home/user/matrix --sim "pmi()" --sim "lin()"
\end{verbatim}

