On augmenting database schemas by latent visual attributes

There have been addressed problems related to effective search in heterogeneous data by the means of multimedia exploration systems [7, 18, 35]. That involved similarity-driven (e.g. force-directed) layout to present results on computer screen, exploratory operations that allow to navigate within distance-based spaces, and efficient data structures to execute them. Although these tools had good evaluation results, the results are difficult to transfer to every day’s search needs. One of the reasons is that multimedia exploration is not established as an retrieval model in existing tools (nor unified or even standardized) when compared to the relational model (and SQL) that is well known, simple and ubiquitous.

One of the major challenges the information retrieval domain facing nowadays is the ability to work with multiple modalities (e.g. numerical attributes, text and images) at the same time. Such so-called multi-modal search tools need to operate with different querying mechanisms, but also multiple search models (e.g. relational, graph-based and similarity-based). In earlier approaches to multi-modal searching, there have been utilized multiple modalities by mapping them all into a similarity space by creating a distance function that considers all known data. However, the search behaviour is sometimes counter-intuitive for the end user and cannot be simply incorporated into existing software applications.

Let’s formulate an example from the domain of fashion and decompose the following search intention: “I am looking for a flower-pattern dress, around 100$, for a party”.In this case, any single-model query wouldn’t be able to answer the search precisely, while a proper multi-model query could provide an exact answer. Please note that such decomposition is not universal and is subject to knowledge available for a given domain. There could be a database ready to answer the outlined search need with a single SQL query, because all the data are already available in the desired form. However, for most cases, the visual information is only contained in an unstructured image and must be processed—either by software or by the end user. In this example, both party and floral pattern are subjects to be “somehow” turned into attributes.

An important related task that attracted a considerable amount of research recently is the object classification task. Classification is a function from an unbound domain of input objects like images, to a fixed set of classes. The goal is to learn a mapping between object’s representation and corresponding class that generalizes well on not-yet-seen data. Some variants of the classification methods also focus on detecting and classifying parts of objects, but the underlying limitation is the pre-defined set of classes. In practical implementations, it also requires multiple examples of each class as training data.

However, let us consider an inverse problem. What if we know what our data is and we can control it, but we cannot define all possible class labels upfront and we also do not have any training data for them? We would like to iteratively discover new class labels based on patterns and usage of the data and integrate the labels into existing database schema as new attributes. We denote this task as attribute discovery. Our main research question is whether and how we could build on the knowledge from objects’ classification methods to solve such a different task as attribute discovery. The comparison in Table 1 suggests that there is a duality with respect to several axes when comparing attribute discovery to common image classification.

The key differences are as follows:

It is important to note that the described techniques originally target different tasks and operate on different levels of granularity. If certain attributes are known at design time, a specialized and pre-trained classifier (e.g. for stripe pattern, or for happy-emotion-clothes) will always do a better job than an unsupervised technique. In such case, the classes map to binary attributes (true/false classification) or numeric attributes (probability/weight of classification or number of occurrences). Similarly, if the domain has the capability to use or generate thousands of N-tuples of similar and dissimilar matching entities, supervised methods like PatternNet [27] will provide more specialized and better results. The important property of the environment our method tries to target is lack of any training data and no or limited existence of a specialized network for that particular domain.

For real-world purposes, we recommend the following orthogonal strategies to be evaluated in order to augment/extend database schemas:

Our motivation outlines the goal toward database schema augmentation via latent visual attributes. This work is a comprehensive full research paper synthetizing and developing partial results published in conference papers [19, 46, 48]. The papers [48] (demo paper) and [46] (short paper) addressed some narrow-scope aspects of discovering shared visual features in product photographs within a fashion e-shop system (i.e. missing the application-agnostic extension to database scheme augmentation). The works aimed rather at a multi-modal product recommender system than at a database-oriented research. In the short vision paper [19], the challenges and roadmap for a more general framework were discussed, with no actual methodology, implementation and experiments. As planned/envisioned in [19], in this manuscript the whole model is developed into a complete data management pipeline (including the human in the loop). Over the previous works, this manuscript includes richer related work (Sect. 2), formal methodology for the process of database schema augmentation (Sect. 3), system architecture and implementation of the proposed methodology (Sect. 4) and finally a user study and experiments demonstrating the outcome of the proposed methodology (Sect. 5).

Relational data model was first coined by Codd [16] as a proposal to manage large data banks. Each relation consists of a heading and a body. The heading is an un-ordered set of named attributes with data types. As per the Cambridge dictionary,² an attribute is “a quality or feature of a person or thing, esp. one that is an important part of its nature”. An attribute could be represented by a simple data type (number, string, date) or by a complex object, often serialized as BLOB type. The body of a relation is a subset of the Cartesian product of all attributes, a set of n-tuples following the heading. Each n-tuple can be uniquely identified using a key, a subset of all attributes marked using underline.Industry is dominated by SQL databases derived from the relational model, family of data management solutions called after the query language SQL. Despite novel approaches to data management (nosql, hybrid databases, multi-model databases), SQL remains the language with widest adoption across industry professionals thanks to it’s ease of use and declarative nature [20]. The declarative power of the relational model is further built upon by newer additions to the language such as window functions or pivoting coming with SQL : 2003 standard [15].

In our work, SQL environments are the integration target. We define data pipeline for visual information which lands its result in normalized data tables. We offer projections on the data using standard SQL features, which allow different views on captured visual information and can provide benefit to different application-specific use-cases.

Similarity-search concept provides a general model for content-based search in unstructured data such as multimedia. Given a dataset of descriptors of objects (e.g. images) and a query example descriptor, the most similar objects are returned. To avoid expensive similarity calculations, metric access methods [59] such as the M-Tree [11, 52] were designed for problems satisfying the metric postulates. Most forms of metric access methods involve pivots, selected objects from the dataset which are used for pre-calculation of similarity values, and prune large portions of the database at query time [36]. The pivot information can be also used to partition the dataset into a Voronoi space [12], which can be utilized by both exact and approximate search queries [38]. In our work, similarity search is the basic building block to find visual patterns in a dataset of (product) images. Due to size constraints, a large-scale technique for approximate similarity joints based on Voronoi partitioning was used [8].

A field which leverages similarity search is the multimedia exploration [3]. Admitting that perfect query formulation is not always possible, novel user interfaces and techniques to navigate multimedia and multi-modal datasets were researched in the past [34, 35]. In selected domains and use-cases, our proposed work aims to make multimedia exploration redundant by solving multi-modal search via relational schema augmentation.

A standard operator used in similarity search is the kNN query for single-input queries and kNN similarity join for set operations. Following text provides basic definitions for them.

When running a similarity join with the query set and dataset being equal, we refer to it as self-join. It produces sets of objects close to each other in the distance space, i.e. identifies near-duplicate or duplicate objects.

Modality is a way in which something is experienced by humans—such as vision, text, sound, taste or smell. The possibility of combining multiple modalities in information retrieval has been researched in the past decades and is referred to as multi-modal search [2, 6]. The basic categories of combination are early and late fusion of multiple modalities. Furthermore, cross-modal search [56] is defined by taking one modality as an input query and retrieving relevant data of different modalities.

Our work aims to satisfy both multi-modal and cross-modal search paradigms. By extracting complex information into relational attributes, standard query mechanisms can be used to accomplish both.

In the last years, many research topics were experiencing the deep learning revolution. Techniques based on deep convolutional neural networks (DCNNs) became the state of the art for many problems, and it was one of the driving forces for our vision of visual attribute discovery. The gradually increasing semantic levels [58] of different layers of the network can detect patterns previously not imaginable with analytical feature descriptors like MPEG-7 or SIFT [9, 37]. One of the research topics lately dominated by deep learning is also image segmentation [31], one of the building blocks of our proposed methodology.

The pioneer DCNN architecture AlexNet [25] contains five convolutional layers, three fully connected layers, and max-pooling layers in between. Newer networks are usually comprised from much more layers and include additional techniques and architectures to further optimize its effectiveness [24, 43]—ResNet, Inception and ResNeXt are just a few examples. The different layers of various networks have been shown to hold different levels of visual information [58], starting with pixels and edges and ending with semantic classes.

DCNN networks are commonly optimized for an image classification task with a fixed set of generic classes. However, the trained models have been successful also as generic feature extractors [14, 60] creating feature vectors by collecting neuron activations after an inference (forward-pass). This makes it possible to use a pre-trained model of a network to solve a problem different than the original static classes. This technique was adopted in our research as well. In general, this technique is part of transfer learning methodologies [49]. There was validated the positive impact of using a model pre-trained on general imagery (ImageNet) on a visually different domain [48]. Further analyses of the impact when using the same model for patches of images shown further improvements of search results [41, 46].

The problem of identifying commonly occurring visual aspects within an image dataset is called “Visual Pattern Discovery”. This problem was defined in order to solve many tasks in computer vision, e.g. content-based image search, object localization [53] or visual pattern recognition [57]. An example of recent visual pattern recognition architecture is PatternNet [27]. PatternNet analyses filters on the last convolutional layer aiming to find locally consistent visual patches for preselected categories. The network specifically stresses on finding patterns that are both representative and discriminative. Although such solution could be used as a building block in identifying new visual attributes, it does require a domain-specific learning phase and a number of training example-sets. At the same time, the expected number of visual patterns must be preset.

In our use-case of discovering latent visual attributes, we face the problem of an unbounded size which is impossible to estimate at design time and is always varying over time due to discrepancies in human interpretation. At the same time, we are targeting use-cases without a supervised training step and aim to eliminate the need for a dedicated training dataset. Nonetheless, we adopted the need for representative and discriminative patterns in the proposed framework.

The standard problem of image classification exists also in specialized variants for products. This is driven by needs for efficient product image classification methods, and state-of-the-art solutions are typically based on supervised methods [30]. Like in generic image classification, convolutional neural networks have lead to largest advances. With the increased usage of e-commerce for fashion, specialized techniques for fashion item retrieval have gained research attention. The domain brings several additional challenges.

Cross-domain retrieval between street-captured photographs and cleaned product photographs represents one of such challenges. Product photographs typically have a standard background, orientation and scale. Novel approaches have been created to target different variants of the problem, such as Street2Shop, Shop2Street or Video2Shop [10, 23]. For supervised approaches, an established dataset DeepFashion [32, 33] provides training data with over 800,000 labelled images, classified into 50 categories and 1000 attributes. Another fashion-specific challenge is the outfit completion problem [29, 50, 54]. Here, the task is to recommend suitable complements to a partially constructed outfit, so that the visual style of the proposed product match with the rest of the outfit. These tasks can be considered in a pipeline, where Street2Shop-like algorithms can be utilized as data constructors for the outfit completion problem.

We see possible synergies between the work of attribute discovery and cross-domain fashion retrieval. Namely, techniques for fashion style generation based on street-level image analysis could be another source of implicit feedback for visual patterns in the fashion domain. That is, the fact that certain items are often spotted together on the street might be a relevant signal for a common attribute that is yet to be discovered. Existing trained models for product classification would be also a natural pre-processing step to extend a new dataset with attributes, thus reducing the scope for attribute discovery. On the other hand, the goal of outfit completion algorithms is mostly orthogonal with our use-case. Instead of focusing on recommending items based on their latent style descriptors, we aim on disclosing the visual (style) patterns themselves and making them transparent for users.

We assume the existence of a database modelling the entities and their known attributes as named tuples, and an image of the entity represented as a bitmap of pixels. As for the image properties, we assume to have canonical product photographs that are common for e-commerce vendors, i.e. centred objects oriented in the same direction with similar product size ratio and uniform background. Premise of our work is that this image inherently contains other semantic features which are not yet covered as attributes in the existing database.where ID represents the unique identifier of each entity, \(A_1 \ldots A_n\) are existing known attributes and Img is a serialized binary representation of an image. Images are typically represented as a (possibly compressed) matrix of pixels. Each pixel (with i, j denoting its coordinates) carries the value of a colour from a chosen colour model, with RGB being the dominant one for storage purposes.

The aim of attribute discovery is to have a process transforming the original set of attributes into an extended set of attributes, while utilising visual information contained in the image. We split the process into two core parts: With this definition of the problem, we propose a formal methodology to systematically discover new attribute candidates and augment database schemas using integration of these attribute candidates. The process is a pipeline consisting of several steps, illustrated in Fig. 3b. The following text describes each of the process steps in detail.

To support multiple levels of granularity for new attributes, we can segment the original image into many possibly overlapping patches, out of which each can yield separate proposals for new attributes. More precisely, the segmentation process assigns each pixel of the image to 1 or more patches. A patch is a subset of the original image, and the union of all patches re-creates the original image. We denote a set of all possible patches as Patches and a single instance as \(Patch_{Img,k}\), defined by its original image and a sequential number.With this terminology, the image itself can be considered as one of the patches, and when writing about patches, we will implicitly assume that one of them is also the full original image. In simplistic scenarios, image patches can be restricted to be continuous and rectangular. In that case, each patch could be defined just by a pair of image pixel locations defining the upper left and lower right corners of the rectangle. But in the general case, the segmentation problem allows patches to be of any shape and not necessarily continuous.

In our model, proposals for new attributes are suggested using visual patterns detected across patches from the entire dataset. Similar patterns are defined as patches being close in a distance space which is constructed using a feature extraction tool and a patch-distance function \(\delta \). A feature extractor takes a single patch as input and produces a feature descriptor as output. The universe of feature descriptors is denoted as \(\mathbb {U}\). The visual pattern then acts as a constructor for a multi-query distance function, which is to be evaluated against the entire dataset and materialize a new attribute. We define the initial proposals for visual patterns as similarity sets.In a practical setup, \(\mathbb {U}\) would usually be a vector space, where vectors of individual patches are obtained as neuron responses from a DCNN layer during forward pass. Also, the distance function should usually satisfy the properties of metric spaces. However, these requirements are not enforced by the general model but specific to an implementation. For the same dataset, multiple feature extraction methods and possibly also multiple distance functions can be used at the same time, resulting in more proposals for attribute candidates. In the area of deep learning networks, each layer of the neural network can produce an independent feature extractor for example.

For efficient creation of the similarity set, approximate algorithms for distributed and highly scalable similarity self-join and kNN-join were used [8]. This was needed to reduce the computation cost of calculating all pairwise distances across the entire dataset and is an approximation which uses the triangle inequality property of metric spaces to avoid majority of distance calculations. The results of the kNN-join can be used as a starting point for refinement to obtain candidates for approximate similarity sets, after several steps of filtering and clustering operations. The following text describes the refinement steps needed to reduce the amount and size of results produced by a similarity self-join on patch features from the entire dataset. It also shows how these results are clustered together to produce unique and de-duplicated sets.

Having the similarity sets, we have observed that not each of them represents what humans understand as an attribute and what brings value in information retrieval scenarios. More specifically, we are looking at the following properties to be satisfied:We propose a sequence of heuristics to support these three properties and to reduce too frequent patches (visual noise) in the similarity sets. Example of noisy sets include background-only patches, mono-colour patches or other patches which are equal or near-equal in the distance space. The heuristics are based on observations of real data and governed by hyperparameters which were tuned in the offline and online evaluation phases.

The complexity of the pre-processing phase is dominated by the similarity self-join calculated on all patches from the entire database. This is a super-linear operation whose efficiency depends on the distribution of values in the distance space [8]. These candidates are meant to be reviewed in a system-supported workflow, accepted, and easily integrated into existing database schema.

In our model, human is an essential last step to complete the workflow. For the complete workflow, we define the following actors:

It is the domain administrator who contributes to the last step completing the workflow. Discriminative power of human vision can be used to quickly filter out noisy or irrelevant attribute candidates and to review promising ones. Detailed review of an attribute candidate evaluates the before-mentioned multi-query search across the entire database to show how the attribute applies to it. It is left to the domain expert to filter out noise entities, blacklist/whitelist entire categories, find a distance threshold for the proposed attribute candidate and provide a new name for it. For a given similarity set and an entity \(e(id,a_1..a_n,img),e \in Entities\), the attribute distance f calculates the average value between the entity’s image img and each of the members in the similarity set. The value for entity’s image and one patch is then calculated as the minimal patch-distance \(\delta \) between that query patch and any of the extracted features from all patches of the image. The attribute distance f between an entity e and an attribute candidate s is defined as follows:where \(S_i \in S'\) is the similarity set representing the attribute candidate \(candidate_i\), q are all its features obtained from patches, extraction is the selected feature extractor and \(\delta \) is the patch-distance function.

The accepted attribute is then persisted in the database schema and made available in different forms for application uses. In Fig. 3a we show the E-R diagram for capturing information about accepted attributes. The entities for Products, ProductCategories and Category are expected to already exist in the database. The other tables are filled by the system at the time of attribute acceptance with the following semantics and example instances:The described schema not only allows to define different views for application usage, but also contains necessary information to re-apply the attribute in the context of dynamic databases, where new products are being added. This is described in more detail in Sect. 4, including SQL-based VIEWs that utilize this schema.

As described in Sect. 1, our motivation for attribute discovery comes from recent advances in computer vision community. The advances have been boosted greatly by the deep learning revolution in recent years and delivered many solutions to different tasks. These solutions are not only black boxes approximating a specialized function, but also have a valuable internal structure. As various authors have shown [14, 48, 58], data from the internal structure can be extracted and used as high-dimensional feature descriptors. Specifically, for deep learning-based techniques, a standard mechanism to generate feature descriptors is to extract values of neuron activations from a certain layer of the network after a forward pass of input data. For the sake of simplicity, we have selected AlexNet [25] in our experimental setup. AlexNet is a pioneer architecture for deep convolutional neural networks (DCNNs) developed in 2012 for the classification task at the ImageNet competition [13]. Since then, it was shown many times that the generalizing effect of DCNN architectures allows to utilize the activations of the internal DCNN layers also for different tasks, such as image retrieval [39]. Recently, it was shown [45] that deep models pre-trained on generic imagery (such as AlexNet) could be successfully used even for representation of artificial images being very different from images used for training (such as visualizations of non-visual data). This observation is rooted in the convolution operation that gradually aggregates lower-level concepts into higher-level ones, enabling thus options for visual-semantic feature extraction.

As new models are created, this component of the system architecture can be easily replaced. Both by new models pre-trained on different image datasets, and by novel architectures and computer vision solutions, as long as there is a possibility to extract feature descriptors. Although analytical solutions like SIFT [37, 60] or PCT signatures [26] could be used as an implementation for this step, it is the convolution operation which delivers the ability to reveal and describe concepts of higher level of abstraction.

To support different levels of attribute granularity, our solution operates not just on entire images of entities, but also on segmented patches. As shown in [46], the usage of image patches improves retrieval quality in various search tasks and makes use of them in attribute discovery as well. In our experiment, we have started with a naive approach of segmenting input images using regular grids. Expanding on our previous work [46], segmentation was done using two regular grids, \(3\times 4\) and \(6\times 8\) in size. This has produced 60 fine-grained patches per input image in total, and offering two different levels of size granularity. This naive approach was possible as the selection of segmentation algorithm is orthogonal to the other parts of the processing pipeline and the underlined dataset contains canonical product photographs.³ For more complex scenarios (e.g. street-level photographs), the segmentation algorithm can be simply replaced by some more advanced technique (e.g. the ones surveyed by Liu et al. [31]).

During our experiments, we also evaluated the usage of inner AlexNet’s overlapping windows in convolutional layers as a possible source of image patches and their descriptors. However, the demonstrated quality of the results was too low to justify this choice.

For each of the created patches, feature descriptors were extracted using the same mechanism as in our previous works [46, 48]. Based on preliminary results, the neuron activations of convolutional layers 3, 4 and 5 followed by a max-pooling step were chosen for the experiments with domain experts. Other configurations (e.g. initial convolutional layers and fully connected layers) were excluded due to the poor quality of generated attribute proposals. This resulted in 384-dimensional vectors for the third and fourth layers, and 256-dimensional vector for the fifth convolutional layer of AlexNet.

As the next step, we ran the approximate kNN self-join operation to initialize the approximate similarity sets construction. In our experiment, we have worked with 19,172 product images. With 60 patches per image, we generated 1,150,320 intermediate images. A non-optimized similarity-based retrieval would have to calculate distance between all possible pairs—1,323,236,102,400 distance calculations. A full similarity graph is computationally not a feasible solution, and we had to trade off full precision for pre-processing time. As similarity sets only contain patches that are similar to each other, we chose the restriction of retrieving 512 nearest neighbours for each patch and calculated a kNN-self-join using MapReduce on the Hadoop environment [8]. Note that the restriction of 512 neighbours only affects the construction of similarity sets, which later defines an attribute candidate. The volume of nearest neighbours was chosen as the largest value we are able to calculate and store results for. The attribute candidate can then be turned into a multi-query and executed against the entire dataset as needed.

We have defined attribute candidates using sets of image patches, acting as a constructor for multi-example query. This produces a function which can score entire dataset using a distance measure. However, not every produced candidate follows what humans understand as an attribute, and intermediate results after applying approximate similarity self-kNN-join contain too much noise and duplicates.

To reduce the noise, we implemented a pipeline of filtering steps based on distance values, distance distribution within a kNN result, and based on symmetrical property enforced using reverse-kNN-lookup. These heuristical filtering steps allowed us to reduce the number of proposed candidates by 85% and the average number of patches contributing to a candidate by 99%.

To eliminate duplicates and further decrease the number of intermediate results, we employed clustering using graph decomposition into independent connected components. To maintain the discriminative and representative properties of attribute candidates, the resulting clusters were further refined using threshold hyperparameters based on the size of a cluster, \(T_{clusterMin}\) and \(T_{clusterMax}\). Depending on the selected configuration, the final number of proposed attribute candidates was on average 0.3% of the original size of kNN-self-join.

At last, existing attributes already present in the dataset were cross-checked against all attribute candidates using Point-Biserial correlation measure. This acts both as a filtering measure to remove information already contained in existing data, and a ranking mechanism to sort candidates by additional value they could provide over existing schema.

Within our candidates for visual attributes, same database entity might be covered using multiple candidates at the same time. Implicitly, this builds a relationship graph between entities using co-appearance in an attribute candidate as edges between the nodes. If an end user is looking at entities A and B, can we infer any new knowledge using this graph? Not surprisingly, this question is very similar to problem definitions in the recommender systems community and there are existing tools to solve it. One class of solutions for rule inference is called “frequent pattern mining” [28] and Market Basket Analysis [1] is one of its representatives. In order to fit the technique, we had to transform our data. Attribute candidates become baskets, and entities covered in it (not their image patches) become items of the basket. The output of the algorithm then produces association rules in the form of functionswhere both antecedent and consequent are sets of items (database entities in our transformation).

This generates an additional insight from visual data on top of database schema extension, with applicability in application-specific use-cases like product recommendation.

In section 3, we have defined the basic actors of our methodology. For accurate integration of new attributes, domain administrator is the most important actor. For larger databases, the domain awareness (the knowledge of domain expert) would become a scalability bottleneck. To overcome it, a grouping of the database into sub-domains based on pre-existing information would be needed. The methodology assumes domain knowledge, and different actions are supported by the software architecture. We have developed an administration user interface where domain administrators can:The process for accepting attribute candidates by the domain administrator begins with an initial display. Pre-processed attribute candidates are loaded from persistent storage (candidates that were accepted or rejected in the previous sessions are filtered out). Displaying of the attribute candidates is done using thumbnails of their defining images and highlights of all relevant patches. This display usually carries sufficient information to assess an attribute candidate and quickly reject it if needed. The most common reasons for rejection were:In other cases, the attribute candidate can be expanded. This shows application of the attribute to the dataset, being ranked via a multi-query distance function as described in Sect. 3.6. The display also highlights patches that caused the attribute to be applied. The task of the domain administrator is to find a threshold for applicability of the attribute in the ranked list. In order to exemplify the task, human judge is simply asked to select the last (most distant) item that still complies with the intended attribute description. The distance of this item is considered as the threshold value. Additionally, to filter out possible noise, human judge has the following tools at hand:When an attribute is accepted, the acceptance information is immediately persisted and integrated into the database. On top of the ranked list of entities from the dataset falling below the threshold, this also includes calculated distance value, coverage of matched image patches for each image, and information about applied filters. This information is then utilized in different views operating on the data, as well as during ingestion of new entities to the database and determining relevance of already applied attributes.

During ingestion of new entities to the system, the first part of the pipeline is executed as is—images need to be segmented into patches, and feature descriptors extracted. After that, extracted descriptors can be evaluated against all already accepted attributes. The system remembers the distance threshold per each attribute and can therefore use it as a decision criterion after calculating the distances between descriptors belonging to the new entity and the descriptors of patches defining the attribute. On top of that, whitelist and/or blacklist applied by the domain administrator can be also applied against known information about the new entity.

For large relative changes to the dataset, entire pipeline should be repeated as new entities can reveal new patterns in the data. This does not drop previous work done by the domain administrator; it is a mere generation of additional attribute candidates. The same de-duplication technique based on correlation ranks is to be used to reduce the amount of attribute candidates.

Our model so far has been modelled around unsupervised generation of attribute candidates and final acceptance by domain administrators. In the context of long-running web enterprises, however, a lot of knowledge about relations between items can be exposed in collected implicit user feedback (i.e. historical co-consumption data) . This implicit feedback can take many forms—search history, shopping basket contents, stream of visited objects, images displayed in full size to end users and many others.

The aggregated implicit feedback is often utilized, for example, in collaborative recommender systems [22] to suggest additional potentially relevant items to the users. The working hypothesis of collaborative recommender systems is that users tend to pursue their interests consistently to some extent, and therefore, if users shared interests (e.g. mutually visited objects) in the past, they should share them in the future as well. In our use-case, we follow a similar hypothesis by considering that a portion of user’s visits reflect his/her interest in some visual attribute. Although such information tends to be very noisy in individual instances, several techniques for frequent patterns extraction, e.g. Market Basket Analysis [1, 44], were quite successful in de-noising this type of data.

While the collected frequent feedback patterns does not necessarily contain visually related objects, we assume that a portion of them would possess such property, and in addition, there is a certain level of guarantee that users took interest in this particular collection of items. Therefore, we can use the same attribute suggestion pipeline, but limit the set of possible attributes to the pre-filtered collection of items that frequently go together. That is, instead of using a full KNN-self-join over the entire database to generate similarity sets, we can restrict the search to operate just on prepared subsets of data. Rest of the data processing pipeline will ensure that the images are pushed through feature extraction, segmented, patterns of image patches are identified, cleaned and aggregated. This will again produce attribute candidates, but this time further supported by a crowd-based evidence.

The last step of our schema extension pipeline is the integration of new attributes into the original schema of the database. This happens in real time when the domain administrator accepts a new attribute by filling in data structure presented in Fig. 3a. The normalized schema is optimized for data maintenance, but is not optimal for attribute querying. For the purpose of data querying, we defined views that present the new attributes in a way that can be better consumed from various applications such as recommendation, search or display functionalities of a system.

The information captured during database schema augmentation goes beyond binary tags (named labels that are either present or missing). The acceptance process transparently captures additional information that is able to provide numerical information for querying purposes. The first additional information is the number of patches matched during attribute acceptance phase, expressing the coverage of a certain attribute. A database user is then able to rank or filter objects according to their ratio, such as “retrieve all objects ranked by their floral pattern coverage”. A second indicator is the distance between the attribute definition and the object itself, which is a decimal number. For normalisation purposes, we provide a view which turns the distance values into a percentile. This can be used to define, for example, “TOP N attributes for an entity” using the distance percentile as a ranking criteria across different attributes. In the following text, we demonstrate the integration of collected attributes into an existing SQL database environment. The examples are written for Microsoft SQL Server 2017, and the query constructs work with minor changes in any database supporting the SQL:2003 language standard.

First query shows how to normalize distance values using distance percentile within each attribute instead of using the raw distance value between an object and a visual attribute definition. The distance percentile is calculated using the \(PERCENT\_RANK()\) window function. This is used as a basis for other queries and views.

The following query uses the normalized distance information to pick top 5 attributes for each product in the database. Since each relation between attribute and product is originally represented as a separate row in the database, the PIVOT clause is used to turn top 5 attributes into individual columns instead. Figure 5a illustrates section of possible results.

The last code snippet shows how all attributes can be queried at the same time, in the form of a matrix of products and attributes. In the result set, each row represents 1 product and each column 1 attribute. This is achieved using dynamic SQL, where all attributes are first queried from the attribute definitions and then turned from rows into columns using the SQL PIVOT clause. The end result is closest to standard database representation of an attribute and makes it natural to express search intentions like “Find me converse-style shoes that are colourful, ordered by price”. A part of the result is illustrated in Fig. 5b.

The evaluation dataset consists of the objects available in two major Czech retail shops,⁴ both focusing on the fashion domain. The range of the dataset is relatively broad. Besides for the major categories of shoes and clothes, there are also some members of accessories (e.g. watches) or home appliances categories present in the dataset. In total, the dataset contains 19,172 objects, organized into 215 categories and further described by 711 tags. For the purpose of the research, we do not distinguish between tags and categories (as they were primarily distinguished for the navigation purposes in the original websites) and denote them uniformly as original attributes. Figure 6 displays a histogram of attribute-product coverage. We can see that there are a few densely covered attributes and a large volume of long-tail attributes with only a handful of products.

In Sect. 3, we introduced several hyperparameters of the considered model, those were the feature extraction method and the thresholds for near-duplicate filters \(T_{nearDuplicate}\), large sets filter \(T_{maxValue}\), distance derivative filter \(T_{distanceDerivative}\) and finally minimal and maximal similarity set cluster sizes \(T_{clusterMin}\) and \(T_{clusterMax}\). This induces a relatively broad parameter space, which is impossible to be evaluated directly by domain administrators. Therefore, we introduced an offline evaluation step in order to pre-process the suitable variants of the model parameters. In the offline pre-processing phase, we performed a grid-search evaluation as follows. As a feature extraction method, we utilized activations of one of the last three convolution layers of the underlying DCNN (denoted as conv3, conv4 and conv5) and the cosine distance metric. The \(T_{nearDuplicate}\) and \(T_{maxValue}\) hyperparameters were held constant at 0.3 and 0.95, respectively. These constants were defined manually by observation of the distance distribution in the space of descriptors created by AlexNet layers and the Euclidean distance, with the intention to filter out clear near-duplicates. \(T_{distanceDerivative}\) was selected from (0.76, 0.99) range, \(T_{clusterMin}\) was selected from \(\{2,4,6,8,10,12\}\) set and \(T_{clusterMax}\) from \(\{25,50,100,200,400,800,1600\}\) set. In the rest of the paper, the hyperparameter settings of the model will be denoted as \(M(fe, T_{distanceDerivative}, T_{clusterMin}, T_{clusterMax})\), where fe denotes the feature extraction method. It is important to note that this setting only affects the search for attribute candidates, i.e. sets of patches used as a pattern across the entire database. The ranges of possible values were chosen based on preliminary results which excluded lower/higher values because of degenerated results.

Usually, the offline evaluation would consider some variants of maximization of user (domain administrator) engagement per model variant, such as the ratio of accepted attributes per model or similar. However, as we did not have any such feedback upfront, we resorted to evaluate some of the aggregated properties of the proposed attribute sets. To be more specific, for each model settings \(M(fe, t_1, t_2, t_3)\) we considered the volume of proposed attributes \(a_M\) and the overall coverage of items from the dataset \(c_M\).

First, we expect a good model to reasonably cover the whole dataset (i.e. that there is at least one attribute candidate for most of the items). Second, in order to decrease the workload of domain administrators, we wanted to minimize the total volume of candidate attributes.

Therefore, while evaluating the suitable candidates, we kept only the model variants, which had a coverage \(c_M > 10000\) items, i.e. 50% of the dataset. Out of the remaining models, we performed a greedy selection based on the \(c_M/a_M\) ratio, while maintaining a sufficient level of diversity among the selected models. The last condition was introduced because the offline evaluation metric is provisional at best, and therefore, we opted for the chance to evaluate a broader range of hyperparameters in the user evaluation phase. To guide with this subjective selection, several other metrics calculated offline were considered: average size of attribute candidates, average number of matching patches per image, distance variance within attribute candidates or maximal distance within candidates.

Finally, Table 2 depicts the model variants that were selected for the user evaluation.

In order to evaluate the usability of the suggested visual attributes, we conducted a user survey focused on confirmation or rejection of the candidate attributes proposed by individual variants of the model.

The user study depicted in the previous section left one important question open. If we let the domain expert to create attributes manually, could the process be more efficient? In order to clarify this point, we employed several domain experts and let them work with a VADET tool [41] designed for manual visual attributes construction. VADET tool allows to filter items based on categories and search for visually similar items based on multiple query items. It also allows to focus the similarity search to certain regions of the queried items. Please refer to [47] for a detailed description of the tool.

The tool was populated with the same dataset as we utilized for the user study in the previous section. Domain experts were first asked to familiarize themselves with the tool and the dataset.⁶ Subsequently, users were asked to manually construct new visual attributes that are not yet present in the database. In the rest of this section, we will refer to such constructed attributes as manual attributes as opposed to the semi-automatic attributes constructed by the pipeline proposed in this paper.

In total, five domain experts participated during the evaluation. Overall they interacted with the system for 4 h and 24 min and constructed 41 visual attributes. The mean time to construct a manual attribute was 6 min and 27 s, which is considerably higher than 1 min 42 s required in average for constructing an attribute in a semi-automatic manner. Manually created attributes also contained less items than semi-automatically created attributes (19.65 vs. 43.6 in average). Therefore, we can conclude that the proposed semi-automatic pipeline is more efficient than the manual constriction of visual attributes.

Next, we assume that the typical domain expert would first like to manually construct those attributes that are already in his/her mind and only then browse through the visual attributes suggested by the proposed pipeline for additional ideas. For such use-case, it is important that the suggested attributes are sufficiently diverse from the manually created ones. In order to evaluate this feature, we focused on the level of similarity between manually and semi-automatically created visual attributes.

Specifically, for each semi-automatic attribute, we selected the most similar manual attribute w.r.t. Jaccard similarity. Histogram of these similarities is depicted in Fig. 11. It can be seen that although several of the attribute pairs have relatively high similarity (up to 0.54), the vast majority of semi-automatic attributes does not correspond to any manually created attribute. We can therefore conclude that the proposed pipeline provides sufficiently novel visual attributes as compared to the ones created manually.

First of all, we need to note that the evaluation was negatively impacted by the fact that the list of categories is largely incompatible for both dataset versions. This included renaming existing categories, introducing some new ones and also some hierarchy modifications. In an online settings, this problem can be solved during the category construction/modification process, but in our evaluation settings, this condition hindered the applicability of black/white list filtering considerably (e.g. a significant portion of attributes with white-list conditions did not match to any new items and more than a half of the rejected suggestions could have been filtered out by a black-list condition, if the categories were not changed). Despite the reduced impact of the evaluation, we were still able to draw some conclusions.

In total, 122 suggestions were accepted and 101 rejected. We also identified several conditions significantly affecting the acceptance probability. First we focused on how distant were new items from the source similarity set (distances were normalized by the threshold defined during attribute construction). Accepted product–attribute pairs had in average lower normalized distance f than rejected ones (0.967 vs. 0.980; t test p value: 0.0002). Furthermore, attributes corresponding to the accepted suggestions had in average less manually discarded objects in the past (6.9 vs. 10.8; t test p value: 0.0007). Finally, the chance of acceptance was higher, if the attribute was restricted by some white/black list (Fisher’s exact test p value:1.5e−5). Surprisingly, user-perceived quality of an attribute had no significant impact on the acceptance probability.

Figure 12 depicts the dependence of acceptance ratio on relative product–attribute distance. It can be seen that the further away from the threshold distances are, the higher is the acceptance ratio. Nonetheless, the probability is still far away from values that would allow us to automatically confirm the product–attribute assignment without the human supervision. On the other hand, the confirmation task was relatively easy with a median time to decision equal to 1.98 s.

To sum up, attribute assignment evaluation for novel products showed that although the visual attributes are not distinguishing enough to allow automated assignment, majority of suggestions are accepted and the acceptance probability can be well modelled through several descriptive features of product–attribute relations. Therefore, visual attribute assignment can be approached as an attribute recommendation component incorporated into the new product insertion process (i.e. list of recommended visual attributes will be displayed for each new product, where the most probable attributes may be preselected).

As our future work, we would like to further research on the applicability of the proposed methodology.

First axis of the applicability are problem domains. Our work is best suited for domains with strong visual element, which also represents an important deciding factor in information retrieval. For example, furniture, travel, art, decorations or posters could be interesting candidates for further investigation and experiments. On the other side of the spectrum, there are domains where visual data exists, but either does not carry much information for user’s decision-making process or such information cannot be clustered into visual attributes. Although such distinction is subjective to some extent, we would not recommend our work, for example, for the domains of books, music records, software products, real estates or most areas of computer components.

Second axis would comprise from evaluating the added value of constructed visual attributes for end-users. Attributes may be directly disclosed to users via some searching or browsing GUI, or utilized, for example, in inner models of recommender systems. We would like to target both the changes in user’s navigational patterns and/or changes in overall consumption statistics via some A/B testing.

As third axis, we would like to explore a possible transition to other forms of multimedia beyond images. The deep learning revolution did not affect just image processing; it significantly improved state-of-the-art techniques in many other disciplines. With feature descriptors extracted from data sources like videos, sounds or texts, similar methodology could be applied to extract common patterns out of the data and turn it into structured attributes.