% -*- Document-Type: LaTeX; Master-File: icdar2.tex -*- 
%make two column with no page numbering, default is 10 point
\documentstyle[twocolumn,epsfig]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% New commands
\def\BB{Blackboard}
\def\RC{Concept Network}
\def\RE{Example Network}
\def\bascet{\textsc{ BAsCET}}
\def\graphein{\textsc{Graphein}}

\begin{document}

%don't want date printed
\date{}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large\bf Bibliography References Validation Using Emergent Architecture}

\author{F. Parmentier and A. Belaïd  \\
~~\\
CRIN/CNRS -- INRIA Lorraine\\
Bâtiment LORIA -- Campus scientifique BP 239 \\
54506 Vand{\oe}uvre-lès-Nancy CEDEX FRANCE\\
E-mail: {\tt \{parmenti,abelaid\}@loria.fr}
}

\maketitle

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract} 
%IEEE allows italicized abstract up to 150 words long.  

{\em In this paper, we present an AI approach for the semantic
recognition of Bibliography references. The objective is to produce
for each reference (given by an {\sc ocr} flow), a structured data
containing the list of the different sub-fields recognized and
semantically validated. The validation is operated according to a
Bibliography reference database, by the exam of principal terms in
each reference field. The system uses an emergent architecture
containing a Concept Network built from the database. This net
represents the principal fields of the references and includes
statistics on the occurrence of their terms. Validation is achieved
dynamically by activation at each time of the more pertinent
concepts. These concepts verify the presence of their terms by the
execution of appropriate agents. This architecture is robust and
non-deterministic allowing to find a solution in spite of {\sc ocr}
errors.}

{\bf Keywords}: Bibliography References -- Emergent Architecture --
Concept Network -- Term Co-occurrence.
  
  %% Introduction
  \section{Introduction}
  
  
  For many applications, it is necessary to analyze the document
  content and to extract the structure relatively to its finest
  components. This concerns the content architecture of text physical
  blocks such as \emph{footnotes}, \emph{figure captions} and
  \emph{Bibliography references}. For these blocks, physical structure
  (limited to a short line sequence) is less informative than logical
  one which is able to inform the system about components structure
  and content. This information, which is fundamental for recognition,
   deals with typographic style, term linguistic affiliation,
  contextual information on successive sub-fields such as limits and
  location. In this case, the structure recognition becomes document
  understanding. Several document image understanding systems have
  been proposed for documents such as letter
  addresses~\cite{dengel90b}, forms~\cite{ybelaid95a} where the
  logical structures is more complete than layout structure.

  In this paper, we present a system for the recognition of
  Bibliography references. The logical structure is composed of a
  series of fields corresponding to {\it authors}, {\it title}, {\it
  conference name}, etc. Limits between these fields are not always
  easy to detect and there is not a rigorous syntax to describe the
  field contents. We chose to validate limits between fields and their
  content by looking for the presence and the co-occurrence of their
  principal terms according to statistics calculated from a reference
  database. The literature mentions several algorithms to validate
  terms linked together, such as decision trees, grammars or discrete
  and stochastic relaxation. Due to the fact that the validation
  problem is combinatory (NP complete), all these approaches are time
  consuming. We chose to use \textsc{BAsCET}, a new architecture,
  inspired from Hofstadter and Mitchell's work \cite{hofstadter92a},
  designed to build any type of system that needs interaction between
  several knowledge sources, declarative and procedural, and that has
  to show an intelligent behavior, versatile in its decisions, aiming
  to approach the human cognitive faculties.


\section{System Overview}
  
  The validation is done in three steps ({\em cf.
  figure~\ref{fig:principle}}).  The first step concerns the
  syntactical analysis of the {\sc ocr} flow in order to extract the
  reference fields.  This step, already operational
  (cf.~\cite{belaid94b}), is based on search of field initials and
  finals from a reference grammar.

  The second step deals with {\em term extraction} or filtering in
  each field. According to each field, terms correspond to names in
  {\sc author} field, keywords in {\sc title}, specific words in {\sc
  conference} field, etc.

  The last step is the \emph{validation} of the reference fields,
  using their term co-occurrences.  The aim is to validate the
  orthography of each term, verifying that these terms already
  appeared in the base. The more they appeared, the more they are
  validated. But their relationships in the base are also important:
  the more often two authors write together, the more probable their
  names are to be correct if they both appear in the same
  \textsc{authors} field.

  \begin{figure} [htb]
    \centerline{\epsfig{figure=overview.eps,width=1.0\columnwidth}}
    \caption{System Overview}
    \label{fig:principle}
  \end{figure}

  

  \section{Concept Network}
  
  As shown in figure~\ref{fig:concept_network}, the Concept Network is
  separated into two parts: the \emph{generic} part which corresponds
  to the syntactical aspect of the model and considered as a
  \emph{long term memory}, and the \emph{specific} part which contains
  the domain information and can be considered as a \emph{mean term
  memory}.
  
  \subsection{Generic part}
  
  The generic part of the Concept Network represents the system model
  of the domain (the references).  Its is a hierarchy of nodes
  corresponding to classes and sub-classes. The root node represents
  the reference concept, while the intermediate nodes represent
  different fields such as {\sc Authors}, {\sc Title} and {\sc
  Conference}. Leaves correspond to elementary parts of different
  fields, such as {\sc Name} and {\sc First-Name} for the field {\sc
  Author}. There are two kinds of links between nodes: {\em
  composed-of} and {\em co-exists with}. The later expresses the
  fact that nodes belong to the same conceptual level in the
  hierarchy. 
  
  \begin{figure} [htb]
    \centerline{\epsfig{figure=refsnet.eps,width=1.0\columnwidth}}
    \caption{Concept Network}
    \label{fig:concept_network}
  \end{figure}
  
  
  \subsection{Specific part}
  
  The specific part, obtained  by ``compilation'' of the reference
  database, allows to point up the most relevant terms in all the
  references. It corresponds to nodes given by instantiation of
  leaves of the {\sc generic} part, such as Author$_i$ for the sub-class
  {\it Author}. Links between generic part and specific part are of
  type: {\em is-a}, while links within specific part are of type: {\em
  co-occurs}. This link expresses the fact that the two terms (nodes)
  appeared in the same reference. 

\subsection{Emergence Principle}

The emergence principle is based on the activation of nodes. A node
emerges when it is activated. Each node has an activation value
depending on the influence of its neighbors, updated at each
cycle. The calculus of the influence is based on the neighbor
proximity and activation. The proximity between nodes depends on the
type of their link and is often expressed as a ratio between
occurrence values. Here are the formulae giving the proximities of
{\em generic nodes}:

\begin{itemize}  
\item {\em composed-of}: the proximity value is a constant given
by the designer,
\item {\em co-exists with}: (ex: A coexists with B) :

\[C1+ (100-C1)\frac{\mbox{NbA}}{\mbox{NbB}\times \mbox{NbT}} \]
    
where NbA (respectively NbB, NbT) is the number of A's (respectively
B's, T's) instances in the base, C1 is a constant set by the designer,
and T is a node composed of A and B.
\end{itemize}

The other types depend on the reference database.
      
\section{Construction of the Specific Part}
  
The system counts in the database, for each node of the generic part,
the number of its occurrences, the number of its co-occurrences 
with the other nodes, and deduces the proximities with nodes appearing
in the same reference. 

We give in the following the formulae for the calculus of links used
at this level

\begin{itemize}
\item {\it is-a} (ex: {\bf A is-a B}):  

\[ C2+ (100-C2)\times \frac{\mbox{NbA}}{\mbox{MaxOccB}} \]

where NbA is the number of A occurrences, MaxOccB the maximum of
 occurrences of all the instances of B, and C2 is a constant (given by
 the designer), this is the same for the
 second formula.

\item {\it has-instance} (ex: {\bf B has-instance A}), this link is
the inverse of {\it is-a}: 

\[ (100-C2)+C2\times \frac{\mbox{NbA}}{\mbox{MaxOccB}} \]

\item {\it co-occurs with} (ex: {\bf A co-occurs with B})

\[100 \times \frac{\mbox{NbCoOc}(A,B)}{\mbox{NbA}}\]

  where NbCoOc$(A,B)$ is the number of co-occurrences of A and B.
\end{itemize}
  
The proximities between the  node  \textsc{author} and the   authors
  represent the number of occurrences of the authors in the list.  The
  proximities  between the authors represent  the number of times they
  have been co-authors in the list.
   
Let (C,B), (C,B), (A,B), (C) and (B) be the author's list in five
references. Figure~\ref{fig:evolutif} gives the occurrence number of
each author (A: 1, B:4, C:3), the number of their co-occurrences
(AB:1, AC:0, BC:2), and the proximity values which calculus detail is
given by the grey areas.

 \begin{figure} [htb]
    \centerline{\epsfig{figure=co-occurrence.eps,width=\columnwidth}}
    \caption{Piece of the specific part of the Concept Network}
    \label{fig:evolutif}
  \end{figure}

  
\section{Architecture Functioning}
    
  The initialization of  the system is the  activation of  the Concept
  Network. This is done by creating an  object (thus, an instantiation
  of a node in the Concept Network) in  the Blackboard, activating the
  node of whom   it is an instantiation. Then,  the agents  of  the
  activated node(s) are posted in a queue (called Coderack in the
  {\sc Copycat} architecture).
  
  Next, N agents are extracted (probabilistically chosen, depending on
  {\em temperature} -- which measures how much problems are solved --
  and on agent urgency values) from the Coderack and executed. The
  number N is a parameter of the system (Mitchell assigned it to 15 in
  the \textsc{CopyCat} project).  After that, Concept Network is
  updated, that is to say its activation is propagated between the
  nodes. Then, activated nodes are allowed to launch agents.
  
  This re-iterates until a stopping agent is executed and actually
  stops the process.
  
  The solution is build  from the blackboard state,  and this state is
  optionally added to  the   references base, in   order to  be  later
  integrated in the particular part of the Concept Network.

  
  \subsection{Agents}
  
  There are currently two types  of agents: the first  one is the {\em
  validating agent},  which decides whether or  not there is a term in
  the Blackboard (instantiation of the node {\sc Author} (respectively
  {\sc Keyword}))  corresponding to the  author (respectively keyword)
  that launched the  agent. This decision is  taken after a comparison
  using the edition  distance.  When 75\% or more  of the term letters
  are the same (in the  same place), the term   is recognized and  its
  confidence score is saved.
  
  Another type of agents is the {\em stopping agent}. Each node of the
  particular  part in the   Concept Network have  such  an  agent. Its
  urgency value is lower  than the other agents,  so  that it has  low
  probabilities of execution  as long as other  agents  are present in
  the Coderack. Once  executed, it examines  the system idleness (when
  an agent changes something in  the Blackboard, the idleness is reset
  to  zero,   else the  idleness  increases   at every update  of  the
  network),  and when it is  greater than the  permitted idleness, it
  decides   probabilistically (depending on  the system's temperature)
  whether or not  it is time   to stop. It  then  shows the recognized
  reference (with the confidence scores).
  
  The beginning idleness is a parameter of the system. If an action is
  done in the Blackboard (descriptor  change, object creation, \dots),
  and the idleness is near of the  maximum permitted idleness (with a
  20\%  margin), this permitted idleness  is  increased of 20\%. This
  behavior allows the system to stop early, and it still is likely to
  execute a last-action agent.
  
  \subsection{An example}
  
  The Concept Network (cf. figure~\ref{fig:ex_cn0}) is obtained from a
  reference database similar to the one shown in
  figure~\ref{fig:evolutif}, added with some keywords. At the
  beginning, all the Concept Network is inactive.
  
  \begin{figure} [htb]
    \centerline{\epsfig{figure=ex_cn0.eps,width=\columnwidth}}
    \caption{Concept Network of the example}
    \label{fig:ex_cn0}
  \end{figure}
  
  After introducing the text of reference containing two authors, and
  a title with two keywords, the system is the state shown by the
  figure~\ref{fig:ex_cn}. All the nodes which were recognized are
  activated (100\%), and the others begin to emerge (in case of
  failure, all solutions have to be tested). The process took 4 cycles
  to produce its response: it found and recognized 2 authors, and 2
  keywords (this is an optimal case because all the terms were already
  in the base). 3 decomposition agents and 4 validating agents were
  executed, which took more time than the 18 stopping agents that only
  checked whether or not the system should stop. The response was
  quasi-immediate (the Concept Network was small, but tests with more
  nodes gave similar speed).

  \begin{figure} [htb]
    \centerline{\epsfig{figure=ex_cn.eps,width=\columnwidth}}
    \caption{Final state of the Concept Network}
    \label{fig:ex_cn}
  \end{figure}
    
  \section{Conclusion and Discussion}
  
  We have developed an architecture based on agent cooperation.  The
  principal information is represented by a Concept Network which is a
  semantic net evolving dynamically during the system execution.  The
  evolution leads the system to propose, at each time, the interesting
  concept to be analyzed and appropriate agents to execute on this
  concept.  To avoid determinism of classical models, we use a
  temperature measurement which controls the system decisions and by
  consequence the system convergence. This architecture has been used
  on two applications: traveler salesman problem and bibliographic
  reference validation. Although the system is in its beginning, it
  works quickly and solutions are satisfactory: they correspond to
  solutions given by human and speed is acceptable. For the first
  problem, since each town is given with distances from all the
  others, the solution is found in only one cycle. But for references,
  the system is tested only on the author concept. The activation
  values are correctly propagated allowing to tune the system
  parameters.  The architecture is completely implemented (in C++) on
  a Sparc Station.

\bibliographystyle{plain}

%%% DEBUT DE VOTRE TEXTE


%%% FIN DE VOTRE TEXTE
\bibliography{/users/ecriture/commun/biblio}


%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%
