UDLF: Unsupervised Distance Learning Framework for Multimedia Retrieval

The Unsupervised Distance Learning Framework (UDLF) [1] is a software developed to facilitate the general use and evaluation of novel unsupervised learning methods. These methods aim at post-processing the ranking information for different tasks, being especially useful for multimedia retrieval. The major advantage of UDLF is that it provides a unified and extensive model for implementing different unsupervised methods. Any execution or experiment can be easily conducted by setting a configuration file, no recompilation is required. To evaluate the retrieval results, the framework computes different effectiveness and efficiency measures and it allows for exporting visual output results to external files. UDLF is written in C++, works out of the box, does not require external libraries, and is compatible with different operating systems including Linux, MacOS, and Windows. The source code is publicly available on GitHub under the terms of the GPLv2 license.

Introduction

The amount of information accumulating is continuously increasing. With the huge amount of data, defining methods to index and retrieve different types of information has become a fundamental need. Given a query, information retrieval systems (IRS) aim at ranking the most similar information to that query at the top positions in the result list. These operations can be performed with different types of data, like text documents, images, videos, and other forms of multimedia objects.

Different supervised approaches have been presented with the objective of improving the effectiveness of the retrieval results. Even more recently, unsupervised learning methods have been proposed aiming at post-processing this information without the requirement of any labeled data or training information. These methods have shown promising results in the literature [2-9]. However, the authors generally do not provide the source code, which makes difficult for the users to reproduce the results.

The Unsupervised Distance Learning Framework (UDLF) [1] features:

• a unified model for different unsupervised distance learning methods;
• seven different methods currently implemented;
• easy implementation of new methods;
• reading and exporting files in different input/output formats;
• compile once, execute for different tasks and datasets;
• easy to use configuration file;
• does not require any extra dependency;
• works out of the box, no installation required;
• compatible with different operating systems;
• completely open-source, licensed under GPLv2.

This article is presenting the version 1.00 of the UDL Framework. Since the software is being continually maintained and improved, it is possible that some details may differ if you are using a different release of this software.

UDL Framework

For most unsupervised learning methods an open-source implementation is not available. Moreover, methods which are publicly available do not provide a unified model for configuration and input/output files. Therefore, most users are not able to reproduce the experiments that are present in the literature. We propose UDLF which offers an open-source and multiplatform implementation of different methods for information and multimedia retrieval. The software defines a unified model, which can be easily extended with other distance learning methods. Furthermore, it provides a simple way to test different novel unsupervised distance learning approaches without demanding much effort.

The project can be compiled once and multiple experiments can be done by changing a configuration file, which specifies all of the settings and input/output files of the execution. Installation or recompilation is not necessary for most typical use cases.

Architecture and Organization

UDLF follows an Object Oriented Paradigm (OOP) in C++ and is developed using the C++11 standard. Figure 1 presents a simplified model of the architecture of UDLF, in which only the most relevant classes and functions are presented. As can be seen, the classes were divided into different categories depending on their role in the project:

• Core: classes responsible for program execution;
• Methods: the unsupervised learning methods, which are implemented following the protocol established by the “Udl” class;
• Evaluation: responsible for reporting the general measures of an execution;
• Utils: auxiliary functions.

Figure 1. Simplified class diagram of UDLF.

For functions and variables different prefixes are used: “+” denotes public components, “-” denotes private components, and “#” denotes components that need to be implemented by subclasses. Underlined functions (e.g. getInstance(): &ClassName) refer to static functions and classes. The use of static classes aims to facilitate the validation and read processes of the configuration file. The configuration file defines all the settings of one given execution and this is explained in further details in the next section.

The “Exec” class is responsible for starting the execution by reading the parameters in a configuration file and calling the validation process verifying the types and the possible values of the parameters. If the user has set an incorrect value, the issue is reported. The “Udl” class establishes a model for the implementation of all the unsupervised learning methods in the framework. All the methods prefixed with “#” need to be implemented by the derived classes, the details about each one of these functions are explained in more details later on. As can be noticed, different methods have different variables and different functions depending on their characteristics.

The classes “Time” and “Effectiveness” are responsible for reporting the efficiency and effectiveness measures (Precision, Recall, and MAP) of the experiments run using UDLF. For now, the “Time” class just counts the amount of time elapsed for a set of instructions. In the future, we intend to extend this class for providing statistical reports (e.g. average and standard deviation for a certain number of executions) and move it to the “Evaluation” part of UDLF.

Getting Started with UDLF

Figure 2 illustrates all of the main steps to get started with our software. The following subsections describe in details each one of the parts of the preparations that the user should understand to perform an execution.

Figure 2. Basic steps to get started.

1. Getting the software

UDLF binaries as well as the source code are available in the official software page and also in the GitHub repository. The most simple way is by downloading the executable for your operating system to be executed in the user’s terminal. However, if the executable for the operating system in use is not available, users can download the source code and compile it using the supplied Makefile. We recommend the GitHub repository for users that want to check for pre-releases.

2. Preparing input files

For running experiments and evaluations with UDLF there are mandatory and optional files. The mandatory files include:

• Ranked Lists/Matrices specifying the ranking of each element of the collection or the distance/similarity among the elements in the dataset. The use of ranked lists or matrices depends on the preference of the user (the choice is defined in the configuration file). Both possibilities are available;
• Lists specifying the name of each element in the collection. Each line specifies a different element. An example of lists file can be seen in Figure 3.

The optional files are

• Classes, which are required if users want the framework to report effectiveness measures. Each line specifies the class of an element of the dataset. This file must be in accord with the information in the lists file (same order of elements). An example of classes file can be seen in Figure 4;
• Dataset path, which is important for image collections. If the users want to visualize the rankings in an HTML file, the path of the images must be provided.

Figure 3. Example of lists file.  

Figure 4. Example of classes file.

For a better understanding of the rankings, Figure 5 presents an example of ranked lists file where the images are identified with their filenames. The dataset objects can also be identified by numbers (an object number is the line that it appears in the lists file) as shown in Figure 6. Besides the representation, Figures 5 and 6 represent exactly the same content. The type of representation to be used is specified once again by the configuration file, which is further explained in the next step.

Figure 5. Example of string ranked lists file.

Figure 6. Example of numeric ranked lists file.

For your first use, we highly recommend the dataset files that are available in the source repository. In case of any remaining doubt, more details about the file formats can be consulted in the GitHub sofware wiki.

3. Configuration

Each experiment run with UDLF is defined by a configuration file: the desired task, method being used, dataset information, input/output files, evaluation settings, and other details. To specify the values of the parameters, a key-value syntax is used: “PARAMETER = VALUE”. Line comments are supported using “#”. Figure 7 presents an example of configuration where the path of the files and the necessary parameters are set. Each line follows the structure: “PARAMETER = VALUE #(regular expression): explanation about the parameter”. Regarding the regular expressions, some simplifications were used: “TUint” stands for unsigned integer, “TFloat” stands for real numbers, and “TBool” stands for boolean values (true or false). Notice that the parameters and values are both case sensitive.

Figure 7. Example of configuration file.

A complete example of configuration file can be found in the GitHub repository.

4. Running Experiments

Since no installation is required, this step is really simple. An experiment can be done by calling the executable in your terminal: “./udlf [path_of_configuration_file]”. If no file is specified, the program searches for a file called “config.ini” in the directory of the executable.

In case of any issue with the parameters or the configuration, the program will attempt to use the default values for the parameters and proceed with the execution. However, if an important parameter is not specified and it can’t be inferred, the execution is aborted. Figure 8 shows a simple and short example that illustrates this process.

Figure 8. Example of how the framework reports issues in the configuration file.

5. Obtaining and analysing the results

The results are reported in the end of the execution and are also stored in a “log.txt” file as illustrated in Figure 9. As can be seen, it summarizes the most important parameters and their values, also including the date of the execution. The amount and type of results provided will depend on what was specified in the configuration file.

Figure 9. Example of generated log file.

Unsupervised Distance Learning Methods

There are seven different unsupervised learning methods currently implemented. Some of them has results compared with the state-of-the-art. Below there is a brief description of each one of the implemented methods:

• ContextRR [2]: the algorithm builds context images, which are abstract representations obtained from the ranked lists to make an analysis of the elements present in the dataset. Given the information extracted from the context images, more effective distance measures are computed;
• Correlation Graph Manifold Learning [3]: aiming at encoding the dataset similarity information, the algorithm employs a correlation graph. The dataset manifold is mainly exploited through this graph and its strongly connected components, in order to compute a more effective distance measure among the multimedia objects;
• CPRR [4]: the Cartesian Product of Ranking References (CPRR) method uses Cartesian product operations in the kNN and reverse kNN sets for each multimedia object. This is done in order to consider the contextual information encoded in the ranked lists;
• Manifold Reciprocal kNN Graph [5]: the algorithm builds a graph considering all the reciprocal references in the top-k positions of the ranked lists. Based on this structure, new ranked lists are computed through the analysis of the edge scores;
• Ranked List Graph Distance [6]: the algorithm represents each ranked list as a weighted sub-graph based on the top-k positions. These sub-graphs are combined in a single graph and the weight of the edges is used to increment the similarity scores between the multimedia objects;
• RL-Recommendation [7]: the method defines the concept of recommendations among ranked lists. The motivation is based on the conjecture that similarity information available in the ranked lists can be used to recommend multimedia objects among themselves. In this scenario, a recommendation indicates a reduction in the distance measures;
• RL-Sim* [8-9]: an iterative re-ranking algorithm that computes a similarity score between multimedia objects based on the similarity of their ranked lists. The algorithm uses the idea that if two multimedia objects are similar, their ranked lists should also be similar.

Development of Other Methods

New methods can be easily implemented and integrated into UDLF. As it was presented earlier, all methods must inherit from the “Udl” class. It is also necessary to extend the internal configuration files with the parameters of the new method. Aiming to facilitate the process of implementing new methods in the framework, a python script is provided. Given a file with the parameters of the new method, it creates all the necessary files and make all the fundamental changes in the software. Following the script execution, the new method can be implemented in the files “src/MyMethod.cpp” and “src/MyMethod.cpp” created by the script. There are several functions that need to be extended:

• runUdlMethod(): defines the main algorithm to be executed when a single file is used as input;
• runFusionMethod(): defines the fusion algorithm to be executed when two or more files are used as input;
• initDataStructuresUdl(): initialize the main variables and data structures used in the main algorithm;
• initDataStructuresFusion(): initialize the main variables and data structures used in the fusion algorithm;
• loadParameters(): load parameters from the configuration file into the method variables;
• checkParameters(): can be used to verify if the values were set in the permitted range;
• prepareInput(): should be used to prepare the input to the format expected for the algorithm (matrix, ranked lists, and others);
• prepareOutput(): should be used to prepare the output to the format expected for the algorithm (matrix, ranked lists, and others).

Conclusions and Future Work

UDLF is an open-source and multiplatform framework of unsupervised learning methods for multimedia retrieval and offers a unified model to run different distance learning methods on arbitrary data. Due to its open source nature and modular architecture UDLF can easily be extended and new methods can be added. A broad range of different experiments can be conducted just by modifying or creating a new configuration file, no recompilation is required.

In the future UDLF will support multi-threading and parallel execution of the available distance learning methods. Moreover, we are working on improving the usability of UDLF. We intend to provide a visual interface moving away from terminal input and we aim to provide conversion routines for common data formats compatible with UDLF. Besides that we are continuously maintaining and updating the code base and plan to provide new algorithms and implementing novel ideas, including methods from other research groups. We hope that many give UDLF a try and help us improving it by offering suggestions, ideas and any other form of feedback.

Acknowledgments

The authors are grateful to the São Paulo Research Foundation – FAPESP (grants 2017/02091-4, 2013/08645-0, and 2014/04220-8).

References

[1] VALEM, L. P.; PEDRONETTE, D. C. G. . An Unsupervised Distance Learning Framework for Multimedia Retrieval. In: International Conference on Multimedia Retrieval (ICMR), 2017.

[2] PEDRONETTE, D. C. G.; TORRES, R. da S. . Exploiting contextual information for image re-ranking and rank aggregation. In: International Journal of Multimedia Information Retrieval, v. 1, p. 115-128, 2012.

[3] PEDRONETTE, D. C. G.; TORRES, R. S. . A correlation graph approach for unsupervised manifold learning in image retrieval tasks. In: Neurocomputing, v. 208, p. 66-79, 2016.

[4] VALEM, L. P. ; PEDRONETTE, D. C. G. . Unsupervised Similarity Learning through Cartesian Product of Ranking References for Image Retrieval Tasks. In: Conference on Graphics, Images and Patterns (SIBGRAPI), 2016.

[5] PEDRONETTE, D. C. G.; PENATTI, O. A. B. ; TORRES, R. S. . Unsupervised manifold learning using Reciprocal kNN Graphs in image re-ranking and rank aggregation tasks. In: Image and Vision Computing, v. 32, p. 120-130, 2014.

[6] PEDRONETTE, D. C. G.; ALMEIDA, J.; TORRES, R. da S. . A graph-based ranked-list model for unsupervised distance learning on shape retrieval. In: Pattern Recognition Letters, v. 83, p. 357-367, 2016.

[7] VALEM, L. P. ; PEDRONETTE, D. C. G. ; TORRES, R. da S. ; BORIN, E. ; ALMEIDA, J. . Effective, Efficient, and Scalable Unsupervised Distance Learning in Image Retrieval Tasks. In: ACM International Conference on Multimedia Retrieval (ICMR), 2015.

[8] PEDRONETTE, D. C. G.; TORRES, R. S. . Image re-ranking and rank aggregation based on similarity of ranked lists. In: Pattern Recognition, v. 46, p. 2350-2360, 2013.

[9] OKADA, C. Y. ; PEDRONETTE, D. C. G. ; TORRES, R. S. . Unsupervised Distance Learning by Rank Correlation Measures for Image Retrieval. In: ACM International Conference on Multimedia Retrieval (ICMR), 2015.