In this paper we present the modeling strategies that were applied by the IBM T.J. Watson research team to the modality classi cation and case-based retrieval tasks of ImageCLEF 2012. The primary challenges of this year's medical modality classi cation task were as follows: 1) the supplied training data was extremely limited, with some categories having as few as 5 positive examples, leaving little room for internal testing, and 2) some modalities appeared to be visually similar. In order to address these challenges, we approached the task from two fronts: 1) we attempted to augment the training data with additional examples of each category, and 2) we experimented with a broad range of modeling strategies and feature extraction techniques. For the case based retrieval task, we employed a semantic similarity approach to measure the relatedness among medical concepts found in the text corpus. We believe the lack of using additional lexical database besides the UMLS-methathesaurus led to poor performance in relation to other approaches.
The ImageCLEF 2012 Medical Modality Classi cation Task is a standardized benchmark for systems to automatically classify medical image modality from PubMed journal articles. The 2012 dataset has changed from the previous year in 3 signi cant ways: 1) there are more categories, 2) the number of training examples is far fewer, and 3) some modalities are more similar.
Our approach can be described as scaling up to utilize as many features and data as possible. Our experiments demonstrate that increasing either axes tends to boost performance. In addition, we present a method for kernel approximation to help address the computational time costs of using a wide variety of methods.
For data augmentation, we drew from several sources outside the
ImageCLEF2012 collection, such as a Bing web-crawl for each category, as well as
publicly available medical image datasets, such as The Cancer Imaging Archives
(TCIA), and Image Retrieval in Medical Applications (IRMA). For our
modeling approaches, we selected multiple features extracted from a set of image
granularities, such as SIFT variants [
Modality Classi cation Task Our experiments are performed on the following datasets:
Dataset 1: The original ImageCLEF2012 training dataset.
Dataset 2: A dataset augmented with up to 100 additional examples per
category. Augmenting data was collected from Bing Image Search, a
Cornell University Vision and Image Analysis Group & International Early
Lung Cancer Action Program (VIA/I-ELCAP) Public CT datase1, The
Cancer Imaging Archives (TCIA)2, Image Retrieval in Medical Applications
(IRMA)3, and the Japanese Society of Radological Technology (JSRT) [
Due to the low number of positive examples in some categories in the original training dataset, we chose to construct an additional augmented dataset. The number of examples per category for both is shown in Fig. 1. 2.2
Feature Collections All our experiments are run using 1 of 7 sets of low-level visual features. Here we name and describe the contents of 7 sets of features that were used for modeling. Each feature is described by name, with the granularity of extraction in parenthesis. The granularities are as follows:
Global: Feature extracted from entire image. Native feature dimensionality preserved.
Grid: 5x5 image grid, with feature vector extracted from each grid block and concatenated. Increases dimensionality by factor of 25.
Grid7: 7x7 image grid, with feature vector extracted from each grid block and concatenated. Increases dimensionality by factor of 49.
Layout: 5 image regions including the center and the 4 quarters. Increases dimensionaltiy by a facor of 5.
Pyramid: Spatial pyramid, with global as rst level, and 2x2 image grid as second level. Increases dimensionaltiy by a facor of 5.
The feature sets referenced later in the section are as follows: Feature Set 1 Color Correlogram (grid), Edge Histogram (grid), Image Type (grid), LBP histogram (grid7), Color SIFT AM Codebook Size 2000 (pyramid), SIFT AM Codebook Size 2000 (pyramid), HSV SIFT AM Codebook Size 1000 (pyramid), Image Stats (grid), Gist (layout), Curvelet Texture (layout).
Feature Set 2 Feature Set 1, removing SIFT features, and adding the following: Color Histogram (grid), Color Moments (grid), Dominant Colors (global), Thumbnail Vector (global), Color SIFT AM Codebook Size 1000 (pyramid), SIFT AM Codebook Size 1000 (pyramid), FourierOrientationVector (grid). FourierOrientationVector is a feature representing the average of diameters in Fourier-Mellin space, across varying angles from 0 to 180 degrees.
Feature Set 3: Feature Set 2, adding FourierPolarPyramid (layout). FourierPolarPyramid is a pyramid constructed in polar coordinates of FourierMellin space. 4 radial levels are employed (partitions of size 1, 2, 4, and 8), with 6 angular levels, across 4 color channels (RGB and Grayscale). Feature Set 4: Color Correlogram (grid), Color Histogram (grid), Edge Histogram (layout), Edge Histogram (grid), Gist (layout), FourierPolarPyramid (global), FourierPolarPyramid (layout), Image Type (grid), LBP Histogram (grid7), SIFT Codebook Size 1000 (global),
Feature Set 5: Feature Set 2, minus all SIFT variants. Feature Set 6: Image Stats (grid), LBP Histogram (grid), Image Type (grid), Edge Histogram (grid), Shape Moments (grid), Dominant Colors (grid), image stats (global), LBP histogram (global), Image Type (global), Shape Moments (global), Edge Histogram (global), Color Wavelet (global), Dominant Colors (global), Color Moments (global), Color Correlogram (global), Color Moments (global), Gist (global), Wavelet Texture (global), Tamura Texture (grid).
Feature Set 7: SIFT Codebook Size 1000 (pyramid), HSV SIFT AM Codebook Size 1000 (pyramid). 2.3
Multiclass SVM
We employed the LibSVM library [
K(x; y) = 1 yd)2
; X (xd d 12 (xd + yd) (1)
Three types of feature fusion methods were experimented: early, late, and kernel fusion.
Early fusion: consists of a concatenation of di erent descriptors, before SVM modeling Kernel Fusion: consists of a point-wise pooling (max or average operator) over the kernel matrices produced by each descriptor. The Multiclass SVM is then learned on top of the aggregate matrix Late Fusion: consists of a pooling (max, average or product) operator over the predictions of the models learned from individual features for each test image. For this type of fusion we employed the probabilistic output option in each SVM, which converts the 1-vs-1 comparisons into class probabilities. For each test image, each model produced a vector with N probabilities (where N is the number of classes, 31 in our case). After the pooling was applied in a point-wise manner over the prediction vectors of the models, the class with the maximum aggregate probability was chosen as the nal prediction.
Each strategy is exempli ed in Figure 2. As reported in Section 2.6, the Multiclass SVM trained from the augmented dataset with early fusion strategy (Experiment 12) provided the best performance. Kernel fusion proved to be equivalent, while late fusion performed worse than the other methods. To explore di erent aspects of visual phenomenon, we employed 19 di erent features, described in Feature Set 5. We used an early fusion strategy by concatenating these features together and training a kernelized Supporting Vector Machine (SVM). However, a practical problem of using so many features lies in the computational cost, both in the training and testing stage. When the number of images grows, or when the feature dimension increases, traditional SVM solvers may not work well or take a very long time to compute the optimal solution.
Among all the kernels in practice, the Chi-square kernel often yields very good performance compared with the others. Moreover, a large amount of our features, including LBP histogram, edge histogram, color histogram, and SIFT histogram, are in the form of histogram features. Chi-square kernel is arguable regarded as the rst choice for histogram form features. In our work, we focus on how to e ciently solve Chi-square kernel only. We do not consider the problem of general kernels. We consider the Chi-square kernel in the form of
K(x; y) = X
d xd + yd where x = [x1; x2; ; xd; , y = [y1; y2; ; yd; .
It is easy to see that Eq.(2) is de ned as the additive sum of di erent
dimensions. Such a kernel is referred to as an additive kernel. As suggested by [
N f (x) = X K(x; xi);
i=1 where i denotes the index of training samples. For any positive de nite kernel, there exists a mapping x ! (x) so that the nal classi cation model becomes f (x) = wT (x) + b where w denotes the weights of the linear model in the mapped space. In this work, we will use Nystrom's approximation to construct the mapping function explicitly.
To make the representation simply we let then we can see the kernel is k(x; y) =
xd + yd K(x; y) = X k(xd; yd): d Next we will discuss how to approximate k(x; y), which is a function on 1D space.
To approximate k(x; y), we employ 8 p 0
if j = 0 j(x) = <>> q2 j+1 cos( j+21 Lx) if j > 0 odd
2
>:> q2 2j sin( 2j Lx) if j > 0 even
where j and j constitute one pair of Fourier transform, L is the frequency
parameter, and we use L = 2 =15 in practice. Then we can convert the nonlinear
kernels with the linear model over j(x). For more details, please refer to [
So far we have discussed how to approximate the kernelized SVM using a
linear model. Now we can compare the computational complexity of both
methods. Suppose we have m features, 1 m M , and each feature is of dimension
dm. The number of training samples is N , and size of testing set is T . For each
(2)
(3)
(4)
dm features, we map it to the space of dimension 7dm. Note that the evaluation
of kernel SVM depends on the number of support vectors, which in practice is
proportional to the number of training examples. Also our linear approximation
requires the extra cost of feature mapping, which is 7dN for training and 7dT
for testing. Table 1 compares the computational complexity of the two methods.
It is easy to see our linear approximation is much more e cient in both training
and testing stage. Our linear approximation is even plausible for the scenario
with a lot of features.
To measure the e ectiveness of our kernel approximation method, we
compare how much di erence exists between Chi-square kernels and our
approximated kernels. Table 2 illustrates the speed up and percentage of kernel
approximation error using randomly-generated features. It is easy to see the
approximation error is low, while the speed up will be increasingly signi cant when the
number of training samples grows.
It is also interesting to see the classi cation accuracy after our kernel
approximation. We implement the Chi-square kernel with LibSVM, and also use
liblinear [
One-vs-All Ensemble SVM with Data Sampling
IBM Multimedia Analytics and Retrieval System (IMARS) [
Using the IMARS learning paradigm, we explored several variants of the pipeline to better understand the contribution of each to system performance: Feature Fusion: Early (vector concatenation) or Late (Unit Model score averaging).
Data Sampling: Random subsamples of negative examples, or using the entire dataset.
Number of Bags: Changing the number of Unit Models that are trained for a particular feature by choosing di erent subsamplings of example data. Feature Sets: Varying sets of features used for modeling.
Kernel Type: A single RBF kernel with kernel parameter -4, C=100, and sigmoid feature normalization was used for most model learning; however, we performed one experiment with a Chi2 kernel, similar parameters, to understand any e ect the variation of kernels might have.
1-vs-All scores of multiple Ensemble Models were converted to Multiclass labels by choosing the max over all the classi er scores. One-vs-All Ensemble SVM with Data Sampling 1-vs-ALL experiments are depicted in Table 3. Experiment index number, feature fusion type (Early or Late), number of examples for each of positive and negative categories per bag, number of bags across data, number of bags across features, the feature set used, the average dimensionality across feature bags, the proportion of data used for Validation Split (VS), multiclass accuracy scores, and relative performance scaled by computational complexity (P/C) are shown. Computational complexity is computed simply as the running time required to compute a kernel matrix.
Experiment 8 was reproduced using a Chi2 kernel, yielding MACC of 64.4%, and was not listed in this table.
In the rst experiment, we established a baseline with a very small data sampling rate (100 examples in each of positive and negative) and only two SIFT features utilized. In the second experiment, we examined the performance of our other features, excluding SIFT. In the third, we used both sets, and in the fourth we added the newer FourierPolarPyramid feature vector. In the fth experiment, we examined the e ect of using late fusion, instead of early fusion. In the sixth experiment, we began to study the e ects of increasing the number of examplars. In the seventh and eigth experiments, we examined the e ect of increasing data sampling either by using larger data bag sizes, or a larger number of bags. The ninth experiment represented our submission NCFC ORIG 2 EXTERNAL SUBMIT.txt; this dataset used a restricted number of features and late fusion, due to time constraints. In the last two experiments, we nally examine the e ects of using larger amounts of data, up to the limit of our dataset.
In summary, our experiments yield a number of notable observations: 1. With early fusion, adding more features improves performance, SIFT contributing the most (see Exp. 1-4). 2. Adding additional data improves performance (Exp. 4, 6-11) . 3. Early fusion of features outperforms late fusion with averaging, and provides a better P/C ratio (Exp. 4-5). 4. Bagging along the data dimension reduces overall performance, but improves
P/C (Exp. 7-8). 5. Best performance is acheived using early fusion of all features and all data (Exp. 11). 6. Chi2 kernels and searching over SVM parameters holds the potential to boost performance further.
Multiclass SVM Multiclass SVM experiments are depicted in Table 4. Three di erent aspects were explored in the experiments: fusion type, dataset size, and aggregation type. From the results in the Table emerges that: 1. Early and kernel fusion are comparable, and perform better than late fusion 2. a larger training set leads to a better classi cation performance (Dataset 2 is better than Dataset 1) 3. Averaging seems to be the best aggregation strategy. Exp. Fusion Aggregation Feature Set Dataset Mean ACC 12 13 14 15 16 17 18 19 20 21
Early Early Kernel Kernel
Late Late Late Late Late Late Avg Avg Avg Prod Max Avg Prod Max 2 1 2 1 2 2 2 1 1 1 2 1 2 1 2 2 2 1 1 1 In Figure 5 are reported the o cial runs submitted to the ImageCLEF 2012 website, in comparison to all other o cial submissions (43 in total). IBM achieved the top three visual only classi cation performances, as well as the best overall accuracy.
The submissions were all purely visual, and corresponded to the following experiments (in decreasing order of performance): 12, 13 with Kernel approximation fusion (as described in Section 2.4), 13, 11, 12 with Kernel approximation fusion, 18, 21. After the submissions we further improved the worst performing ones through better normalization, parameter selection, and further debugging, yielding to the performances reported in Tables 3 and 4.
Fig. 6(b) shows the confusion matrix of the best performing run. Overall the matrix presents a strong diagonal. However, some clear mis-classi cations are evident. In particular, \GSYS - System overview" resulted to be the hardest class to categorize, being quite often confused with \GFLO - Flowcharts". Looking at the appearance of the images in such classes, it is evident that based on visual features alone they are in most cases indistinguishable. This confusion might be mitigated by exploiting the textual information associated with, or in, the images. We plan to follow this direction in future experiments.
We expect that extracting textual information and combining it with our strong visual modeling will boost classi cation performance, given the complementary information of those two representations, and also looking at the performances of other groups.
In conclusion, appropriately modeling the visual appearance can provide strong modality classi cation performance, even without text analysis. In our experiments we found that adding more features and training data lead to models with better classi cation performance. Early fusion and kernel fusion seem to be the best combination strategies. Our kernel approximation provides a principled and e cient framework to perform such fusion, while signi cantly increasing the e ciency of the computation of the best performing CHI2 kernel. In this section, we give an overview of the application of our methods to casebased medical image retrieval and present the results of our submitted runs. Techniques used for case-based retrieval task are mainly based on methods from Information Retrieval (IR) and Natural Language processing (NLP), including rule-based and machine-learning techniques. In order to facilitate the classi cation of a large dataset and to retrieve the most relevant documents for a given query, an IR system applies various NLP methods to construct a semantic view of each document indexed via relational database or text index. This semantic view is summarized by a set of relevant keywords (i.e., index terms) as a signature of this document.
In the biomedical domain, the terminology is very important because the words used in the document are related to medical terms that can refer to the same concept with di erent semantic interpretation (i.e., senses) based on the textual context. In addition to the NLP techniques for reducing the size of the relevant keywords by eliminating stopwords and stemming words, our system also applies semantic similarity methods to improve the understanding of textual terms and remedy potential ambiguity among medical concepts. The focus of the semantic similarity is to nd the strength of the semantic relatedness or the semantic connections between textual terms. The taxonomic proximity between terms measures the degree of overlapping between contextual word vectors using Information Content (IC) based measures. To reduce computational complexity, the semantic relatedness is applied within an ordered window to nd relevant terms between adjacent terms in the document. To build our retrieval framework based on the approaches we described above, we use the YTEX (Yale cTAKES extensions) system for computing the semantic IC-based measures and the cTAKES (clinical Text Analysis and Knowledge Extraction) as a NLP system based on the Unstructured Information Management Architecture (UIMA) that combines rule-based and machine-learning. The cTAKES system uses the OpenNLP Maximum Entropy package for sentence detection, tokenization (words), part-of-speech (POS) tagging. It performs the name entity recognition of biomedical from the Uni ed Medical Language system (UMLS) Metathesaurus, and other biomedical source such as Systematized Nomenclature of Medicine, Clinical Terms (SNOMED CT).
To classify the medical articles, our system used the YTEX semantic similarity to identify and disambiguate medical terms before storing the annotations on the documents in the relational database, and indexing relevant medical concepts that can facilitate the topic case query matching. For each case-based query, we rst executed the NLP pipeline to extract relevant medical concepts and generate an SQL expression by combining the concepts using logical OR operator (meaning all of the concepts to be optional). To limit the number of query results and select the most relevant annotations, we de ne the weight measures for sorting and ranking them based on the cosine distance between medical concept vectors. Fig. 7 describes the processing ow of the system. The data processing splits the whole article le into multiple individual les in order to distribute them across multiple nodes. Each article is stored in the database as an annotation including its most relevant medical concepts. The case-based NLP pipeline processes each case-based le to nd relevant medical concepts. Finally, the search engine composes a SQL logical expression and ranks the result set retrieved from the annotation database.
Due to time constraint, we only submitted one run for case-based retrieval task, shown in Table 5. First, we experimented with the semantic similarity approach, and found good correlation among medical concepts within the text corpus with appropriate senses. However, by matching only the medical concepts, the results are not as good as could be if we had used additional lexical databases. 3.4
Conclusion The IC-based measures applied to adjacent words in a de ned text window improves the semantic relatedness performance and is less expensive than computing all the word-pairs in the corpus. However, we also observed low system performance when the SQL expressions are complex and the number of concepts is high. In the future, we would like to improve the semantic similarity methods by incorporating the medical concepts with the lexical semantic analysis. We also want to have a better matching measures to improve the accuracy.