\documentclass{scrartcl}
\usepackage{hhline,lmodern,url,moreverb}
\usepackage[square,numbers]{natbib}
\usepackage[british]{babel}
\usepackage[T1]{fontenc} % edh in BibTeX
%\usepackage{graphicx}
\newcommand{\sluga}{\rule{1.5em}{0em}}
\newcommand{\slugb}{\rule{1.0em}{0em}}
\newcommand{\slugc}{\rule{1.0em}{0em}}
\urldef\mails\url|a.funk,k.bontcheva@dcs.shef.ac.uk|
\selectlanguage{british}
%
\title{Ontology-Based Categorization of Web Services with Machine Learning}
\author{Adam Funk and Kalina Bontcheva\\
  University of Sheffield, Department of Computer Science\\
  Regent Court, 211 Portobello, Sheffield, S1~4DP, UK\\
  \mails}
%
\begin{document}
\maketitle
%
% \begin{abstract}
%   We discuss the problem of categorizing web services according to a shallow
%   ontology for presentation on a specialist portal.  We treat it as a text
%   classification problem and apply first information extraction techniques
%   (using keywords and rules), then machine learning.  The techniques are
%   evaluated according to standard measures for flat categorization as well as
%   the Balanced Distance Metric for ontological classification and compared with
%   related work in web service categorization.  The results for machine learning
%   are very good and will let us take advantage of the portal's Web~2.0 features
%   to improve it.
% \end{abstract}
%
\section{Introduction}
\label{sec:intro}
%
The Service-Finder project aims to address the problem of web service discovery
for a wide audience through a
portal\footnote{\url{http://demo.service-finder.eu/}} which presents automatic
semantic descriptions of a wide range of publicly available Web Services and
also enables service consumers (not just providers) to enrich them according to
Web 2.0 principles.  In this project, the Service Crawler 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 analyses
them to produce semantic annotations to the semantic repository and back end for
the web portal. \cite{DellaValle08}

This paper focuses on a specific AA problem: automatically categorizing web
services from the crawled documents so that portal users can find them
effectively.  Although users can improve the categorizations, we must provide
some good ones so that users will find the portal useful and contribute (instead
of facing about 23~000 uncategorized services with only keyword searching).

The project ontology contains 59 subclasses of \emph{Category} for web services,
such as \emph{Genetics}, \emph{SMS}, and \emph{Media Management}, arranged in a
shallow tree (down to three levels below the top class) in seven main branches
(such as \emph{Business} and \emph{Science}).  Each service can be annotated
with more than one category.  (See \cite{DellaValle08} for further details.)


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 pipeline that was already being developed
using GATE \citep{Cun02b} for other IE purposes.

After the first release of the portal, members of the project manually annotated
224 services through the portal to produce 387 category annotations, which we
used to evaluate 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 used the same way.
%%%%%
\section{Keywords and weighted voting}
\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), and weighted
the values of the keywords using JAPE rules \cite{Cun00e} to associate each
match with a multiplier $m$ which starts at 1 and varies up to 5 if it occurs in
a significant place such an HTML \url{<title>} or heading element.  Each match
is later treated as $m$ votes for the relevant category for the document's
services.  These votes are compiled for every service, which is then labelled
with the two highest-scoring categories.


We used the manually annotated data to evaluate this component using the
traditional IE measures.  The first two versions of the tool scored about
$P=36\%$, $R=15\%$; extending the gazetteers produced $P=20\%$ and increased
$R=32\%$.  We also evaluated the third version according to the Balanced
Distance Metric (BDM), which 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; these \emph{augmented} measures are better for ontological
classification~\cite{Maynard07c}.  We obtained $AP=38\%$ and $AR=40\%$, which
show that the system makes a significant number of ``near misses'', but we were
not satisfied with these results.  We ruled out language bias (99\% of the
abstracts and 87\% of the HTMLs were in English) and chose a different approach.
%
%%%%%
\section{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.  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{Joachim98s,Yaoyong07b,Funk08}


SVM ML can learn and apply only one class to each instance (here, each document)
so we had to simplify the training data by using the most specific class in the
category ontology for each document, although we then devised a way to generate
more than one category for a service.


We carried out several document classification experiments on the manually
annotated services using standard parameters for GATE's SVM tool, 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{Yaoyong07b} for the technical details of the parameters.  All the ML
experiments described here are evaluated with 4-fold cross-validation.)  The
first experiment used 0.1 as the classification probability threshold, first
over 229 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{input/ml-initial-evaluation}


The performance was much better for both abstracts and HTML documents so we
experimented further with this combination.  (Some services have no HTMLs or
only a few small ones, but every one has an abstract with some content.)
Table~\ref{tab:ml-initial} shows the results for document classification with
various classification threshold values.  One normally expects increasing the
threshold to increase $P$ and decrease $R$, but the effect above 0.3 was quite
severe, so we continued with only the low threshold values.  (We consider $R$
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.)


Those evaluations are scored with one key and one response category for each
document, the key being the single manual category explained above.  But the ML
tool can assign different categories to documents related to the same service,
so we let each service's documents vote to assign one or two categories to it,
and scored services, to obtain the results in Table~\ref{tab:ml-voted}.
%%
\input{input/ml-voted}


We have two explanations for the drop in $P$ and $F_1$ when each service has two
categories.  First, if a service has only one manual annotation but gets the
correct automatic label as well as its superclass, the second label is scored as
spurious and the service gets a 50\% score.  For this work's goal (helping users
find services on the portal) we do not consider this a problem.  Second, some
services with few documents received only one automatic category even when two
categories were allowed; these automatically received one correct category but
lacked the second one and so get a 50\% score.
%
%%%%%
\section{Related work and conclusions}
\label{sec:related}
%%%%%
We have examined other published research about semantic annotation of web
services and found one set of papers for a comparable task: the research for the
ASSAM (Automated Semantic Service Annotation with Machine Learning)
\cite{ASSAM,Hess04} tool, which uses machine learning (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, with accuracy
up to around 75\%.


Although our results so far are not as high as ASSAM's best, our task is more
difficult: our service ontology has twice as many classes and a service can
belong to any number of them.  We therefore consider our results so far to be
very good for our purpose.  Another useful result of these experiments for
Service-Finder has been to show that it is not worth pursuing incremental
improvements using keywords, since it was relatively easy to get significantly
better results with ML, which will (unlike the first approach) make use of the
portal's collaborative tools in the future.


In our continuing work, we are experimenting with using separate classifiers for
abstracts and HTML documents.  (Using separate classifiers for different types
of input improved the results for \cite{Hess04}.)  We are also developing an
ontologically aware voting system to avoid assigning near-duplicate categories
such as a class and its superclass.
%
%%%%%
\section*{Acknowledgements}
This research is partially supported by the European Union's Seventh Framework
Program project Service-Finder (FP7-215876).
%%%%%
\bibliographystyle{plainnat}
\bibliography{../../big,extra}
\end{document}
