The raw data samples in DevSetLabel.tsv is organized as below: 

DevSetLabel.tsv Statistics:

Target Label Data (Annotations for Negative Bootstrap) Structure: 

concepts<TrainSet>.txt [File]:

Concept#.txt [File]:

<TestSet>.txt [File]:

Mapping Data

Obtain Training & Testing Sets

For each concept, find related images;

Divide those images into positive and negative samples with respect to annotations;

Divide positive and negative samples into two non-overlapped subsets, respectively, one for training and the other for testing. 

Other Issues

Select concepts of which the number of labeled examples is greater than or equal to a certain minimal (e.g. 100).

Set the proportions of training and testing samples (e.g. 50/50).

Use the ‘collect-unique-sort’ approach to obtain ‘ImageSets’ files.

Simulation Results

--

MATLAB Code (MATLAB R2013a)

close all; clear all; tic; fprintf('-->> Set parameters... '); % Set properties MinQSize=100; Desc=num2str(MinQSize); Proportion=0.5; rng('default'); % Set paths and file names Root='VisualSearch'; TrainCollec='msr2013devtrain'; TestCollec='msr2013devval'; TrainDir=fullfile(Root,TrainCollec); TestDir=fullfile(Root,TestCollec); % Set 'Annotations' directories TrainAnnoDir=fullfile(TrainDir,'Annotations'); TestAnnoDir=fullfile(TestDir,'Annotations'); TrainAnnoName=strcat(TrainCollec,Desc); TestAnnoName=strcat(TestCollec,Desc); TrainConceptName=strcat('concepts',TrainAnnoName,'.txt'); TestConceptName=strcat('concepts',TestAnnoName,'.txt'); TrainConceptFile=fullfile(TrainAnnoDir,TrainConceptName); TestConceptFile=fullfile(TestAnnoDir,TestConceptName); TrainConceptDir=fullfile(TrainAnnoDir,'Image',TrainConceptName); TestConceptDir=fullfile(TestAnnoDir,'Image',TestConceptName); % Set 'ImageSets' directory TestImageSetDir=fullfile(TestDir,'ImageSets'); TestImageSetName=strcat(TestCollec,Desc,'.txt'); TestImageSetFile=fullfile(TestImageSetDir,TestImageSetName); fprintf('Done!\n     '); toc; % Import raw data tic; fprintf('-->> Import raw data... '); Filename='DevSetLabel.tsv'; [Query,Image,Rate]=importfile(Filename); clear Filename fprintf('Done!\n     '); toc; % Select queries with number of samples >= 'MinQSize' tic; fprintf('-->> Select queries with number of samples >= ''MinQSize''... '); [QIndex,~,QLevels]=grp2idx(Query); NQueries=length(QLevels); QSize=hist(QIndex,1:NQueries); SelecQIndex=find(ismember(QIndex,find(QSize>=MinQSize))); for i=1:NQueries     % Rename <Query> as <Concept#> to avoid weird file names     QLevels{i}=strcat('Concept',num2str(i)); end Query=QLevels(QIndex); clear QIndex QLevels NQueries QSize i Query=Query(SelecQIndex); Image=Image(SelecQIndex); Rate=Rate(SelecQIndex); clear SelecQIndex for i=1:length(Image)     % Clear 'img' prefix     Image{i}(1:3)=[]; end clear i fprintf('Done!\n     '); toc; % Obtain annotations tic; fprintf('-->> Obtain annotations... '); Anno=strcmp('Excellent',Rate)+strcmp('Good',Rate)...     -strcmp('Bad',Rate); clear Rate fprintf('Done!\n     '); toc; % Obtain 'Annotations' tic; fprintf('-->> Obtain ''Annotations''...\n'); if exist(TrainConceptFile,'file')     delete(TrainConceptFile); end if exist(TestConceptFile,'file')     delete(TestConceptFile); end if exist(TrainConceptDir,'dir')     rmdir(TrainConceptDir,'s'); end if exist(TestConceptDir,'dir')     rmdir(TestConceptDir,'s'); end [QIndex,QNames,QLevels]=grp2idx(Query); NQueries=length(QLevels); for i=1:NQueries     iQuery=QNames{i};     iImage=Image(QIndex==i);     iAnno=Anno(QIndex==i);     % Write 'concepts(...).txt' file     fprintf('---> Write ''');     fprintf(iQuery);     fprintf(''' to ''');     fprintf(TrainConceptName);     fprintf('''... ');     if ~exist(TrainAnnoDir,'dir')         mkdir(TrainAnnoDir);     end     FID=fopen(TrainConceptFile,'a');     fprintf(FID,'%s\n',iQuery);     fclose(FID);     fprintf('Done!\n');     fprintf('---> Write ''');     fprintf(iQuery);     fprintf(''' to ''');     fprintf(TestConceptName);     fprintf('''... ');     if ~exist(TestAnnoDir,'dir')         mkdir(TestAnnoDir);     end     FID=fopen(TestConceptFile,'a');     fprintf(FID,'%s\n',iQuery);     fclose(FID);     fprintf('Done!\n');     % Divide positve samples     PosiIndex=find(iAnno==1);     NPosi=length(PosiIndex);     TrainPosiIndex=PosiIndex(randsample(NPosi,round(NPosi*Proportion)));     TestPosiIndex=setdiff(PosiIndex,TrainPosiIndex);     % Write positive samples to '(Concept#).txt' file     fprintf('---> Write positive samples to ''');     fprintf(strcat(iQuery,'.txt'));     fprintf('''... ');     if ~exist(TrainConceptDir,'dir')         mkdir(TrainConceptDir);     end     FID=fopen(fullfile(TrainConceptDir,strcat(iQuery,'.txt')),'a');     Temp=[iImage(TrainPosiIndex),num2cell(iAnno(TrainPosiIndex))]';     fprintf(FID,'%s %d\n',Temp{:});     fclose(FID);     fprintf('Done!\n');     fprintf('---> Write positive samples to ''');     fprintf(strcat(iQuery,'.txt'));     fprintf('''... ');     if ~exist(TestConceptDir,'dir')         mkdir(TestConceptDir);     end     FID=fopen(fullfile(TestConceptDir,strcat(iQuery,'.txt')),'a');     Temp=[iImage(TestPosiIndex),num2cell(iAnno(TestPosiIndex))]';     fprintf(FID,'%s %d\n',Temp{:});     fclose(FID);     fprintf('Done!\n');     % Divide negative samples     NegaIndex=find(iAnno==-1);     NNega=length(NegaIndex);     TrainNegaIndex=NegaIndex(randsample(NNega,round(NNega*Proportion)));     TestNegaIndex=setdiff(NegaIndex,TrainNegaIndex);     % Write negative samples to '(Concept#).txt' file     fprintf('---> Write negative samples to ''');     fprintf(strcat(iQuery,'.txt'));     fprintf('''... ');     if ~exist(TrainConceptDir,'dir')         mkdir(TrainConceptDir);     end     FID=fopen(fullfile(TrainConceptDir,strcat(iQuery,'.txt')),'a');     Temp=[iImage(TrainNegaIndex),num2cell(iAnno(TrainNegaIndex))]';     fprintf(FID,'%s %d\n',Temp{:});     fclose(FID);     fprintf('Done!\n');     fprintf('---> Write negative samples to ''');     fprintf(strcat(iQuery,'.txt'));     fprintf('''... ');     if ~exist(TestConceptDir,'dir')         mkdir(TestConceptDir);     end     FID=fopen(fullfile(TestConceptDir,strcat(iQuery,'.txt')),'a');     Temp=[iImage(TestNegaIndex),num2cell(iAnno(TestNegaIndex))]';     fprintf(FID,'%s %d\n',Temp{:});     fclose(FID);     fprintf('Done!\n');     % Write test image label log     FID=fopen('TestImage.tmp','a');     fprintf(FID,'%s\n',iImage{[TestPosiIndex;TestNegaIndex]});     fclose(FID); end fprintf('     '); toc; % Obtain 'ImageSets' tic; fprintf('-->> Obtain ''ImageSets''...\n'); TestImage=sort(unique(importtestimage('TestImage.tmp'))); delete('TestImage.tmp'); if exist(TestImageSetFile,'file')     delete(TestImageSetFile); end fprintf('---> Write image labels to '''); fprintf(TestImageSetName); fprintf('''... '); if ~exist(TestImageSetDir,'dir')     mkdir(TestImageSetDir); end FID=fopen(TestImageSetFile,'a'); fprintf(FID,'%d\n',TestImage); fclose(FID); fprintf('Done!\n'); fprintf('     '); toc; % Mission accomplished fprintf('-->> Mission accomplished!\n'); beep();

--

References

MSR-Bing Image Retrieval Challenge Datasets: http://web-ngram.research.microsoft.com/GrandChallenge/Datasets.aspx

Training:

Step 1: Remove meaningless words like “image”, “image of”, “images”, “images of”, etc. in all clicked queries, and aggregate the query counts on these queries to the same ones but without these words.

Step 2: Label propagation on training set. Propagate queries/labels to their duplicate and near duplicate images.

Step 3: For each unique query, find all the clicked images, ordered by click counts.

Step 4: For each query, use the top N images generated from Step 3 as positive samples, and randomly sample N negative samples from the rest of the dataset. Optionally, we can divide these samples into two non-overlapping sets, and one is for training a classifier and the other is for verify and fine-tune the classifier. Of course, more sophisticated approaches for training data selection can be applied here. It is obvious that it is an essential step in this approach.

Step 5: Train a classifier for each query based on some visual features. Please note there are a large number of classifiers need to be trained, so the complexity of the classifier needs to be taken into account. Obviously, scalability is an essential aspect that needs to be considered in this step.

Testing:

Assuming the input is an image-query pair. Then you will check whether the query has been included in your trained query list. If yes, then, apply the model on the image and get a relevance/confidence score. Of course, visual features need to be extracted from the image first before applying the model.

If not, it is a bit tricky. The simplest way is to return a random prediction. Alternatively, we can find one or more “similar” queries that we have already modeled, and then use those models to predict the relevance scores and then combine the outputs from those models to generate an estimated relevance score of the image to the target query.

Please note in the real evaluation process, the time cost for feature extraction and label relevance prediction will impact the evaluation results. There is a time limit for the web service to return the prediction result to the evaluation server. To avoid the impact of network latency, we’ve left sufficient buffer there. Researchers should make their feature extraction and label prediction as fast as possible. Though we identify winners by comparing the average DCG numbers, the response time of the web service will be used as tie-breaker if two teams DCG numbers are the same or very close.

When all the “image-query” pairs are predicted, you’re able to generate a rank list according to the confidence scores for each query in the develop set. Then you can calculate the DCG of the query and then average on all queries in the develop set to get your final result.

Some Additional Notes

In the above exemplary approach, please note the outputs of the predictors need to be “normalized” so they are comparable, because the image rank list for a certain query will involve comparing the scores from different classifiers.

Please note some query have very few images in the dataset. It may be helpful to do some pre-processing before training the final model which will be evaluated. For example, to discover more images in the dataset that may be relevant to the query thought whatever data analytical approach.

Please note that manual labeling is not scalable for big data applications and hence is discouraged for cleaning and creating additional training data.

An alternative approach to handle “out-of-lexicon” queries in the develop/test set is to model n-grams instead of queries. For example, if we’re able to train models for “A”, “B”, “C” and “A B”, “B C”, then we’re also able to predict relevance scores for query “A C”, “A B C”, etc., even they don’t appear in the training set.

--

看了这么多，来简单的理一下这个算法的思路：

Training:

Remove meaningless words, and then aggregate the query counts;

Label propagation on training set;

Find all the clicked images for each unique query, and then sort by click counts;

Select positive and negative samples for each query, and optionally, divide these samples into two non-overlapping sets, one for training and the other for verification and classifier fine-tuning;

Train a classifier for each query based on visual features.

Testing:

Check whether the query has been included in the training query list;

If the answer to Step 1 is yes, get a relevance/confidence score;

If not, return a random prediction or find one or more "similar" queries, and then obtain an estimation of the relevance;

Generate a rank list after all the scoring;

Calculate DCG and obtain the final result. 

--

Reference: