Automatic video tagging systems are targeted at assigning semantic concepts (“tags”) to videos by linking textual descriptions with the audio-visual video content. To train such systems, we investigate online video from portals such as YouTubeTMas a large-scale, freely available knowledge source. Tags provided by video owners serve as weak annotations indicating that a target concept appears in a video, but not when it appears. This situation resembles the multiple instance learning (MIL) scenario, in which classifiers are trained on labeled bags (videos) of unlabeled samples (the frames of a video). We study MIL in quantitative experiments on real-world online videos. Our key findings are: (1) conventional MIL tends to neglect valuable information in the training data and thus performs poorly. (2) By relaxing the MIL assumption, a tagging system can be built that performs comparable or better than its supervised counterpart. (3) Improvements by MIL are minor compared to a kernel-based model we proposed recently [13].
Content-based video retrieval has recently attracted growing interest by research and industry, which is triggered by the enormous amount of digital video being generated and published world-wide. While efficient methods for data acquisition and storage exist, finding useful information within the sheer plethora of content remains a challenge.
The most successful and comfortable search strategy from a user perspective remains the text-based search allowing users to “google” inside a database. Conventionally, this approach demands a previous manual annotation of content, which is time-consuming, expensive and simply not possible in many situations. To overcome this problem, automatic video tagging has been investigated (the task is alternatively referred to as “concept detection” or “high-level feature extraction”), which aims at building computer systems that detect semantic concepts in video data by analyzing its audio-visual content. This way, a text-based index can be created automatically.
To realize such a computer-based tagging, machine learning techniques are used that analyze correlations between the audio-visual content of a video and textual keywords associated with it. This requires training sets of annotated videos, which must be large-scale due to the high number and visual complexity of concepts. The cost associated with the manual acquisition of such large training sets poses a key burden for the practical use of concept detection systems. (a) (b)
To overcome the lack of annotated training data, we have recently proposed to train
tagging systems on online video [
On the downside, online video as training data is of a significantly lower quality than conventional datasets, which are labeled according to precise visual criteria (assessors are given instructions like “find shots that take place outdoors at night, but no sporting events under lights” [TRECVID 2008] ). In contrast to this, tags at portals like YouTubeTMare often given with an intention that links the tag only indirectly to the visual content. Further, online videos come with tags for the whole video that do not tell us when in a video a target concept appears. Overall, online video clips contain relevant content as well as irrelevant parts. This phenomenon is illustrated in Figure 1, which shows key frames from clips tagged with the concept “airplane”: some relevant frames do in fact show airplanes, while other irrelevant ones are not visually related to the target concept at all.
Obviously, training a video tagger on all (including non-relevant) content can lead to significant performance loss. This issue is addressed here by using multiple instance learning (MIL). In contrast to standard supervised learning – which is targeted at classifying single samples – MIL aims at classifying bags of samples (which correspond to videos in our case), whereas latent positive samples in the bag (here: relevant frames) cause it to be labeled positive regardless of the presence of negative samples (irrelevant frames). Training is performed on labeled bags of unlabeled samples.
We study two MIL models of varying strictness in quantitative experiments on
realworld online videos. Our contributions are: (1) to our knowledge the first study applying
MIL to video tagging, (2) a modification of the MIL-BPNET [
To the best of our knowledge, video annotation on weakly labeled videos has not been
studied except for prior work we presented in [
Research on video tagging in general is concentrated in the TRECVID campaign3,
an open metrics-based evaluation that provides researchers with common datasets,
evaluations, and a forum for discussion [
For learning from weakly labeled training data, several models have been
studied in the context of image annotation. Here, ground truth labels are usually given on
image level and no region-wise annotations are provided. Ku¨ck et al. [
Research on multiple instance learning has been started by Dietterich et al. [
Given an input video X and a target concept, a tagging system estimates P (T |X),
where T is a Boolean random variable with T = 1 iff. the target concept is present
in X. X is viewed as a “bag” of representative “key frames” associated with feature
vectors x1, .., xn ∈ Rd. To infer P (T |X), a classifier Φ : 2Rd → [
To construct Φ, the system is trained on a set of videos X1, .., XN . Again, each Xj is a bag of key frame-related features xj1, .., xjnj . We assume that training videos are weakly labeled, i.e. the associated concept presence variables Tj are observed, but we do not know which key frames of a video are “critical”, i.e. visually related to the target concept. 3 http://www-nlpir.nist.gov/projects/t01v/
In the following, we discuss multiple instance learning in the context of weakly
labeled videos. Two formulations corresponding to different assumptions on the
relevance of training data are given: (1) the multiple-instance neural network MIL-BPNET
(which has been presented in [
This section briefly discusses the MIL-BPNET approach from [
Classification works by feeding all samples xi to the network, obtaining scores
φ(xi) ∈ [
P (T |X) ≈ Φ(X) := max φ(xi) i=1,..,n
Correspondingly, training minimizes classification error on the training set of bags X1, .., XN with relevance labels T1, .., TN ∈ {0, 1}, whereas only the critical sample in each bag is taken into account:
E =
N j=1
max φ(xjk) − Tj k=1,..,nj 2 This energy function is minimized in a procedure similar to backpropagation: samples are iteratively fed to the network, and for each bag Xj = {x1, .., xnj } the “critical sample” is determined as arg maxk=1,..,nj φ(xjk). Then, the network weights are updated with respect to the critical samples previously identified. 4.2
The strict multiple instance learning setup outlined in Section 4.1 is very restrictive in a sense that it assumes a single critical sample per bag. This neglects valuable information in the training data if multiple relevant samples per bag exist. In our video-related setup it is fair to assume that videos contain more than a single key frame related to the target concept, which is why we relax the multiple instance learning condition.
The basic idea is to assume a known fraction α ∈ [
Sα(X) = { xi | φ(xi) ≥ Q1−α[φ(X)] } where Q1−α[φ(X)] is the empirical (1−α)-quantile of the MLP scores φ(x1), .., φ(xn). For example, we might assume that α = 70 % of key frames sampled from each “basketball” video are in fact visually related to the concept, and assume that these are the ones with the highest MLP scores φ(.).
The parameter α is unknown and can vary between videos and between concepts.
In the current setting, we assume that it is learnable using a validation set, and that no
variation between videos of a concept takes place (a more sophisticated way would be
to introduce a prior for α similar to topic priors in topic models [
Classification is again based on the assumption that a fraction α of samples in the bag is positive. Their scores are averaged: Training is also similar to the multiple instance version. Iteratively, critical samples are estimated and used for updating the network. Again, instead of a single critical sample per bag, a fraction of samples Sα(X) is estimated and used for updating the network weights in order to minimize the following energy function:
E =
(φ(x) − Tj )2 j x∈Sα(Xj)
Let us briefly discuss the behavior of the model for extreme choices of the “critical fraction” α: if α → 0, only the single sample with the highest score is considered critical, i.e. the model corresponds to the MIL model outlined in Section 4.1. For α → 1, the model becomes fully supervised: all samples are considered relevant, and bag classification is done using a sum rule fusion over all samples in the bag. 5
In the following experiments on a dataset of real-world online videos it is studied
whether multiple instance learning can make video taggers more robust to irrelevant
training content. First, the dataset and experimental protocol are outlined. After this,
we study whether strict MIL (Section 4.1) leads to performance improvements
compared to a conventional supervised setup. Third, the relaxed MIL model introduced in
Section 4.2 is tested. Finally, the results are compared to the generative weakly
supervised approach introduced in [
We test our framework on the youtube-22concepts dataset of real-world online videos
downloaded from the portal YouTubeTM. The dataset consists of 2200 videos (about
194 hrs.) and has been made available for research purposes4. It contains 100 clips
for each of 22 semantic concepts that include locations (e.g., “desert”, “beach”),
actions (e.g., “hiking”, “interview”), objects (e.g., “cat”, “eiffeltower”), and sports (e.g.,
“swimming”, “soccer”). Tests were run for 5 concepts: the sports “basketball”, “golf”,
“soccer”, and “swimming”, as well as the tag “desert”. Our motivation for the sports
4
http://sites.google.com/a/iupr.com/iupr-image-and-video-computing/youtube-22-conceptsdataset
candidates is that good tagging performance has been achieved even with simple
features in previous experiments, which makes them good candidates for studying the
influence of multiple instance learning. “desert” is a more challenging tag, for which
weakly supervised learning similar to MIL has previously been demonstrated to give
good results [
The dataset was split into a training set of 66 % and a test set of 33 % using
stratified sampling. Key frames were extracted using a shot boundary detection and
intrashot clustering of frames [
The parameters for neural network training were set to 5 hidden units, a fixed backpropagation learning rate (0.5) and 100 training epochs. In previous test, results were found rather insensitive with respect to these parameters. Since results vary with the initialization of backpropagation, the median results over multiple runs are presented.
To measure performance for each concept, test videos are sorted by their score P (T |X), obtaining a ranked retrieval list. By thresholding this list at different positions, a recall-precision curve is obtained, and the average precision AP (which corresponds to the area under the curve) is used as a performance measure. 5.2
We first evaluate multiple instance learning as discussed in Section 4.1. As a baseline serves the fully supervised MLP, which uses all key frames for training (including the ones not visually related to the target concept). Note that another interesting benchmark would be training on relevant key frames, but this is thus omitted here due to the time and cost associated with manual ground truth annotation.
Figure 2 gives the median results over 7 backpropagation restarts for both methods.
For all concepts tested, multiple instance learning is significantly outperformed and
gives poor results. An explanation for this is also given in Figure 2: for a “basketball”
training clip, the 5 samples are plotted for which the MIL classifier gives the highest
scores at the end of training. Under each image, the corresponding score can be found.
Obviously, the system has overfitted to a few examples it assumes to be critical. The rest
of the bag – though it contains a significant amount of basketball content – is neglected
in training and thus given incorrect low scores. Similar observations have been made by
Ray and Craven [
Table 1 gives the median performance for both methods. Relaxed MIL outperforms
strict MIL significantly and gives performance improvements over the supervised case
for three of five concepts (4.9 % for “basketball”, 2.8 % for “desert”, and 3.5 for “golf”).
For “soccer” and “swimming”, the standard supervised setup performs comparably.
We also compare MIL to another system following the idea of modelling irrelevant
training video content. This “kernel-based relevance modelling” (KRM) approach was
introduced in [
It can be seen in Table 1 that KRM tends to benefit more from modelling irrelevant content. For all concepts, an improvement compared to the fully supervised case is achieved that can reach up to 17.2 % (desert). Due to this fact, KRM outperforms both MIL and the supervised system on all concepts. 6
We have addressed the challenge of visual learning from weakly labeled videos with
the practical motivation of training automatic video tagging systems on online video
content. To achieve such weakly supervised learning, a relaxed formulation of MIL was
suggested as a modification of the MIL-BPNET algorithm [
In quantitative experiments using on a dataset of real-world online videos, the
following key observations have been made: (1) While strict MIL was significantly
outperformed, relaxed MIL gave moderate performance improvements compared to a
supervised system. (2) The benefits of multiple instance learning are lower than for a
kernelbased model we have introduced recently [
Finally, we point to the annotations of web videos as another information pool of potential interest. In a video search framework, this information might help to link queries with concepts or concepts with detectors. While we have focused on the visual aspect of concept detection in this paper, we believe that video concept detection and search could benefit from a joint learning on textual descriptions and content5.