Using a kernel–based approach to visualize integrated Chronic

Ahmad Al–Oqaily Paul J. Kennedy
Faculty of IT,
University of Technology, Sydney,
PO Box 123, Broadway, NSW 2007,
AUSTRALIA,
Email: aaoqaily@it.uts.edu.au

Abstract
We describe the use of a kernel–based approach using the Laplacian matrix to visualize an integrated Chronic Fatigue Syndrome dataset comprising symptom and fatigue questionnaire and patient classification data, complete blood evaluation data and patient gene expression profiles. We present visualizations of the individual and integrated datasets with the linear and Gaussian kernel functions. An efficient approach inspired by computational linguistics for constructing a linear kernel matrix for the gene expression data is described. Visualizations of the questionnaire data show a cluster of non–fatigued individuals distinct from those suffering from Chronic Fatigue Syndrome that supports the fact that diagnosis
is generally made using this kind of data. Clusters
unrelated to patient classes were found in the
gene expression data. Structure from the gene expression
dataset dominated visualizations of integrated
datasets that included gene expression data.
Keywords: kernel–based visualization, Laplacian matrix,
data integration, biomedical datasets.
1 Introduction
Chronic Fatigue Syndrome (CFS) (Afari & Buchwald
2003) is an illness with a primary symptom of debilitating
fatigue over a six month period. Currently
diagnosis of CFS is generally made by clinical
assessment of symptoms using a number of questionnaires
or surveys measuring functional impairment,
quantifiable measurements of fatigue and occurrence,
duration and severity of the symptoms
(Reeves et al. 2005). One goal of current research is
to derive a definition of the syndrome, which goes beyond
a clinical assessment of symptoms to an empirical
diagnosis founded on measurements such a gene
expression profiles. The motivation for this kind of research
is to gain a clearer understanding of the illness
and to find empirical guidelines for its diagnosis.
The question we examine in this paper is whether
data visualization methods, specifically a method
based on the eigenvectors of the Laplacian matrix
(Shawe-Taylor & Cristianini 2004), can be used to
discover patterns in biomedical datasets associated
with CFS patients. Also, because there are several
datasets from different sources, we are interested in
creating integrated datasets and visualizing the combined
data.
Copyright !c 2006, Australian Computer Society, Inc. This paper
appeared at Australasian Data Mining Conference (AusDM
2006), Sydney, December 2006. Conferences in Research and
Practice in Information Technology (CRPIT), Vol. 61. Peter
Christen, Paul Kennedy, Jiuyong Li, Simeon Simoff and Graham
Williams, Ed. Reproduction for academic, not-for profit
purposes permitted provided this text is included.
In the biomedical domain it is commonplace for
data to be generated by high–throughput technology.
One example is microarray technology (Baldi
& Hatfield 2002) which generates gene expression
profiles that simultaneously measure the level of expression
of thousands of genes in biological samples.
In general, biomedical datasets derived from high–
throughput technology are described by a small number
of samples (patients) and a large number of features
or attributes (i.e. genes) per sample. This results
in what is often referred to the ‘curse of dimensionality’
which makes building classifiers troublesome.
For analysis of this type of data, algorithms
are often applied to select features from the data to reduce
its dimensionality. As a first step towards working
to building classifiers for this kind of data, we
initially just visualize it and look for patterns in the
dataset.
In our case the data is represented by different
datasets and kinds of measurements including questionnaires,
complete blood evaluations and gene expression
data so we also create integrated datasets by
combining the individual datasets.
We apply a kernel based method to visualize
the individual and combined datasets. The method
(Shawe-Taylor & Cristianini 2004) we use is similar to
kernel PCA (kPCA). Kernel PCA is kernel–based extension
of the well known Principal Component Analysis
(PCA) algorithm (Haykin 1999) and is used to
reduce the dimensionality of datasets in a principled
way. PCA forms a new dataset where each attribute
is a linear combination of attributes from the original
dataset. When the dataset is reduced to two or three
dimensions it can be graphed and this allows PCA
and kPCA to be used to visualize the data. Kernel
PCA differs from PCA in that the data is transformed
using a kernel function before the new attributes are
derived. The benefit of doing this is that the attributes
are not limited to being linear combinations
of the original attributes and can therefore “see” nonlinear
relationships in the original data. Also, using
a kernel function allows visualization of non–vectorial
data. We use a method based on kPCA but it differs
in that whilst kPCA uses eigenvectors of the kernel
matrix, the method we employ uses eigenvectors of
a slightly different matrix: the Laplacian matrix. A
similar approach to clustering of text with Laplacian
matrices in done in (Li, Ng & Lim 2004). That approach,
however, did not apply kernel functions to the
data.
In section 2 we describe the datasets used for this
study and the preprocessing steps applied to the data.
Next, in section 3 we describe in detail the data mining
and visualization approach used to identify potential
patterns in the CFS datasets. In section 4 we
present and results of applying the kernel based visualization
method to the datasets. In section 5 we
discuss these results and describe future directions for
Proc. Fifth Australasian Data Mining Conference (AusDM2006)
53
the research. Finally, in section 6 we summarize the
paper.
2 Data
In this section we describe in detail the datasets used
and the preprocessing steps applied.
We used publicly available data generated as the
2006 Critical Assessment of Microarray Data Analysis
(CAMDA 2006) competition datasets (CDC
Chronic Fatigue Syndrome Research Group 2005).
The data consists of separate datasets for patients
linked by a patient identifier (“ABTID”). There were
datasets with (i) survey results from fatigue and
symptom questionnaires; (ii) complete blood evaluations;
(iii) gene expression profiles; (iv) single nucleotide
polymorphism (SNP) data; and (v) proteomics
data.
The sources of data used in this study are significant
because they cover the full biological spectrum
from genotype through to phenotype. That is,
ranging from data concerning genes through to data
about their expression in the body in the form of proteins.
The researchers who generated the data for the
CAMDA competition hypothesize that the gene expression
profile data will allow identification of “prognostic
indicators” or biomarkers for diagnosis of CFS
(National Center for Infectious Diseases 2005). As
mentioned above, CFS is currently diagnosed using
symptom questionnaires, so identification of biomarkers
is potentially very significant. The analysis in this
paper explores this hypothesis.
The SNP and proteomics datasets were not analyzed
in this study. Analysis of the SNP and proteomics
data is straightforward with our methods but
will be analyzed in future studies. The SNP and proteomics
data will not be mentioned further in this
paper.
Data was integrated between the three datasets
used in the study simply by linking of records using
the patient identifier i.e. ABTID. Not all patients
have data in each of these datasets. In cases where
data was not available across the integrated dataset
(e.g. when linking the gene expression and blood work
datasets) we omitted the patients affected. This was
acceptable in our situation because, as individuals in
the gene expression data are a subset of patients in
the clinical datasets, there was considerable overlap
between the datasets and not many patients were lost.
Patients were classified into a number of categories
which we grouped into three different classes:
(i) those classified by physicians as suffering from
Chronic Fatigue Syndrome (CFS); (ii) those classified
as suffering from symptoms associated with CFS
but with insufficient severity to be classified as CFS
(IFS); and (iii) non fatigued individuals (NF).
In the following subsections we describe each
dataset in more detail.
2.0.1 Clinical Datasets: Illness Classification
and Complete Blood Work
The clinical data comprised two datasets: (i) an Illness
Classification and Symptoms dataset consisting
of information about patient symptoms and fatigue
and (ii) evaluation of blood samples taken from
patients. Each individual indicated with a patient
identifier (“ABTID”) has a record in both of these
datasets. There were 139 CFS/ISF patients and 73
NF individuals.
The “Illness Classification SF36 MFI and Symptoms”
(illness) dataset is generated based on survey
results for the above mentioned patients (CDC
Chronic Fatigue Syndrome Research Group 2005).
The dataset includes (i) attributes that describe the
general information of the patient like sex, date of
birth, race, and ethnicity; (ii) the Medical Outcomes
Survey Short Form–36 (SF–36) (Ware & Sherbourne
1992), as a measurement criteria for functional impairment,
such as physical function, role emotional,
and mental health; (iii) Multidimensional Fatigue Inventory
(MFI) (Smets, Garssen, Bonke & DeHaes
1995), to obtain reproducible quantifiable measures
of fatigue including “General Fatigue”, “Physical Fatigue”,
“Active Reduction” and “Mental Fatigue”;
and (iv) the CDC Symptom Inventory (Wagner,
Nisenbaum, Heim, Jones, Unger & Reeves 2005) to
document the occurrence, duration and severity of the
symptom complex including attributes such as “Sore
Throat”, “Tender Nodes”, “Muscle Pain, and Depression”.
The “Complete Blood Evaluation” dataset
(blood) contained measurements of components of individual’s
blood as well as flags for when these measures
were out of normal range.
2.0.2 Gene Expression Datasets
Microarray technology allows the high throughput
analysis of global gene expression within a biological
specimen. Gene expression measurements are
made simultaneously for many thousands of genes.
The gene expression profile of diseased cells may reflect
the unique genetic alterations present and has
been shown to be predictive of clinical and biological
characteristics of illness for many diseases (Baldi
& Hatfield 2002). A major issue in these data is
the unreliable variance estimation, complicated by
the intensity–dependent technology–specific variance
(Weng, Dai, Zhan, He, Stepaniants & Bassett 2006).
Below we describe our approach to normalizing this
data. The gene expression profiles used in this study
measured the level of expression of genes in blood
samples from patients.
Data collected was for a subset of individuals: 118
CFS/ISF patients and 53 NF individuals. Generally
there is one gene expression profile for each of these
patients. A few individuals had more than one sample.
The gene expression profile for a sample contains
data for around ten thousand genes and data for each
gene comprised around 15 attributes.
2.0.3 Preprocessing of the Clinical datasets
Most of the attributes in the questionnaire and blood
evaluation datasets were used without much preprocessing.
Some attributes of the “illness” dataset, the clinical
dataset containing the patient’s answers to the
illness questionnaires, are omitted because they are
(i) skewed with almost all individuals having the same
attribute value, (ii) not deemed useful for the data
mining effort, or (iii) are calculated by the original researchers
and would bias our efforts. The attributes
concerned are “DOB”, “intake classific”, “cluster”,
“onset”, “yrs ill”, “race” and “ethnic”. The dependent
variable “Empiric” is used as the patient class
and patient subtypes are combined to make three
classes CFS, ISF and NF.
In the blood evaluation dataset, we add a copy of
the “Empiric” attribute so that the dataset has the
patient class.
All attributes of the clinical datasets apart from
the patient class “Empiric” were converted to numeric
values as the kernel visualisation method employed requires
strictly numeric data. Binary attributes were
converted to -1 and +1 for “false” and “true” respectively.
Similarly, in the questionnaire dataset, categorical
data values such as “mild”, “moderate” and
“severe” were coded to 1, 2 and 3 respectively.
CRPIT Volume 61
54
Missing values were universally converted to 0.
This is consistent with the coding scheme used for
binary and categorical attributes. Coding of missing
values to 0 is appropriate for kernel based schemes
because the value 0 does not adversely effect the dot
products used to build kernels. Missing values were
very infrequent in the dataset and we believe that this
simple approach to dealing with them is effective.
Data items in both clinical datasets were centred
by subtracting the mean and attributes were normalized.
2.0.4 Preprocessing of the Gene Expression
data
Data for each gene comprised a spot label (the name
of the gene) and several measurements describing the
level of expression of the gene as well as quality control
indications of the expression measurement. We
extracted the “Spot labels”, “ARM Dens — Levels”,
“MAD — Levels” and “SD — Levels” fields. We discarded
the other fields. The three statistical measures
of gene expression are normalized over all arrays
(samples) and patients by multiplying values with the
average value of every gene over all arrays divided by
the average value of every gene over the individual
array.
Data for each sample was in a separate text file
with filename indicative of the identifier of the patient
sampled. The data for all samples was concatenated
into a single gene expression file and with the patient
identifier as the initial field. Additionally, the patient
class “Empiric” was associated with the gene expression
data through linking with the patient identifier
although it was not added as an attribute to the large
concatenated file.
3 Approach
The approach we have used is to visualize patients in
the datasets with a kernel–based visualization method
and to look for interesting features in the visualization.
As shown in Fig. 1, we visualize each of the
datasets (i.e. illness, blood and gene expression) in
isolation, in integrated pairs (i.e. illness and blood,
illness and gene, and blood and gene) and finally the
integrated triplet.
As we mentioned above, the integration between
datasets is done using the patient identifier. The patient
class (CFS, ISF or NF) is excluded from the attributes
used in the visualization because this is what
we want to see in the visualization. However, each patient
class is plotted with a different symbol and color
in the visualization. If patients of the same class are
grouped together in a visualization, this lends support
to the claim that there is a relationship in the
dataset. This potential relationship can be investigated
in future work.
3.1 Kernel–based Visualization Approach
The approach we use is related to the kernel–based
extension to Principal Component Analysis (PCA)
(Haykin 1999). Principal Component Analysis is a
well established method that transforms a dataset
into a different coordinate system. The transformation
is essentially a rotation of the dataset. The coordinates
of the transformed dataset (called principal
components) are orthogonal linear combinations
of the original coordinates. The principal components
are ordered in descending order by the amount of variance
they explain in the data. Often much of the variance
in the dataset can be explained by many fewer
coordinates than in the original dataset (e.g. less than
normalised
clinical /
"illness"
data
CFS
NF
normalised
clinical / blood
data
CFS
NF
normalised
gene
expression
data
CFS
NF
patients /
genes
measures
CFS vs NF
data sets for comparison
Transform into integrated
kernel matrix
Cluster & visualise
with kernel based
visualisation
CFS & NF
Points represent patients
Kernel matrix
represents similarity
between patients
Figure 1: Approach used to visualize the individual
and integrated CFS datasets.
ten). This fact means that PCA is often used for compression
of data or feature selection. It also facilitates
visualization of datasets by plotting the first two or
three principal components of the dataset. However,
as principal components are linear combinations of
the original dataset, PCA has the limitation that it
can only model linear relationships in the data.
There have been several approaches to extending
PCA to handle nonlinear relationships. One approach
is kernel PCA (kPCA) ((M¨uller, Mika, R¨atsch, Tsuda
& Sch¨olkopf 2001), (Haykin 1999) or (Shawe-Taylor
& Cristianini 2004)) which transforms the dataset X
into a feature space using a kernel function ! before
the PCA is done. Kernel PCA returns the principal
components of data items in the feature space. It
takes as input a Gram kernel matrix K which is a representation
of the original dataset transformed with
the kernel function. Each element Kij of the kernel
matrix is defined as
Kij = !(xi, xj) = !"(xi), "(xj)" (1)
where xi and xj are the data items, "(xi) is the transformation
of xi into the “feature” space and !·, ·" is
the dot product operator. Generally it is not necessary
to compute "(xi) explicitly. Instead, K is computed
directly from the dataset. This is called the
“kernel trick” and it means that the feature space
can be very large without making generation of K inefficient.
It also means that non–vectorial data types
can be handled using special kernels such as string
kernels (e.g. (Leslie, Kuang & Eskin 2004)).
Two commonly used kernel functions are the linear
kernel and the Gaussian kernel. The linear kernel is
defined as
!(xi, xj) = !xi, xj" (2)
and is simply the dot product of the two data items.
The Gaussian kernel explicitly considers the distance
between data items and is defined as
!(xi, xj) = exp
!
-$xi - xj$2
2#2
"
(3)
where # is a control parameter.
Proc. Fifth Australasian Data Mining Conference (AusDM2006)
55
Finding the principal components in kPCA
amounts to deriving the eigenvalues and eigenvectors
of the kernel matrix K. Shawe–Taylor and Cristianini
describe another technique in (2004) that they say
more explicitly controls the correlation between the
points in the original and feature spaces. The technique
is essentially the same as kPCA except that
it uses (non–zero) eigenvalues and matching eigenvectors
of the Laplacian matrix L(K) of the kernel
matrix instead of the kernel matrix. The Laplacian
matrix is defined as
L(K) = D -K (4)
where D is the diagonal matrix with entries
Dii =
#l
j=1
Kij (5)
where l is the size of the kernel matrix.
In this study, we employ this last method using the
Laplacian matrix to identify the first three principal
components of datasets for visualization. We examine
the data using both the linear kernel in (2) and the
Gaussian kernel in (3).
3.2 Applying Kernel–based Visualization to
the CFS data
Application of the kernel–based visualization scheme
to our datasets was, in general, fairly straightforward.
As described above, the method requires a kernel matrix
representing the dataset to be visualized.
We used the linear kernel and the Gaussian kernel
to make kernel matrices for the clinical datasets
(illness and blood) both individually and in the integrated
pair. Due to its large size, application of a kernel
function to the gene expression dataset required
a special approach similar to that used in computational
linguistics.
Each row of the gene expression dataset represents
an individual gene measurement for a particular microarray
(for each patient). The straightforward approach
of calculating the linear kernel matrix is to
concatenate the rows of the gene expression dataset
into a matrix consisting of one row for each array with
a set of attribute values for each spot label (“ARM
Dens - Levels”, “MAD - Levels” and “SD - Levels”)
then to calculate the linear kernel by multiplying the
matrix with its transpose.
Clearly this approach is impractical in our situation
because of the large number of genes on each
of the arrays. A more efficient approach, motivated
by computational linguistics (see, for example, the
description of generating the vector–space kernel in
(Shawe-Taylor & Cristianini 2004)), for direct computation
of the linear kernel matrix from the gene
expression data is more appropriate.
The kernel value for two samples (i.e. microarrays)
is calculated from sorted lists of genes (spot labels)
associated with each array. The kernel value is calculated
as the sum of the product of the attribute values
for genes matching in both lists.
Computation of the linear kernel for the integrated
datasets (of gene expression combined with illness
and/or blood) is trivial. The linear kernel for the integrated
dataset is simply the sum of the linear kernel
matrices for the individual datasets.
Unfortunately this simple method of computing
the linear kernel for the integrated datasets does not
apply for the Gaussian kernel. In this case it is necessary
to have the entire data vector. Since we never
compute the data vector for the gene expression data
(it is too large), we are unable to easily use the Gaussian
kernel for the gene expression dataset or any integrated
dataset containing the gene expression dataset.
4 Results
4.1 Visualization of individual datasets
We visualise each dataset individually. Figure 2 shows
visualizations of the illness dataset. That is, the
dataset containing patient’s answers to the fatigue
and symptom questionnaires. Figure 2a shows a visualization
of the dataset with the linear kernel and
Fig. 2b shows a visualization with the Gaussian kernel.
The # parameter of the Gaussian kernel was set
to 100 in this case. We examined other settings for
this parameter, but the value 100 gave the clearest
images. As can be seen clearly in both figures, the
NF individuals cluster together on the left hand side,
with the ISF in the middle and the CFS patients on
the right. These pleasing results are expected, as the
data in this dataset is used to make the patient classifications.
For the illness dataset, there is not a great
deal of difference between the visualization with the
linear kernel and with the Gaussian kernel.
We investigated some of the patients marked as
ISF that clustered with the NF individuals on the
left. Patients in the dataset are actually classified
with two different schemes. When we examine some
of the patients that appeared to cluster incorrectly,
they are classified correctly using the other scheme.
Figure 3 shows a visualization with the linear kernel
of the complete blood evaluation dataset. In
Fig. 4 we present visualizations of the same dataset
using the Gaussian kernel. As with the illness dataset
above, we tried different values for the # parameter
of the Gaussian kernel but found that the value of
100 produced the best images. Fig. 4a plots the first
two principal components of the projection of the
data in feature space and Fig. 4b shows the three–
dimensional view. In both the linear and Gaussian visualizations
of the complete blood evaluation dataset
there are no clear groupings of patient classes into distinct
or separable regions. This suggests to us that
there are no simple “biomarkers” in the blood evaluation
dataset associated with CFS. In Fig. 4a there
are some small groupings of CF patients particularly
five clustered in the center of the diagram that may
warrant further investigation.
Finally, in Fig. 5 we present visualizations using
the linear kernel for the gene expression dataset. Figure
5a shows the two–dimensional plot with the first
two principal components and Fig. 5b gives the three–
dimensional view. Three fairly distinct clusters of
patients can be seen. However, these are not naturally
associated with the classes of patient, although
the top right grouping in Fig. 5a contains the least
number of CF patients compared the NF individuals.
The same clusters are visible in the three–dimensional
plot. Although not clearly shown in the diagram
(Fig. 5b), these clusters are mostly embedded in a
plane with only a few data points extending further
along the pc3 axis. Although the clusters do not
seem to be associated with the classes of patient, it
would be interesting to further investigate relationships
within the clusters.
4.2 Visualization of Integrated datasets
In this section we investigate patterns in the integrated
datasets. First we look at the pairs of
datasets. Then we examine the combination of all
three datasets. We visualise the integrated datasets
CRPIT Volume 61
56
a) b)
Figure 2: Kernel visualization of illness classification (questionnaire) dataset. a) linear kernel. b) Gaussian
kernel with # = 100. Axes in both graphs are the first three principal components. + = NF individuals, ! =
ISF patients and " = CF patients.
Figure 3: Kernel visualization of the complete blood
evaluation dataset using the linear kernel. Axes are
the first three principal components. + = NF individuals,
! = ISF patients and " = CF patients.
with only the linear kernel rather than both the linear
and Gaussian kernel functions because (i) the use
of the Gaussian kernel function did not add much to
the visualizations in the previous section and (ii) because
the Gaussian kernel was not applied to the gene
expression dataset for the reasons described above.
Figure 6 shows visualizations of the integrated illness
and blood evaluation datasets. As before, the
visualization on the left (Fig. 6a) shows the two–
dimensional view and on the right (Fig. 6b) the
three dimensional view. It is interesting to compare
these images with the visualizations for the individual
datasets to see the effect of integrating the data
(i.e. with Fig. 2a and Fig. 3). Recall that the NF
individuals were tightly clustered in the visualization
of the illness dataset but not in the blood evaluation
dataset. In the integrated dataset the visualization
shows the NF patients again clustered. However, instead
of the compact clustering of the illness dataset,
the NF individuals are now clustered in a line. In
the three–dimensional visualization most of the data
points are on the surface of a sphere and the NF individuals
appear as line of “longitude”.
Next we integrate the blood and gene expression
datasets and visualise with the linear kernel function
in Fig. 7. Comparing with the graphs of the individual
datasets in Figures 3 and 5 it can be seen that
the structure of the gene expression dataset dominates.
The diagram of Fig. 7a seems to be the reflection
across the horizontal of Fig. 5a. Similarly,
the visualization of the integrated illness and gene
expression datasets in Fig. 8 are essentially the same
with the structure completely controlled by the gene
expression dataset. We speculate that the reason that
the gene expression dataset dominates the structure
is that it contains many more attributes than either
the illness or blood evaluation datasets.
Finally, in Fig. 9 we present the linear kernel visualization
of the integrated triplet of datasets. Again,
the situation is the same as above and the gene expression
dataset dominates the visualization. There
are again three fairly distinct clusters that are not
naturally associated with the patient classes.
5 Discussion and Future Work
The kernel–based visualization approach allows us to
integrate datasets in a straightforward way, particularly
if we are content to limit ourselves to the linear
kernel. This limitation, at least in the context of our
study, does not seem to be onerous because the differences
between visualizations of the individual blood
and illness datasets with the linear and Gaussian kernel
functions seemed to be relatively unimportant.
Being able to visualise integrated datasets in this
way supports a “constructionist” approach to data
analysis where we look for “global” patterns in the
integrated dataset. The opposite method, a “reductionist”
approach, looks for “local” patterns over subsets
of attributes in individual datasets. An example
of the latter approach in the context of this paper is
Proc. Fifth Australasian Data Mining Conference (AusDM2006)
57
a) b)
Figure 4: Kernel visualizations of complete blood evaluation dataset using the Gaussian kernel with # = 100.
a) Axes are the first two principal components. b) Three–dimensional visualization. + = NF individuals, ! =
ISF patients and " = CF patients.
the search for small sets of genes indicative of CFS.
We do not necessarily advocate a “constructionist”
approach over “reductionist” ones. Rather, it is better
to apply both approaches which look at different
ends of the problem. A combined approach would
identify global patterns, which can be used to focus
the search effort for local patterns.
It was heartening that the kernel–based visualization
was able to distinguish patterns in the illness
data as this data was used to make the CFS diagnosis.
Visualizations of the other datasets did not show
such clear patterns. However, the three clusters in
the datasets containing gene expression data warrant
further scrutiny.
The kernel–based visualization technique is a general
purpose approach and can be applied to other
biomedical datasets. Indeed we intend to examine
the domain of acute lymphoblastic leukaemia next.
Previous work exists linking the cancer to genes so
we expect to see clear clusters in this domain.
Use of specialized kernels with the technique allows
visualization of non–vectorial data. We essentially
used this kind of approach to efficiently build a linear
kernel for the gene expression data in Section 3.2.
We are also interested in the issue of the structure
from the gene expression dataset dominating over the
other datasets. It is important to understand why
this is the case: is it the result of the structure of the
integrated dataset or is it due to the relative numbers
of attributes in the individual datasets? This
question must be addressed before there can be more
widespread use of the technique for visualization of
integrated datasets. We think that the issue here is
indeed the large discrepancy between the numbers of
gene expression attributes compared to the number of
clinical attributes. Any method, such as the one we
use, that treats attributes as equally important, will
be dominated by the dataset with the larger number
of attributes. One approach we plan to use to overcome
this problem is to apply feature selection on the
datasets before the data integration and visualisation.
This feature selection will even up the relative numbers
of attributes in the different datasets.
The linear kernel used in this study is able only to
identify linear relationships in the data. Use of other
kernels (such as the polynomial or Gaussian kernels)
allows visualization of nonlinear relationships. In this
work we were restricted to use of the linear kernel because
of the size of the gene expression data. Efficient
calculation of other kernels for the gene expression
data is another area of future investigation.
6 Conclusion
This study describes the use of a kernel–based approach
using the Laplacian matrix to visualise an
integrated Chronic Fatigue Syndrome dataset with
symptom and fatigue questionnaire and patient classification
data, complete blood evaluation data and
patient gene expression profiles. Visualizations were
produced for individual and integrated datasets with
linear and Gaussian kernel functions. We described
an efficient approach to constructing a linear kernel
matrix for the gene expression data. The visualizations
of the questionnaire data showed a cluster of
non–fatigued individuals distinct from those suffering
from Chronic Fatigue Syndrome. This observation
supports the fact that diagnosis is generally made using
this kind of data. The method was unable to find
clusters in the other datasets that related to patient
classes, although three distinct clusters were found in
the gene expression data. Structure from the gene
expression dataset dominated visualizations of integrated
datasets that included gene expression data.
References
Afari, N. & Buchwald, D. (2003), ‘Chronic fatigue
syndrome: A review’, American Journal of Psychiatry
(160), 221—236.
Baldi, P. & Hatfield, G. W. (2002), DNA Microarrays
and Gene Expression: from experiments to
data analysis and modeling, Cambridge University
Press.
CDC Chronic Fatigue Syndrome Research
Group (2005), ‘CAMDA 2006 conference
contest datasets’, cited; Avail-
CRPIT Volume 61
58
a) b)
Figure 5: Kernel visualization of gene expression dataset using the linear kernel. a) Two dimensional visualization
with axes being the first two principal components. b) Three–dimensional visualization. + = NF
individuals, ! = ISF patients and " = CF patients.
able from: http://www.camda.duke.edu/
camda06/datasets/, viewed at 10 March 2006.
Haykin, S. (1999), Neural networks: a comprehensive
foundation, 2nd edition edn, Prentice–Hall.
Leslie, C., Kuang, R. & Eskin, E. (2004), Inexact
matching string kernels for protein classification,
in B. Sch¨olkopf, K. Tsuda & J.-P. Vert, eds,
‘Kernel methods in computational biology’, MIT
Press, pp. 95–112.
Li, W., Ng, W.-K. & Lim, E.-P. (2004), Spectral
analysis of text collection for similarity–based
clustering, in H. Dai, R. Srikant & C. Zhang,
eds, ‘Proceedings of Pacific–Asia Knowledge Discovery
and Data Mining Conference (PAKDD)
2004’, LNAI 3056, Springer–Verlag, Berlin Heidelberg,
pp. 389–393.
M¨uller, K., Mika, S., R¨atsch, G., Tsuda, K. &
Sch¨olkopf, B. (2001), ‘An introduction to kernel–
based learning algorithms’, IEEE Transactions
on Neural Networks 12, 181–201.
National Center for Infectious Diseases (2005),
‘Proposal: clinical assessment of subjects with
Chronic Fatigue Syndrome and other fatiguing
illnesses in Wichita’, cited; Available from:
ftp://ftp.camda.duke.edu/CAMDA06 DATASETS/
wichita clinical irb protocol.doc.
Reeves, W. C. et al. (2005), ‘Chronic fatigue syndrome
— a clinically empirical approach to its
definition and study’, BMC Medicine 3(19).
Shawe-Taylor, J. & Cristianini, N. (2004), Kernel
Methods for Pattern Analysis, Cambridge University
Press, Cambridge.
Smets, E. M., Garssen, B. J., Bonke, B. & DeHaes,
J. C. (1995), ‘The multidimensional fatigue inventory
(MFI) psychometric qualities of an instrument
to assess fatigue’, J. Psychosom. Res.
39, 315–325.
Wagner, D., Nisenbaum, R., Heim, C., Jones, J. F.,
Unger, E. R. & Reeves, W. C. (2005), ‘Psychometric
properties of a symptom–based questionnaire
for the assessment of chronic fatigue
syndrome’, BMC Health Quality Life Outcomes
3(8).
Ware, J. E. & Sherbourne, C. D. (1992), ‘The MOS
36–item short form health survey (sf–36): conceptual
framework and item selection’, Med.
Care 30, 473–483.
Weng, L., Dai, H., Zhan, Y., He, Y., Stepaniants,
S. B. & Bassett, D. E. (2006), ‘Rosetta error
model for gene expression analysis’, Bioinformatics
22(9), 1111–1121.
Proc. Fifth Australasian Data Mining Conference (AusDM2006)
59
a) b)
Figure 6: Kernel visualization of integrated illness and blood datasets using the linear kernel. a) Two dimensional
visualization with axes being the first two principal components. b) Three–dimensional visualization. +
= NF individuals, ! = ISF patients and " = CF patients.
a) b)
Figure 7: Kernel visualization of integrated blood and gene expression datasets using the linear kernel. a) Two
dimensional visualization with axes being the first two principal components. b) Three–dimensional visualization.
+ = NF individuals, ! = ISF patients and " = CF patients.
CRPIT Volume 61
60
a) b)
Figure 8: Kernel visualization of integrated illness and gene expression datasets with the linear kernel. a) Two
dimensional visualization with axes being the first two principal components. b) Three–dimensional visualization.
+ = NF individuals, ! = ISF patients and " = CF patients.
a) b)
Figure 9: Kernel visualization of integrated blood, illness and gene expression datasets with the linear kernel.
a) Two dimensional visualization with axes being the first two principal components. b) Three–dimensional
visualization. + = NF individuals, ! = ISF patients and " = CF patients.
Proc. Fifth Australasian Data Mining Conference (AusDM2006)

Applied linguistics

 

Main article: Applied linguistics
Whereas theoretical linguistics is concerned with finding and describing generalities both within particular languages and among all languages, applied linguistics takes these results and applies them to other areas. Often applied linguistics refers to the use of linguistic research in language teaching, but this is just one sub-discipline:
• Research in language teaching: today, 'applied linguistics' is sometimes used to refer to 'second language acquisition', but these are distinct fields, in that SLA involves more theoretical study of the system of language, whereas applied linguistics concerns itself more with teaching and learning. In their approach to the study of learning, applied linguists have increasingly devised their own theories and methodologies, such as the shift towards studying the learner rather than the system of language itself, in contrast to the emphasis within SLA.[13][14]
• Applied computational linguistics: two computer applications are speech synthesis and speech recognition, which use phonetic and phonemic knowledge to provide voice interfaces to computers. Machine translation, computer-assisted translation, and natural language processing are fruitful areas which have also come to the forefront in recent years.
• Clinical linguistics entails the application of linguistics to speech-language pathology. This involves treating individuals whose linguistic development is atypical or impaired.[15] This branch of applied linguistics may also involve treatment of specific language impairment, where one aspect of language develops exceptionally.[16] The field has also adopted existing ideas which have have not become 'mainstream' in theoretical linguistics. For example, both behaviourism[17] and natural phonology[18] have appeared in the literature.

Linguistic reality and technological limitations - brains vs chips

Thomas Hansen
University of Southern Denmark
Natural Interactive Systems Lab
thomas@nis.sdu.dk

Abstract

Behind the somewhat pompous name of this paper hides a much
more modest aim. It is an attempt at clarifying one of the major
problem areas found in the field of Computer Assisted Language
Learning (CALL), specifically the use of Automatic Speech
Recognition (ASR). The aim of CALL is to produce tools aiding
the acquisition of foreign languages and, long-term, to produce
full-fledged, virtual, multi-modal language tutors. In essence, the
teacher in the machine.
Focusing specifically on Computer Assisted Pronunciation
Training (CAPT) I intend to present a, hopefully, pedagogic
picture of how the mind works in relation to adopting the sounds of
a foreign language (L2), both perception- and productionwise, and
illustrate the shortcomings of ASR in comparison.
I also intend to present you with some rather unsubstantiated ideas
on language learning which can hopefully generate a wholesome
debate.
1. Introduction - and some fairly unsubstantiated claims open for discussion
Learning a foreign language is by no means a task which is accomplished easily. In recent years a trend has become visible which, within school systems, exposes children to foreign languages
earlier than ever seen before and the immigration politics of different countries focus much more on adult immigrants acquiring the native language as a prerequisite for permanent residence.
As the demand for faster, better and more autonomous language study increases, scientists have
begun looking at the computer as a potential aid in language acquisition. Some even speculate in the idea of an autonomous interactive, multi-modal language teacher/tutor. Although I find myself convinced that this will someday be reality, there are, as yet, multiple areas in which technology needs to improve in order to qualify for such a label, ASR not the least.
In my opinion the area in which computers can, presently and long-term, benefit learners the most is within the area of pronunciation. Very often in classes consisting of 20-40 people teachers will not have the available time to practice with and correct individual student pronunciation. Areas such as vocabulary and grammar tutoring lend themselves much more easily to a (blackboard) class-based teaching environment. In my opinion languages are not learned in class. Only building blocks aiding the learning of the language are provided within such an environment. One does not fully learn a language until one has to use the language in an actual situation with native speakers.
Furthermore, using a language entails possessing some rudimentary communication skills. It is my firm belief that three different priorities for language acquisition can be established1:
1. Vocabulary
2. Pronunciation
3. Grammar and all the rest.
 This claim was partly reached through a conversation with a Chinese test subject who said, “I know everything about
the grammar, I just can’t for the life of me pronounce it.”
In order to be able to speak a language a learner must know some basic words. Without a
vocabulary nothing else will work. Again, in order to use that vocabulary a learner needs to be able to pronounce the contents. Subsequently learners can be taught to arrange words in their proper
position. Whether a student utters the sentence: 1) “Me beer want,” or 2) “I would like a beer,” he or she will still be understood. This is comparable to tourists visiting foreign countries and availing themselves of standard phrases which have been picked up in one way or the other.
Learning a language in class is much like learning to drive a car. Initially you are presented with all the rules and interpretations of the signs, but it is not until you find yourself alone, driving the car on your own in actual traffic that you really learn how to drive.
Computer Assisted Language Learning, in time, carries the potential to provide you with your own car, but there are many hurdles which need to be overcome before this becomes reality.
2. Computer Assisted Language Learning
Computer Assisted Language Learning (CALL) and Computer Assisted Pronunciation Training
(CAPT) are areas in the academic field that explore the role of information and communication
technologies in language learning and teaching. This includes: materials development, pedagogical practice and research. Both are interrelated areas that have experienced rapid growth in recent years.Especially the introduction of the internet and the computer as a household item has spawned the possibility of online learning and computer applications in language learning [Levy, 1997].
Today CALL/CAPT have established themselves as prolific areas whose advantages are well
known to language educators. As a matter of fact I believe that this area should be viewed as a branching tree with a headline and several subdivisions, depending on your focus. CALL seems to me to be initial node, CAPT comes directly beneath it on its own branch. Other branches could be areas of grammar learning and vocabulary learning.
 See for instance (Neri, Cucchiarini, Strik & Strik 2002).
1) Training available at any time the learner wishes – (install on laptop and transport)
2) More and faster individualized feedback for the learner. – (only the learner uses it)
3) Stress free environment for the learner to practice in. – (nobody listens, no time limit)
4) More practice time than in a classroom setting. – (available anytime)

The above four points should be viewed in terms of a class setting versus a non-class setting.
But, as pointed out by Neri [Neri, 2001], many are concerned with the missing link between
technological advances and Second Language Acquisition (SLA) research. One task at hand lies in bridging the gap between proceduralists and formalists, those who wish to build applications versus those with knowledge of language [Chambers, 2001]. In essence a method for pronunciation training is needed which focuses on both the linguistic perception and production facets of learning a language as well as taking into consideration the shortcomings and possibilities of present day
technology.
Perception and production
Nearly all people are born with the capacity of speaking one language with native competence (L1), but children and adults differ greatly in their ability to learn a second language (L2). To find bilingual children with the competence of speaking both languages with native qualities is not unusual and even throughout their initial years of education they may acquire a third or fourth language where they attain near-native qualities. Research shows that around the age of thirteen the capacity for learning a language seems to diminish, otherwise known as the Critical Period
Hypothesis (CPH) [Lenneberg, 1967; Flege, 1987]. Upon reaching adolescence our capacity to
interpret new phonetic input (i.e. sounds not indigenous to our native language) seems to fossilize. This is evidenced in many adults attempting to acquire a second language but producing it with heavy accent coloring. In 1957 Noam Chomsky coined the term Universal Grammar (UG) [Chomsky, 1957] arguing that all people possessed an underlying language module which acted as a blueprint for acquiring language. Once all the sounds of the native language have been ‘put into place,’ they are grouped in acoustic categories appropriate for the L1.5 Heavy accent coloring in L2 acquisition has then hitherto been explained via Equivalence Classification [Flege, 1987]: Upon attempting to acquire the sounds of the L2, these pass through the ‘phonological filter’ of the L1 and are assimilated to the sounds already known. In other words, the learner will attempt to compare the new sound with an already existing one in his or her native language, and produce the already known sound rather than the new one. This is also known as Acoustic Assimilation. Hence, a necessary component of speaking a foreign language with native quality is the ability to perceive the phonetic differences between the mother tongue and the target language. Additionally the ability to produce the sound is dependent on the ability that a learner must be able to perceive the difference in acoustic quality before he/she can produce it and thereby make room for new acoustic categories for the language in question.6
There are, of course, numerous other processes involved in the acquisition of a foreign language
besides the ones that relate specifically to speech viewed as a simple acoustic signal. These relate to extra-linguistic factors such as body movement, but are not treated in this paper.
It should be noted that the theory of Universal Grammar is highly controversial and opposing viewpoints can be found in most of the linguistic literature by J.R. Firth and M.A.K. Halliday. I am not an avid proponent of UG theory, but it does seem to provide a pedagogically sound picture of the elements involved in language acquisition.
Acoustic categories can here be thought of as those ‘vowels’ and ‘consonants’ that we view as a fixed inventory for a particular language. Other languages will posses different acoustic qualities.
There are opposing views on the matter such as Borrel [Borrel, 1990] who claims that production precedes perception. Mastering the motor mechanics (in relation to the tongue), should facilitate the perception factor. My personal view, based mostly on simple intuition, disagrees with that statement.
4 CALL – ASR and all the problems we encounter
Today the most widely used piece of technology in CAPT applications are Automatic Speech
Recognition (ASR) systems. ASR allows the L2 learner to interact with the constructed software as well as provides the possibility of the learner’s pronunciation to be understood and evaluated
immediately, by analyzing the acoustic signal provided by the learner. In an ideal CAPT application the level of feedback should emulate that provided by human teachers in terms of, for instance, segmental correction. A teacher standing in front of a student is able to offer corrective feedback in respect to motor movements of the mouth, articulatory advice, guide the student on the phonetic as well as the sentence level. Hence, a non-native speaker pronouncing the word as
should be informed that the second segment should be pronounced differently, followed by
exemplification. Currently the best available option in terms of computer feedback is provided
through the use of ASR systems. However, numerous problems are encountered when employing
ASR technology in CAPT systems. These problems are manifold and can be exemplified on, at
least, two separate, yet interdependent, levels:
1. Single word pronunciation
2. Sentence level pronunciation
ASR systems, unlike the human auditory system, are currently incapable of distinguishing between and non-speech sounds. Hence a cough, a sigh, a hiccup, the slamming of a door, the chirp of a bird, all these sounds will be interpreted by the ASR system as constituting a speech signal and the system will attempt to match this signal with an already incorporated vocabulary. Even the possibility of having a faint echo in the room when producing an utterance will potentially be misinterpreted by the ASR.
Limited vocabulary, or simply out-of-vocabulary, constitutes another problem for ASR systems.
Most often the training material available to the student is fairly limited since not all words,
counting inflections and similar, are part of the trained or inbuilt vocabulary.
This in turn brings up a related problem, namely that of dialectal variation and speaking style.
Dialects can in some cases vary to such a degree that they can almost be considered languages
within languages. Even the human auditory system can run into trouble at this level. Differences are also visible in terms of physiological differences in the human vocal tract.
In addition to dialects, we also encounter differences in speaking styles as well as differences
between the acoustic signals of men, women and also children. In many cases ASR systems are not capable of handling these differences unless specifically designed to cater to a particular group.
Furthermore ASR systems often run into trouble when the vocabulary becomes too similar. Hence, minimal pairs such as and are very difficult to distinguish. Most ASR systems seem
happier when the phonetic material provided is polysyllabic.
Even more difficult, if not entirely impossible is the aspect of getting ASR systems to provide
segmental feedback. Segmental feedback requires the isolation and identification of single-phones
in a context of other phones. Hence the system should ideally be able to recognize whether a [k] is pronounced with aspiration or without aspiration, or even as non-released. ASR systems are
composed, mostly, of diphones or triphones, hence eliminating the possibility of single-phone
identification. Creating an acoustic model which would be able to distinguish between all the
different phonetic realizations of sounds does indeed provide a daunting task.
The already mentioned problems are then even further magnified when examining continuous
speech. Continuous speech has no apparent boundaries from which the ASR system can solidly
deduce single words. This can be seen from perhaps the most widely used example listed below.
How is an ASR system to know whether a speaker says:
1. Recognize speech
2. Wreck a nice beach
As human listeners we have the advantage of context and reasoning, an ASR system does not.
Further examples can be found in the area of homophones, which are words that sound the same but are spelled differently i.e. sale versus sail. All in all speech recognition still suffer from severe shortcomings in terms of functioning as substitute and autonomous language teachers.
5 Conclusion
In this paper I have attempted to outline two very different processes, which aim at achieving the
same goal, namely that of creating new speech sounds in learners of a foreign language, perception and production of the mind versus perception in ASR.
As we have seen, acquiring new speech sounds is by no means an easy task once a native language has become fossilized. Human teachers have the ability to tutor and monitor individuals as well as correcting minuscule differences between the mother tongue and the L2, but to some degree they suffer from not having enough time to devote to each individual students. ASR, if viewed as part of a larger package, does contain the possibility of providing students with more time for learning and individual practice and correction, but are simply not able to generate feedback which is finegrainedenough to highlight small differences in language sounds. Furthermore, ASR systems as standalone applications are entirely unable to provide the learner with the

Linguistic Knowledge and Reasoning for Error Diagnosis and Feedback Generation

RODOLFO DELMONTE
Department of Language Sciences
Università Ca' Foscari - Ca' Garzoni-Moro
Venice, Italy

Abstract:
We present four sets of NLP-based exercises for which error correction and feedback are produced by means of a rich database in which linguistic information is encoded either at the lexical or at the grammatical level. One exercise type "Question-Answering" utilizes linguistic knowledge and inferential processes on the basis of the output generated by GETARUN, a system for text understanding. GETARUN produces a complete parse of a text and a semantic mapping in line with situational semantics in the form of a Discourse Model. Another exercise, Grammcheck, uses a 'robust' version of the parser to produce suitable environments for grammatical error spotting and consequent accurate and precise feedback generation for German. The parser of GETARUN is then presented as an analytical tool for students who study Lexical Functional Grammar (LFG). Finally, exercises on "Essay Evaluation," which are cast into the more general problem of text summarization, are discussed. In this case, the system is used to perform multidocument sentence extraction on the basis of a statistically based Summarizer. This summary is then compared with the student's summary. All applications can be found at our web site, project.cgm.unive.it.

1. INTRODUCTION

The GETARUN program (Delmonte, 1990; Delmonte, Bianchi, & Pianta, 1992; Delmonte & Bianchi, 1998) is a system for text and reference understanding, which is currently being used for summarization and text generation, and has a sophisticated, linguistically based semantic module used to build up a discourse model (DM). Semantic processing is strongly modularized and distributed among a number of different submodules which take care of spatio-temporal reasoning, discourse level anaphora resolution (Delmonte & Bianchi, 1999), and other subsidiary processes like topic hierarchy—which impinges on relevance scoring when creating semantic individuals. The system uses a parser that requires

in its deep version a complete lexicon of the domain in which it will perform its analysis. This deep version is used for students of linguistics as an aid in the assessment and control of grammatical principles. It allows for the parsing of grammatical and ungrammatical sentences. The "shallow" version of the parser allows students of German to get detailed information on their grammatical mistakes. We will show how GETARUN is used for different linguistic exercises for learners of different languages. We will concentrate on how GETARUN facilitates the provision of adequate feedback.

1.1 Self-assessment and Feedback

Generally speaking, assessment in self-instructional courses is problematic but of course very important. Within learner-centered self-instruction, or self-directed learning, self-assessment is a necessary part. Decisions about whether to go on to the next item, exercise, or unit; the allocation of time to various skills; or the need for remedial work are all based on feedback from informal and formal assessment. This concept then is central both to learners and to the kind of courseware we wish to build. We consider self-assessment important as an educational goal in its own right, and training learners to use self-assessment is beneficial to learning. In fact, language learners regularly engage in self-assessment as part of their learning. They complete exercises and check, by whatever means available, whether their responses are correct or not.

In this paper, we present an approach to teaching the comprehension of spoken and written texts by facilitating related text production and by providing explanatory feedback. We consider understanding texts, whether oral or written, an important objective of language learning. A system for CALL that is aimed at tutoring and testing students in text understanding should ideally be equipped with a feedback module to provide explanations for mistakes made by the students. However, many systems today provide very limited feedback: an answer is either right or wrong, and no explanation is made available. An additional limitation is that drills for text understanding on the computer are often of one of two types: multiple choice and/or true/false decisions. Drills that permit students to answer questions by producing free text, even short segments, are rare because automatic analysis and feedback are hard to implement for written language. Production tasks constitute a challenge in that the right feedback may be unavailable if students make an unanticipated mistake, one not included in a list of possible mistakes.

What kind of feedback could be given? In their paper, Lyster and Ranta (1997:45) make the following classification of feedback by human tutors:

1. Explicit correction: "the explicit provision of the correct word or part phrase, usually making clear that this is a correction— e.g. you mean …, you should say … ."

2. Recast: "the teacher's reformulation of all or part of the student utterance, minus the error, without making it clear that this is a correction."

3. Clarification request: "What? What do you mean? (only coded in response to language error)."

4. Metalinguistic feedback: "comments, information or questions regarding the well-formedness of the student's utterance, but without giving the correct form: that's not quite right, is that right?"

5. Elicitation: "getting the student to give the correct form by pausing for her to continue the sentence, or by asking the student to reformulate the utterance."

6. Repetition: "the repetition, in isolation, of the student's utterance, usually with error intonationally marked."

We believe that recast, clarification request, elicitation, and repetition are totally inadequate for feedback generation on a computer. As to explicit correction, perhaps it could be done for grammar drills, but it is certainly much harder in semantically based drills. We assume that only metalinguistic feedback is fully compliant with the current state of human-computer interaction.

In all cases, we want learners to be informed about the error they made, the kind of error they made, and the possible reason why they made it. In addition, they can be directed to carry out some linguistic activity appropriate to help them remedy the problem.

1.2 Our Applications

The applications presented in this paper are all concerned with text comprehension. The first one, Grammcheck, presented in section 2 below, is an application for students of German which prompts them to create sentences for which they are given a sequence of base forms or lemmata. These lemmata are taken from a database of correct and incorrect sentences that constitutes the Linguistic Knowledge Database (LKD). We also use a large lexicon of German where lemmata are fully classified with subcategorization frames and morphological features. Knowledge in this case is resident both in the database and in the grammar contained in the analysis program—a robust parser of German.

The second application uses the same system as Grammcheck for German (see section 3 below). It is called GETARUN. Here we use its complete and deep version. The idea for these activities is to help students understand the relevance of linguistic and extralinguistic information in the grammatical analysis and the representation of sentences of a given language—English in this case. The system uses a top-down, depth-first definite clause grammar (DCG) parser with lookahead and a well-formed substring table (WFST) lookup in case of failure to improve efficiency. It implements the core and periphery grammar rule model accompanying the notion of Universal Grammar. This allows it to be multilingual, that is, it parses with the same grammar and set of parameters for German, English, and Italian. The important feature of the parser is the implementation of parsing strategies to allow for multiple analyses of a single input sentence to be appropriately executed.

In section 4, we discuss the generation of "Question-Answering" exercises which utilize linguistic knowledge and inferential processes on the basis of the output generated by GETARUN, our system for text understanding. The GETARUN system produces a complete parse of a text and a semantic mapping in line with situational semantics in the form of a discourse model (DM). The DM is used to generate questions and answers based on the text that the system analyzed and that the students had to read. Students are then given feedback on the question and answers they selected.

Finally, in section 5, exercises on "Essay Evaluation," which are cast into the more general problem of text summarization, are discussed. In this case, the system is used to perform multidocument sentence extraction on the basis of a statistically-based Summarizer. This summary is then compared with the student's summary.

2. GRAMMCHECK

The first application is a grammar checker for Italian students of German (and English) (see Delmonte, Chiran, & Bacalu, 2001; Delmonte, 2000a). It is based on the shallow parser of Italian used to produce the syntactic constituency for the National Treebank. The output of the parser is a bracketing of the input tagged word sequence which is then passed to the higher functional processor. This is a Lexical Functional Grammar (LFG)-based c-structure to f-structure mapping algorithm which has three tasks: the first task is to compute features from heads; the second is to compute agreement, and the third is to impose LFG's grammaticality principles of coherence and consistency to insure that the number and type of arguments are constrained by the lexical form of the governing predicate.

The parser uses a recursive transition network (RTN) which has been endowed with a grammar and a lexicon of German of about 8,000 entries. The grammar is written in the usual arc-transition nodes formalism, well known in augmented transition networks (ATN). However, the aim of the RTN is to produce a structured output both for well formed and ill formed grammatical sentences of German. To this end, we allowed the grammar to keep part of the rules of Italian at the appropriate structural level. Grammar checking is not accomplished at the constituent structure building level, but at the function-structure level.

2.1 The Shallow Cascaded Parser

The function of the shallow cascaded parser is to create syntactic structures eligible for grammatical function assignment. This task is made simpler given the fact that the disambiguator associates a net or constituency label with each disambiguated tag. Parsing can then be defined as a bottom-up collection of constituents which contain either the same label or which are contained in or are a member of the same net or higher constituent. No attachment is performed

in order to avoid being committed to structural decisions which might then reveal themselves to be wrong. We prefer to perform some readjustment operations after structures have been built rather than introducing errors from the start. Readjustment operations are in line with the LFG theoretical framework which assumes that f-structures may be recursively constituted by subsidiary f-structures (i.e., by complements or adjuncts of a governing predicate). So the basic task of the shallow parser is that of building shallow structures for each safely recognizable constituent and then pass this information to the following modules.

The tagset we use for German consists of 85 tags which encore a number of important features for the parser such as transitivity, modality, and auxiliary class for verbs and semantic classes like color, human, and evaluative for nouns. Tags are disambiguated by a statistical and syntactic procedure which is set up for special ambiguity classes. In some cases, we use appropriately organized Finite State Automata. The output of the disambiguator is a partially disambiguated input which is then processed by the shallow cascaded parser. 

2.2 Syntactic Readjustment Rules

Syntactic structure is derived from shallow structures by a restricted and simple set of two categories of rewriting operations: deletions and restructuring. In building syntactic constituents, we obey the general criteria below:

1. We accept syntactic structures which belong to either language—German or Italian.

2. Constituency should allow for the recovery of errors in the higher structural layers where functional mapping takes place.

3. The tensed verb is treated in a special manner. If it is sentence final, it belongs to a separate ibar constituent called IBAR2, and it triggers the building of a specific IP clausal constituent called FYESNO in all "aux-to-comp"-like structures and structures subject to inversion. Otherwise, it is treated as in Italian.

2.3 From C-structure To F-structure

Before working at the functional level, we collected 2,500 grammatical mistakes from students' final tests. We decided to keep track of the following grammatical mistakes which are typical for Italian learners of German: lack of agreement NP internally; wrong position of argument clitic pronouns; lack of subject-verb agreement; wrong position of the finite verb in main clauses, subordinated clauses, or coordinated clauses; and wrong case assignment. Example (1) illustrates this process.

(1) Heute willst ich mich eine bunte Krawatte umbinden.

'today want I me a colorful scarf tie'

(today I want to wear a colorful scarf)

cp-[

advp-[adv-[heute]],

vsec-[vmod-[willst],

fvsec-[subj2-[np-[pers-[ich]]],

obj-[np-[clitdat-[mich]]],

obj1-[np-[art-[eine],adj-[bunte],

n-[krawatte]]],

ibar2-[vit-[umbinden]]]

], punct-[.]]¹

The parser issues two error messages. The first one regards case assignment: mich is in the accusative whereas dative is required. The second one concerns subject-verb agreement: willst is second person singular whereas the subject ich is first person singular. In order to recognize errors, full morphological and lexical subcategorization information for all words must be available. For instance, the entries for ich, wollen, and umbinden are specified in example (1).

2.4 Sentence Creation and Automatic Evaluation

In order to build exercises automatically, we duplicated all the sentences with mistakes from our database and created the corresponding correct sentences. This procedure allowed us to generate exercises for students by picking at random

a certain number of sentences, say three or four, from the correct subset and mix them with one or two sentences from the mistakes subset. The task for students could be either to identify the sentences with error(s) or correct the error(s). In either case, their response could be easily checked. Rather than discussing these exercises, we will concentrate on the "Sentence Creation" exercise which requires students to produce a correct sentence from a sequence of input hints consisting of lemmata (uninflected content words). This procedure first selects one of the correct sentences. It then deletes the function words in the sentence and displays the lemma for each content word. The resulting sequence of words is presented to students who are asked to build a correct sentence. Given the fact that students can produce any sentence using the lemmata provided, we cannot evaluate their responses by a simple pattern-matching operation. The parser has to check for correctness.

The system addresses issues for students of German who are enrolled in degree programs in Linguistic Sciences where General Linguistics and other similar courses are required. Students are asked to repeat an exercise after they have checked for mistakes in the feedback window. In the case of a sentence being correctly entered, the system simply confirms the correctness and proposes a new sentence. Whenever students decide to interrupt the exercise, an evaluation is issued for the whole interaction, and the result is shown graphically by turning previous successes and failures into scores and then transforming scores into colored bars: red for mistakes and green for correct sentences. A comment is generated based on the severity of the errors and by relying on the overall score.

3. GETARUN: A PARSER FOR LFG STUDENTS

We have seen how the shallow version of the GETARUN parser is used for the analysis of linguistic errors. Here, the detailed description and disambiguation of sentences in linguistic analysis is the task of the 'deep' version of the parser. The GETARUN program is a web-based multilingual parser which relies mainly on Lexical Functional Grammar (LFG) theory and partly on Chomskian theories and incorporates a number of parsing strategies which allow students to parse ambiguous sentences using the appropriate strategy in order to obtain an adequate grammatical output. The underlying idea was that of stimulating students to ascertain and test linguistic hypotheses by themselves by means of a linguistically motivated system architecture. The parser builds c-structure and f-structure and computes anaphoric binding at the sentence level; it also has provisions for quantifier raising and temporal local interpretation. Predicates are provided for all lexical categories, and their description is a lexical form in the sense of LFG. 

Web Version of the LFG Parser

It is composed both of functional and semantic specifications for each argument of the predicate: semantic selection is operated by means both of thematic role and inherent semantic features or selectional restrictions. Moreover, in order to select adjuncts appropriately at each level of constituency, semantic classes are added to the more traditional syntactic ones. Semantic classes are of two kinds: the first class is related to extensionality versus intensionality and is used mostly to build discourse relations; the second class is meant to capture aspectual restrictions which decide the appropriateness and adequacy of adjuncts so that inappropriate ones are attached at a higher level. 

3.1 Parsing Strategies

Another phenomenon which receives some attention in the study of linguistics is ambiguity (see Schubert, 1984; Altman, 1989; Frazier, 1987). Ambiguities arise, for example, if a pronoun in the subclause could have one of two antecedents in the main clause:

(2) The authorities refused permission to the demonstrators because they feared violence.

The authorities refused permission to the demonstrators because they supported the revolution.

The underlying mechanism for ambiguity resolution takes one analysis as the default in case it is grammatical. The other plausible interpretations are obtained by activating one of the available parsing strategies which are linguistically and psychologically grounded (see Delmonte, 2000b, 2000c). These strategies allow us to check in the example above whether there is more than one antecedent for a pronoun. Generally, the strategies are used to re-assess syntactic structures which are prone to ambiguity. With this application, we hope to help students understand syntactic analysis better.

4. QUESTION-ANSWER SEQUENCES FOR LISTENING COMPREHENSION TASKS

We are not using the complete version of the GETARUN parser only for syntactic analysis. The parser also provides the basis for the generation of exercises which follow from text understanding. Text understanding (see Iwanska & Shapiro, 2000; Herzog & Rollinger, 1991; Delmonte, 2002b, 2002c) is a task which constitutes a challenge in that the right feedback may not be available if students provide an incorrect answer which is not included among the list of possible mistakes.

We use question-answer dialogs with listening comprehension tasks. Students hear a text read by the internal text-to-speech module or a previously recorded text. No written version is provided to students. At the end of the listening activity, a certain number of questions appear on the screen, and students are prompted to provide answers to each of them.

Each text given to students is represented in the system in the form of a discourse model (DM) and turned into an appropriate database structure. This structure can then be analyzed by our programs. The system takes as the starting point the feature structures represented as direct acyclic graphs (DAGs) of each input sentence analyzed by the parser. Then, in the semantic analysis, the f-structure is turned into a logical form (i.e. a set of well formed formulas). These formulas are mapped onto semantic representations, that is, predicate-argument structures with a polarity and a couple of indices for spatiotemporal locations (based on situation semantics). The final output is a DM. 

4.1 Queries to the System

We present a Question-Answer module which can be used for well defined domain.

The domain in our case coincides with the text the system has just analyzed and transformed into a DM. Below are some of the queries that can be addressed to the system (see Delmonte, 2002a), here generated by the system. The reason why we let the system generate both questions and answers is that we want to prevent the dangers related to the "open dialogue" mode of questions and answers; we work within the much safer "close dialogue" mode. We also want to prevent having to check for appropriate orthography and grammar and to concentrate on text understanding. The queries generated include questions on spatio-temporal locations (see Bianchi & Delmonte, 1996), identity, and activities. 

5. EXTRACtING AND SUMMARIZING WITH GETARUN

In this section we shall present the use of GETARUN for the generation of short summaries (see Boguraev & Kennedy, 1997; Mani & Maybury, 2000). The system builds a semantic database of facts describing the entities of the world contained in the text(s) under analysis along with their properties and relations. This is achieved by tagging and shallow-parsing the tokenized text. The text is then transformed into a functional representation at the sentence level. This representation is passed on to the semantic module which is responsible for the creation of predicate-argument structures from verb subcategorization information (mainly derived from the lexicon made available by the University of Pennsylvania) and semantic features associated with each predicate in a big dictionary (derived from WordNet and Corelex). Main arguments are turned into referential expressions to be filtered by the anaphora resolution module which implements a slightly modified version of the centering algorithm. In this way, pronominal and nominal expressions are co-referred to their antecedents. Systems for information extraction rely crucially on the availability of structural counterparts of semantic entities which constitute the pivoting elements of their recognition task. In particular, recognition tasks may be ranked for difficulty along the following lines:

1. named entity recognition,

2. canned template matching, and

3. generalized relevant information extraction and summarization.

Whereas the first two tasks above may be dealt with by resorting to a certain number of heuristics and a good list of named entities of the relevant domain, the third task is solely dependant on the solution of the basic problems of:

1. recognition of clausal structure,

2. recognition of arguments from adjuncts, and

3. recognition of predicate-argument structures.

It is a fact that these three tasks are ineludible prerequisites for any type of summary generation if one wants to summarize texts with unlimited vocabulary. It is a well established fact that shallow parsing does not ensure carrying out these structural tasks smoothly; it does so only with a certain level of approximation. Therefore, we use GETARUN's DM to check and compare semantic representations.

5.1 Using Automatically Generated Summaries for Essay Evaluation

One of the possible implementations of automatically generated summaries could be a task very similar to a multidocument summary generation: students are given a newspaper article which deals with a topic related to current local or international events, and they are told to write a summary on that topic by using information made available in the article. Since the summary has a length limitation which can be expressed in number of words, students will be obliged to use some summarization strategy. The task specification will also enable students to use as many words or sentences taken from the text as they deem sufficient to convey the most relevant facts.

Student summaries have been evaluated by comparing automatically generated summaries with ones produced by students. At first, the comparison procedure tries to gauge the relevance of the text from the percentage of shared concepts and from their order of presentation. The GETARUN program produces a DM of the input text and of the student's summary. The comparison is concerned with the semantic similarity between the two texts. Whenever a given concept is expressed with the same linguistic description, it is checked for its semantic interpretation. Semantic roles associated with this linguistic description, causal relations, and further inferential links with other concepts are analyzed in order to ascertain whether students have adequately understood the original text. All semantic relations are recovered from WordNet. According to the rate of overlapping information, a score is issued and then weighted. This produces a suitable means of evaluation.

We show here how the DM generated by GETARUN can be made to apply to the task at hand. The list of facts generated sentence by sentence is merged into a single list in which each entity is assigned a score according to whether it participated as main, secondary, or expected topic in the topic hierarchy. Every entity is listed with a semantic type, a semantic index, a score, and a list of facts. The result is the DM, part of which we show below. (T has been substituted for temporal index to improve readability).

(3) entity(ind,id3,30,facts([

fact(infon5, inst_of, [ind:id3, class:man], 1, univ, univ),

fact(infon6, name, [john, id3], 1, univ, univ),

fact(id5, go, [agent:id3, locat:id4], 1, T, id2),

fact(id8, sit, [actor:id3, locat:id7], 1, T, id2),

fact(id14, take_order, [agent:id13, goal:id3], 1, T, id2),

fact(infon64, poss, [john, id3, id19], 1, id1, id2),

fact(id20, read, [agent:id3, actor:id19], 1, T, id2),

fact(id22, begin, [actor:id3, prop:id20], 1, T, id2)])).

…

fact(infon29, part_of, [restaurant, id10, id4], 1, T, id2)])).

The entity with the highest topicality score is John with semantic identifier id3. Students have to produce a short summary which deals with John by mentioning explicit, and also possibly implicit, relations like the fact that John sat at a table and that he ordered something. In case students mistakenly take the waiter to be the most relevant participant in the story and write about the waiter reading the book we can easily gather that they did not understand the text.

Students can make use of synonyms, hypernyms, hyponyms, meronyms, holonyms, and other relevant semantic relations. However, we would like to stress the fact that here we are dealing with second language learners. Cohesion recovery can be accomplished by using one of the following four procedures:

1. pronominalization,

2. passivization with agent deletion,

3. relative clause formation, and

4. coordination and subject deletion.

All four procedures can be checked appropriately by the system. In particular, the system has been used with Italian students of English for Economics whose lexical knowledge is often very limited. As a matter of fact, students are told to use the original text as much as possible and to concentrate on reporting the most important facts and relations. The length of the summary must be less than 100 words. Our experiments with the system have given good results and we intend to make it fully automatic in the near future. At present, all decisions made by the system go through a screening phase during which a human tutor checks the automatically assigned scores.

6. CONCLUSIONS

The four exercises presented above have all gone through the preliminary experimental phase of software robustness testing in which an extended number of "crash" tests have been carried out in order to prevent the system from freezing or the web server from crashing. The results in terms of student reactions have so far demonstrated the validity of the system. The human tutors are currently working on improving and extending the gamut of feedback messages to be produced and presented to users. As to exercises themselves, we find that those bound to parsing performance and lexical information are well suited to their task, in particular because the architecture required is very simple: both parsing and information refer to a limited domain and written production. However, the exercises based on text understanding and summarization have by far larger importance: the first one has spoken input and the second one uses free text as input, even though semantic updating may take place before the system is actually applied to a text chosen by the human tutor. We are thinking of spoken interaction in the text understanding exercise by introducing a talking head who will be in charge of entertaining students with more extended dialogue exchanges. This will require using the automatic speech recognition module, called SLIM, currently available on the main system for self-instructional second language learning (see Delmonte et al., 1996; Delmonte (2000d).