\documentclass[10pt,a4paper]{article}
\usepackage{lrec2006}
\usepackage{dirtree}
\usepackage{url,moreverb,hhline,graphicx,lmodern}
\usepackage[british]{babel}
\usepackage[T1]{fontenc} % edh in BibTeX
\newcommand{\slug}{\hspace{1.0em}}
%%%%%
% Message-ID: <160220101402163735%gregorio@math.unipd.it>
\renewcommand{\thesection}{\arabic{section}}
\renewcommand{\thesubsection}{\thesection.\arabic{subsection}}
\renewcommand{\thesubsubsection}{\thesubsection.\arabic{subsubsection}}
\makeatletter
\renewcommand*{\@seccntformat}[1]{%
  \csname the#1\endcsname
  \ifcsname adddot@#1\endcsname.\fi\quad
}
\let\adddot@section=T
\let\adddot@subsection=T
\let\adddot@subsubsection=T
\makeatother
%%%%%  max. 8 pages
\title{Ontology-Based Categorization of Web Services with Machine Learning}
\name{Adam Funk, Kalina Bontcheva}
\address{Department of Computer Science\\
  University of Sheffield\\
  Regent Court, Sheffield, S1~4DP, UK\\
  a.funk@dcs.shef.ac.uk, k.bontcheva@dcs.shef.ac.uk\\}
%
\abstract{We present the problem of categorizing web services according to a
  shallow ontology for presentation on a specialist portal, using their WSDL and
  associated textual documents found by a crawler.  We treat this as a text
  classification problem and apply first information extraction (IE) techniques
  (voting using keywords weight according to their context), then machine
  learning (ML), and finally a combined approach in which ML has priority over
  weighted keywords, but the latter can still make up categorizations for
  services for which ML does not produce enough.  We evaluate the techniques
  (using data manually annotated through the portal, which we also use as the
  training data for ML) according to standard IE measures for flat
  categorization as well as the Balanced Distance Metric (more suitable for
  ontological classification) and compare them with related work in web service
  categorization.  The ML and combined categorization results are good and the
  system is designed to take users' contributions through the portal's Web~2.0
  features as additional training data.}
%%%%%
\begin{document}
\maketitleabstract
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}
%
The web is no longer just a set of documents; services now feature prominently,
and both research and industry devote considerable effort and interest to
service-oriented architecture (SOA), web services, and related technologies.  In
a web of services or a service-oriented-architecture, discovery is an essential
task for building and using applications.  Unfortunately the widely used service
description techniques only cover the syntactic level.  Previous research
projects showed that semantic descriptions (such as OWL-S, WSMO, and SAWSDL) can
enable precise service discovery, but they are not widely
deployed~\cite{DellaValle08}.


The main existing solution for service discovery is UDDI (Universal Description,
Discovery and
Integration\footnote{\url{http://www.oasis-open.org/committees/uddi-spec/doc/tcspecs.htm}}),
a standard for programmatically publishing and retrieving structured information
about web services.  Some companies operate public UDDI repositories, but its
success has not been widespread because of complicated registration, missing
monitoring facilities, and other difficulties.  A few portals have been designed
to act as web service repositories, but they all rely on manual registration and
review, so coverage is limited and information falls out of date easily.
Furthermore, the standard web search engines do not provide effective ways to
search for services or to allow filtering according to availability and service
parameters.


The Service-Finder project aims to address this problem for a wider audience by
offering a comprehensive framework for service discovery through a
portal\footnote{\url{http://demo.service-finder.eu/}}, so we must address the
problem of creating semantic descriptions of Web Services. The TAO
project\footnote{\url{http://www.tao-project.eu/}} dealt with semi-automatic
creation of semantic service descriptions, but focused on legacy applications
and relied on the existence of substantial software documentation.
Service-Finder offers automatic creation of service descriptions for a wide
range of publicly available services and enables service consumers (not just
providers) to collaboratively enrich the semantic descriptions according to Web
2.0 principles.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The research problem}
%%%%%
The information flow in Service-Finder is structured as follows.  The Service
Crawler (SC) carries out focused crawling for web services and archives WSDL
files and related HTML files, then passes batches of these data to the Automatic
Annotator (AA), which processes them using information extraction techniques to
produce semantic annotations for the Conceptual Indexer and Matcher (CIM).  The
CIM acts as a semantic repository and back end for the Service-Finder Portal
(SFP)---it answers the latter's queries and records users' annotations in the
repository along with the automatic annotations.  The Clustering Engine (CE)
also provides recommendations by clustering users and services based on the
users' behaviour and interests~\cite{SF-First,DellaValle08}.

This paper focuses on a specific problem in Service-Finder: automatically
categorizing web services so that portal users can find them effectively.
Although users can improve the category annotations, the aim is to provide
reasonably good ones to start with so users will find the portal useful and
contribute---so they do not have to face 23~000 uncategorized services with only
keyword searching.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Data}
\label{sec:data}
%%%%%
A batch of AA input from the SC consists of several files in the
Heritrix\footnote{\url{http://crawler.archive.org/}} Internet Archive format;
Table~\ref{tab:input-output} summarizes one of the last batches processed.  The
SC also provides an index which associates each document with one service
identifier.  (The services and providers are identified by URIs, and a service's
URI can be easily converted to the relevant provider's URI.)
%%
\input{figures/input-output}

The AA's task is to extract information (such as contact addresses), classify
documents and services, and semantically annotate the services, providers, and
interesting documents, using tools built on the GATE \cite{Cun02b} infrastructure.
This paper presents work on the service categorization task.


Table~\ref{tab:input-output} also shows the results of preprocessing the archive
files to produce datastores of GATE documents (relating to about 8~000 providers
and 23~000 services).  The preprocessor merges exact duplicate
documents\footnote{Each provider is associated with one or more services.  Each
  input document is associated by the SC with one service, but merged documents
  that refer to different services (of the same provider) are associated with
  all of them.  Each abstract relates to only one service.}, suppresses WSDL
documents that the XML parser rejects, and suppresses documents whose provider
URIs indicate that the services are not usable from the crawled WSDL files
because they contain invalid endpoints (they have been incorrectly generated or
the endpoints have been deliberately edited out of the publicly available
versions).


The AA uses the WSDL documents to generate instances of \emph{Endpoint},
\emph{Interface}, and \emph{Operation}, and to instantiate relations between
them and the \emph{Service} instances, but carries out very little textual
information extraction (IE) on them. The \emph{abstracts} are compiled by the SC
from various textual elements and attributes in the WSDL files (service name,
documentation, operation names, input and output parameters, etc.).  The SC
generates one abstract for each service URI, choosing the best WSDL file
associated with the service (typically the shortest WSDL URL containing the
provider name).  The AA carries out textual IE on the abstracts as well as the
HTML files.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The categorization task}
\label{sec:purpose}
%%%%%
The category ontology used in the project contains 59 subclasses of
\emph{Category} arranged in a shallow tree (with some multiple inheritance)
under seven main branches, as shown in Figure~\ref{fig:categories}.  Each
service can be annotated with more than one category, as shown in
Figure~{fig:categories}.  (See \cite{DellaValle08,SF-D4.2} for further details
of the ontology design.)
%
\input{figures/categories}


Since we originally had no manually annotated data to use for training but
needed to generate category annotations quickly for the first release of the
portal, we devised a weighted voting system based on keywords; this was
relatively easy to integrate with the AA pipeline which was already being
developed to apply gazetteers and rules to the documents for other purposes.
\S\ref{sec:keywords} explains this approach in more detail and presents the
evaluation results.


After the first release of the portal, members of the project manually
annotated 224 services through the portal to produce 387 category annotations
(using 45 of the service categories), which we exported to use for evaluation of
the keyword-based system and as training data for machine learning (ML).  At
that point, we did not have enough annotations from outside users to make a
significant contribution, but in the future, their annotations will also be
exported and used in the same way.  \S\ref{sec:ml} explains and evaluates the ML
techniques used.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Methodology}
\label{sec:methodology}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Keywords, rules, and multipliers}
\label{sec:keywords}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For our first approach to categorization, we devised an \emph{ad hoc} gazetteer
of keywords and phrases associated with service categories (the category names,
parts of the multiword names, morphological variations (such as plurals),
synonyms, and related words obtained by examining the documents);
Table~\ref{tab:gazetteer} shows examples for three of the categories.  This
gazetteer processor was configured to be case-insensitive but to match whole
words only (for example, \emph{Address} would match part of \emph{address list}
but nothing in \emph{headdress}).
%%
\input{figures/gazetteer}


Because some place where keywords can appear are more significant than others,
JAPE rules\footnote{JAPE processors in GATE compile rules that specify regular
  expressions of annotations and create additional annotations, manipulate
  features, and execute Java code when matches are detected. \cite{Cun00e}}
later in the pipeline create special annotations over the gazetteer matches,
% each of which has a multiplier $m$ which starts at 1 and is increased up to 5 if
% the keyword occurs in an HTML \url{<title>} or heading element, a \url{<p>}
% element with a significant number of interesting keywords (from this and other
% gazetteers), or an \emph{interesting}\footnote{The IE pipeline adjusts each
%   document's \emph{interesting} feature between 0 and 3 according to the
%   information it finds.} document.
%
% back to the longer version
each of which has a multiplier $m$ which starts at 1 and is increased according
to the following rules:
%%
\begin{itemize}
\item $+3$ if the match is in an HTML \url{<title>}, \url{<h1>}, \url{<h2>},
  \url{<h3>}, or \url{<h4>} element;
\item $+2$ if the match is in a \url{<p>} element that contains a significant
  number of interesting keywords (from various gazetteers in the application);
\item $+2$ if the document has an \emph{interesting} value\footnote{The IE
    pipeline adjusts each document's \emph{interesting} feature, initially 0,
    between 0 and 3 according to the information it finds.} $2.0{\leq}i$;
\item $+1$ if the document has an \emph{interesting} value $1.0{\leq}i{<}2.0$.
\end{itemize}


Each category keyword match in a document is later treated as $m$ (the
multiplier) votes for the relevant category for each service associated with the
document.  These votes are compiled for every service, which is labelled with
the two highest-scoring categories.  (This arbitrary limit was agreed within the
project.)


We used the manually annotated data described in \S\ref{sec:purpose} to evaluate
the AA's categorization of those services.  Table~\ref{tab:keyword-eval} shows
the traditional IE measures\footnote{Precision, recall, and $F_1$
  \cite{Manning:evaluation}.} for the three major datasets (which we call
Crawls~1, 2, and~3) that have been processed through Service-Finder, as well as
the Balanced Distance Metric (BDM) \cite{Maynard06a} for the latest one.  The
traditional measures count each categorization as wrong if it is not an exact
match, even if the key (manual) and response (automatic) categories are close in
the ontology tree.  BDM scoring, however, counts 1 for an exact match but gives
partial credit for getting a superclass or subclass of the key, as well as for
hitting another node on the same branch of the class tree.  It counts a response
as 0 only if its lowest superclass in common with the key is the top class.
These \emph{augmented} precision, recall, and $F_1$ measures are more suitable
for ontology-based classification~\cite{Maynard07c}.
%%
\input{figures/keyword-evaluation}


The BDM scores for Crawl~3 are noticeably higher than the traditional ones; this
indicates that the system is categorizing quite a few services with ``nearly
correct'' classes from the category ontology.  These results are still not very
good, however.  After Crawl~2, we improved recall by adding more keywords to the
gazetteers, but this made precision deteriorate significantly.  We had suspected
that the documents in other languages than English might pose a problem, but we
added an automatic language identification tool based on character $n$-grams
\cite{smile} to count the number of abstracts and HTML documents by language, as
shown in Table~\ref{tab:crawl3-lang} and concluded that adding translations to
the gazetteers would not be fruitful.  Instead, we pursued experiments in
service categorization based on machine learning.
%%
% Note to Kalina: 
% we didn't actually try adding translations to the gazetteers.
%%
\input{figures/crawl3-lang}
%
%%%%%
\subsection{Machine learning}
\label{sec:ml}
%%%%%
We treat this as a text classification problem and use the Support Vector
Machine (SVM) technique, which is well documented for this
purpose. \cite{Joachim98,Yaoyong04,Yaoyong07b} SVM text classification is
carried out using $n$-grams of features of sequential units of text (such as
unmodified tokens, part-of-speech tags, orthographic features, or lemmata), but
previous research indicates that increasing $n$ from 1 to 2 slows down
performance and rarely improves the results, and increasing $n$ beyond 2
typically deteriorates the results. \cite{Yaoyong04,Pang02,Funk08}


One disadvantage of SVM ML is that it can learn and apply only one class to each
instance (document, in this case), so we had to simplify the problem for
services with more than one manually annotated category by using the lowest
(most specific) class in the category ontology (or making an arbitrary choice
between two equal categories).  As we shall see later, however, it is possible
to generate more than one category for a service with multiple documents.


We carried out several document classification experiments on the manually
annotated services using standard parameters for GATE's SVM tool, with unigrams
of tokens\footnote{We used the standard ANNIE tokenizer for natural language on
  the HTML documents and a \emph{source code tokenizer} on the abstracts.  The
  second one splits camel-cased strings (e.g., \texttt{getUnsplicedSequence}
  $\to$ \texttt{get Unspliced Sequence}) as well as tokens separated by
  whitespace and inter-word punctuation.}  as the instance attributes (i.e.,
treating each document as a bag of words) and one service category per document
as the target class, one-against-others classification, and a linear kernel.
(See \cite{Yaoyong04,Yaoyong07b} for the technical details of the parameters.)
All the ML experiments described here are evaluated with 4-fold
cross-validation, which makes better use of the available corpus. The first
experiment used 0.1 as the classification probability threshold, first over 224
abstracts (one per service) and then over 1019 documents (including the
abstracts).  The first part of Table~\ref{tab:ml-initial} shows the traditional
and BDM measures for document classification.
%%
\input{figures/ml-initial-evaluation}


We noted that the performance was much better for both abstracts and HTML
documents, and decided to carry out further experiments using this combination.
(Working with HTMLs only is not practical since quite a few services have no
HTMLs or only a few small ones, whereas every service has an abstract with some
content.)  Table~\ref{tab:ml-initial} shows the results for document
classification with various values for the classification threshold (the minimum
probability required for the SVM to assign a classification).  One normally
expects increasing the threshold to increase precision and decrease recall, but
the effect above 0.3 was quite severe here, so we decided to continue with just
the two low threshold values.  (We consider recall important because it is
beneficial to try to provide at least one approximate category for every service
on the portal; otherwise users are less likely to find the service at all and
then improve the categorization.)


The evaluation results presented so far in this section are scored per document,
with one key and one response category for each document, the key being the
single category selected from the manual annotations (as explained above).  But
the ML tool can assign different categories to documents related to the same
service, so we now consider letting each service's documents vote (with equal
weighting) to assign one or two categories to it.\footnote{If an HTML document
  can be associated with more than one service, its categorization votes for
  each relevant service.}  Table~\ref{tab:ml-voted} presents the traditional and
BDM measures for service categories derived from this process, for thresholds of
0.1 and 0.3 and for one or two categories per service.
%%
\input{figures/ml-voted}


It is surprising to see the precision and $F_1$ drop when each service has two
categories, but we can explain this in two ways.  First, many of the services
had only one manual annotation, so the second automatic one counts as a spurious
classification, even if it is closely related: for example, several services
were automatically labelled with \emph{Genetics} and its direct superclass
\emph{Science}, although the manual annotators only marked them as
\emph{Genetics}---these services get a 50\% score.  Since the ultimate purpose
of this work is to help users find services on the portal, however, we do not
consider this a significant fault.  Second, some services which had very few
documents received only one automatic category even when two categories were
allowed (because all the documents were labelled with the same category);
several such services automatically received one correct category but lacked the
second one---these too get a 50\% score.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Integrated approach}
\label{sec:integrated}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We then integrated the machine learning and keyword-based categorization
components in the AA pipeline in such a way that ML categorizations always
overrule keyword-based ones, but the latter can still be used if necessary to
make up to one or two categories per service.  (The ML categorization is turned
into a votable annotation on each document with a multiplier $m=100$, sufficient
to outvote keywords' annotations.)  This produced the results shown in
Table~\ref{tab:ml-combined}.  The measures are slightly lower but this approach
gives wider coverage of the services and categories (only 45 of the 59
categories were represented in the manually annotated data used for training the
ML component).
%%
\input{figures/combined}
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related work}
\label{sec:related}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As a result of the proliferation of web services and growing interest in web
service discovery, browsing, composition, and related matters in recent years,
several approaches have been investigated in service classification.


Belhajjame \&~al.~\cite{1346239} presented an algorithm to automatically annotate
web services with information to support service discovery and composability (in
particular, to allow data-driven composition of workflows).  This work achieved
good results for a very detailed type of annotation (concentrating on the
service and operation details) over a limited domain (bioinformatics), but does
not really apply to our broad coverage.


The \emph{Woogle} web-service search engine included a clustering system
\cite{Dong04} based on parameter names into meaningful groups to allow
similarity search.  This work also achieved good results, although it would not
be applicable to the Service-Finder task, which uses \emph{a priori} categories.
Woogle's approach was also dependent on UDDI repositories, which (as explained
in \S\ref{sec:intro}) we cannot rely on.
 

The ASSAM (Automated Semantic Service Annotation with Machine Learning)
\cite{ASSAM} tool loads WSDL files along with previously created ontologies and
provides a GUI for the user to annotate the services, and learns from previous
annotations in order to show suggestions and make manual annotation faster and
easier.  This system uses the authors' work on web service annotation with
machine learning \cite{Hess2003las,Hess2004}, which is related to our approach
presented here.  That work used Na\"ive Bayes and SVM classification on
combinations of bags of words from UDDI descriptions, WSDL files, and services'
input and output messages to classify two sets of services according to
ontologies with 11 and 26 categories, respectively.  The authors obtained
accuracy up to around 75\%, and noted that it is beneficial to offer users a
choice from a small number of predicted categories (this is similar to our point
that ``near miss'' categories are still useful for our portal users); their best
result for this purpose was to get the correct category in the top three
predictions 82\% of the time.  It is also worth noting that they obtained better
results by training and applying separate classifiers for the different types of
input data.


Although our results in Tables~\ref{tab:ml-voted} and~\ref{tab:ml-combined} are
not as high as ASSAM's best \cite{Hess2004} our task is more difficult: our
service ontology has twice as many classes and a service can belong to any
number of them, although ML techniques only produce one label per instance.  We
currently deal with the second problem by treating each document rather than
each service as an instance, and then collating the results and putting an
arbitrary limit on the number of categories per service.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
\label{sec:conclusion}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We consider the results in Table~\ref{tab:ml-voted} and~\ref{tab:ml-combined} to
be very good for our purposes.


A useful result of these experiments for Service-Finder and in general has been
to show that it may not be worthwhile to pursue incremental improvements in the
first classification approach (using keywords and rules), since it was
relatively easy to get significantly better results for this task with machine
learning.  Furthermore, training from manual annotations---unlike the first
approach---can also take advantage of the portal's collaborative (Web~2.0)
tools.


For future work in this type of classification task, we would be interested in
testing several improvements.  For the machine learning itself, experimenting
with using separate classifiers for abstracts and HTML documents would be
worthwhile, since using separate classifiers for different types of input texts
significantly improved ASSAM's results~\cite{Hess2003las,Hess2004}.)  It would
also be useful to develop an ontologically aware voting system to avoid
assigning near-duplicate categories: for example, if the top three voting
results for a service are \emph{Finance}, \emph{Currency}, and \emph{Logistics},
eliminate \emph{Finance} (a direct superclass of \emph{Currency}) and return
only the other two, which are on separate branches.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgements}
This research is partially supported by the European Union's Seventh Framework
Program project Service-Finder (FP7-215876).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{lrec2006}
%\bibliography{../../big,extra}
\bibliography{../../big}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
