Deep Style Match for Complementary Recommendation
Kui Zhao Xia Hu Jiajun Bu Can Wang







Deep Style Match for Complementary Recommendation
    
Kui Zhao^†, Xia Hu^, Jiajun Bu^†, Can Wang^†

†College of Computer Science, Zhejiang University

Hangzhou, China

{zhaokui, bjj, wcan}@zju.edu.cn

Hangzhou Science & Technology Information Research Institute

Hangzhou, China

hx@hznet.com.cn

    December 30, 2023
=======================================================================================================================================================================================================================================================




Humans develop a common sense of style compatibility between items based on their attributes. We seek to automatically answer questions like “Does this shirt go well with that pair of jeans?” In order to answer these kinds of questions, we attempt to model human sense of style compatibility in this paper. The basic assumption of our approach is that most of the important attributes for a product in an online store are included in its title description. Therefore it is feasible to learn style compatibility from these descriptions. We design a Siamese Convolutional Neural Network architecture and feed it with title pairs of items, which are either compatible or incompatible. Those pairs will be mapped from the original space of symbolic words into some embedded style space. Our approach takes only words as the input with few preprocessing and there is no laborious and expensive feature engineering. 




§ INTRODUCTION

We have a common sense of style compatibility between items
and can naturally answer questions like “Does this shirt go well with that pair of jeans?”
These kind of style compatibility information can be exploited in many commercial applications, 
such as recommending items to users based on what they have already bought; or generating the whole 
purchase outfits (see Figure <ref> for an example of clothes) to users querying certain items, if sufficient compatibility 
relationships between items are provided. 


To identify these compatibility relationships, existing methods such as frequent itemset mining <cit.> 
attempt to generate match items automatically by analyzing historical purchasing patterns. 
However, frequent itemset mining relies on historical purchasing records to find items frequently 
purchased together and new items will inevitably suffer from the “cold start” problem <cit.>.

Recently, McAuley et al. <cit.> and Veit et al. <cit.>
intend to discover the style match relationships between items using visual information presented in the images of items.
However, besides being computationally expensive, image-based matching methods 
are frequently plagued by the plentiful contents presented in images. 
For instance, Figure <ref> shows a part of the image for leggings from Taobao, 
which is the largest e-commerce platform in China. Besides leggings, 
the image also contains a coat, a pair of shoes and a very complex background etc. 
These contents will confuse the learning machines if only leggings are expected.



To overcome the limitations of existing methods,  
we propose in this paper a novel style match approach using the title descriptions of items in online stores. 
The basic assumption of our work is that online sellers will place most 
of the important attributes of a product in its title description, 
so that the product can be easily found by a keyword-based query. 
Therefore, the title description is a highly condensed collection of 
attribute descriptions for a product. 
So it is feasible to model compatibility between two items better if we are capable of mapping the title
pairs from the original space of symbolic words into some embedded style space.

We here design a Siamese Convolutional Neural Network architecture 
for matching title sentences. It will map two title sentences from an item pair into low-dimensional vectors respectively in parallel, 
which are then used to learn the compatibility between these two items in the style space. 
When designing the amalgamation part of Siamese CNN for computing compatibility, 
we have considered the ability of our model to be extended to  big data scenarios, 
which is critical for real-world recommendation applications. 
We test our approach on two large datasets: a Chinese dataset from Taobao provided by 
Alibaba Group and an English dataset from Amazon provided by <cit.>. 
Our approach demonstrates strong performance on 
both datasets, which indicates its ability of learning human sense of style compatibility between items. 



§ RELATED WORK

Finding complementary items has been studied for a long time. 
The early works can be traced back to frequent itemset mining <cit.>, 
which generates match items automatically by analyzing history purchasing patterns. 
Frequent itemsets such as “beer and diaper” sometimes have nothing to do with compatibility. What's more, they are challenged by the “cold-start” problem, which means new products 
with no historical records are invisible to the algorithm <cit.>. 

Many approaches such as content-based recommendation or social recommendation are proposed to address this 
problem (see <cit.> for a survey). 
Closely related to our work are <cit.> and <cit.>, in which McAuley et al. and Veit et al. attempt to learn clothing style similarity based on their appearance in images. However, our work differs from <cit.> and <cit.> in the following two aspects:
(1) we use title descriptions, which contain rich attribute information instead of item images; (2) the objective of our method is to find matching items from their attribute description instead of learning visual similarities from item images. 



§ PROBLEM FORMULATION

We here describe the problem in a formal way: 
given a query item set Q={q_1, ⋯, q_m} and a candidate item set C={c_1, ⋯, c_n}, 
where each query item q_i∈ Q comes together with the compatibility 
judgements {y_i_1, ⋯, y_i_n}. 
The complementary item c_j∈ C is labeled with y_i_j=1 and y_i_j=0 otherwise. 
Our goal is to build a model to compute the compatibility probability between q_i and c_j: 

    P(y=1|q_i, c_j) = f(ϕ(q_i,θ_1), ϕ(c_j,θ_1), θ_2),

where function ϕ(·) is the sentence model mapping a title 
sentence into a low-dimensional representation vector 
and function f(·) computes the compatibility probability between two items in the style space. 
The parameter vectors θ_1 and θ_2 are learned in the training process. 



§ STYLE MATCH

The main building block of our approach is a sentence model based on CNN. 
This sentence model will map two title sentences from an item pair into low-dimensional vectors respectively in parallel, 
which are then used to learn the compatibility between two items in the style space.


 §.§ Sentence model

We model sentences with function ϕ(·), 
which is a convolutional architecture as shown in Figure <ref>. 


In the following, we give a brief explanation of the main components in our Convolutional Neural Network. 


  §.§.§ Sentence matrix.

Our sentence model takes a sentence s as the input, 
where it is treated as a sequence of raw words: [s_1,⋯,s_| s|] 
and each word s_i is from a vocabulary V. 

Firstly, each word s_i is represented by a distributional representation vector 
w_i ∈ℝ^d, looked up from the word-level embedding matrix W∈ℝ^d× |V|. 
Then a sentence matrix S∈ℝ^d× | s| can be built for the input sentence s:

    S=
    [      |      |      |;    w_1      ⋯ w_| s|;      |      |      | ],

where the i-th column is the distributional representation vector w_i 
for the i-th word in s. 
The values in the embedding matrix W are parameters initialized with an unsupervised neural language model <cit.> and sequentially optimized during training. 
The embedding dimension d is a hyper-parameter of the model. 

As shown in Figure <ref>, 
for the sentence s=[Uniforms, Men's, Short, Sleeve, Polo, Shirt], 
when the embedding dimension d is 4, the sentence matrix is a matrix in ℝ^4× 6.



  §.§.§ Convolutional feature maps.

Convolution can be seen as a special kind of linear operation and aimed to extract local patterns. 
We use the one-dimensional convolution to recognize discriminative word sequences from the input sentences. 
The one-dimensional convolution is an operation between 
two vectors f∈ℝ^m and s∈ℝ^| s|. 
The vector f is called as a filter of size m and the vector s  
is a sequence of size | s|. The specific operation is to take the dot product of 
the vector f with each m-gram sliding along the sequence s and obtain 
a new sequence c where:

    c_j= f^ T s_j-m+1:j.
 
In practice, we usually add a bias b to the dot product result:

    c_j= f^ T s_j-m+1:j+b.
 

There are two types of convolution depending on the allowed range of index j: narrow and wide. 
The narrow type restricts j in the range [m, | s|] and 
the wide type restricts j in the range [1, | s|+m-1]. 
The benefits of wide type over the narrow type in text processing
are discussed in detail in <cit.>. 
Briefly speaking, unlike the narrow convolution 
where words close to margins are seen fewer times, 
wide convolution gives equal attention to all words in the sentence 
and so is better at handling words at margins. 
More importantly, a wide convolution always produces a valid 
non-empty result c even when | s|<m. 
For these reasons, we use wide convolution in our model. 

The sentence matrix S is not just a sequence of single values but a sequence of vectors, 
where the dimension of each vector is d. 
So when we apply the one-dimensional convolution on the sentence matrix S, 
we need a filter bank F∈ℝ^d× m consisting of d filters of size m
and a bias bank B∈ℝ^d consisting of d baises. 
Each row of S is convoluted with the corresponding row of F 
and then the corresponding row of B is added to the convolution result. 
After that, we obtain a matrix C∈ℝ^d× (| s|+m-1):

    conv( S,  F,  B): ℝ^d× | s|→ℝ^d× (| s|+m-1).

The values in filter bank F and bias bank B are parameters optimized during training.
The filter size m is a hyper-parameter of the model. 

In Figure <ref>, 
after applying a 4× 3 filter bank and a bias bank of size 4 on the 4 × 6 sentence matrix, 
we obtain an intermediate matrix of size 4 × 8. 



  §.§.§ Activation function.

To make the network capable of learning non-linear functions, 
a non-linear activation α (·) need to be applied in an element-wise way 
to the output of the preceding layer 
and a matrix A∈ℝ^d× (| s|+m-1) is then obtained:

    α( C): ℝ^d× (| s|+m-1)→ℝ^d× (| s|+m-1).


Popular choices of α (·) include: sigmod, tanh and relu (rectified linear defined as max (0, x)). 
In practice, our experimental results are not very sensitive to the choice of activation,
so we choose relu due to its simplicity and computing efficiency. 
In addition, we can see the bias b in (<ref>) plays the role of setting 
an appropriate threshold for controlling units to be activated. 



  §.§.§ Pooling.

Pooling layer will aggregate the information in the output of preceding layer. 
This operation aims to make the representation more robust and invariant to small translations in the input. 
More importantly, pooling helps to handle inputs with varying size, e.g. processing sentences with uncertain length. 

For a given vector  a∈ℝ^| a|, traditional pooling aggregates it into a single value:

    pooling( a): ℝ^| a|→ℝ.
 

The way of aggregating the information defines two types of pooling operations: average and max. 
Max pooling is used more widely in practice. 
Recently, max pooling has been generalized to k-max pooling <cit.>, 
in which k max values are selected from the vector a and arranged in their original order: 


    k-pooling( a): ℝ^| a|→ℝ^k,
 
where k is a hyper-parameter of the model. 

When we apply k-max pooling on the matrix A, 
each row of A is pooled respectively and we obtain a matrix P∈ℝ^d× k: 

    k-pooling( A): ℝ^d× | a|→ℝ^d× k.


In Figure <ref>, after applying k-max pooling (with k=5) on 
the intermediate matrix of size 4× 8, we obtain a new intermediate matrix of size 4 × 5.



  §.§.§ Multiple feature maps.

After a group of above operations, we obtain the first order representation 
learning to recognize the specific m-grams in the input sentence. 
To obtain higher order representations, we can use a deeper network 
by repeating these operations. The higher order representations can 
capture patterns of the sentence in much longer range. 

Meanwhile, we can also extend network to learning multi-aspect representations. 
Let P^i denote the i-th order representation. 
We can compute K_i representations P^i_1,⋯, P^i_K_i 
in parallel at the same i-th order. Each representation P^i_j 
is computed by two steps. 
First, we compute convolution on each representation P^i-1_k at the lower order i-1
with the distinct filter bank F^i_j,k and bias bank B^i_j,k  and then 
sum up the results. 
Second, non-linear activation and k-max pooling are applied to the summation result: 

    P^i_j=k-pooling(α(∑_k=1^K_i-1conv( P^i-1_k,  F^i_j,k,  B^i_j,k))).


In Figure <ref>, there are two representations at the first order and two 
representations at the second order: P^1_1∈ℝ^4× 5,  P^1_2∈ℝ^4× 5 
and P^2_1∈ℝ^4× 3,  P^2_2∈ℝ^4× 3.  



  §.§.§ Full connection.

Full connection is a linear operation 
to combine all representations at the highest order into a single vector. 
More specifically, for the highest order representations 
P^h_1,⋯, P^h_K_h (assume P^h_k∈ℝ^d× l), 
we first flat them into a vector p∈ℝ^K_h× d× l. 
Then we transform it with a dense matrix H∈ℝ^(K_h× d× l)× n:

    x= p^ T H,

where x∈ℝ^n is the final representation vector. 
The values in matrix H are parameters optimized during training. 
The representation size n is a hyper-parameter of the model.

In Figure <ref>, we finally represent the input sentence with 
a vector of size n=5. 







 §.§ Matching items

We compute the compatibility probability between two items 
with function f(·), which is a Siamese Convolutional Neural Network as shown in Figure <ref>. 
 


Siamese setup is introduced by Hadsell et al. <cit.> and used widely in learning distance metrics. 
When designing the amalgamation part of our model, 
we have considered its scalability for big data scenarios, 
which is critical for real-world applications. 



  §.§.§ Style space.
 
For two given items q and c, after generating 
the representation vectors x_q∈ℝ^n and x_c∈ℝ^n
of their title sentences respectively, we compute the compatibility probability between them as follow:

    P(y=1|q,c)   =σ( x_q^ T M x_c+b)
       =1/1+e^-( x_q^ T M x_c+b),

where M∈ℝ^n× n is a matrix and b is a scalar. 
We  call M as the compatibility matrix 
and the space spanned by M as the style space. 
After transformation x'_q= x_q^ T M, 
x'_q represents the item which is most style compatible to q.  
We seek items whose representations are close to x'_q under linear kernel distance. 
The values in compatibility matrix M and the bias b are parameters 
optimized during the training. 

On the other hand, x_q^ T M x_c in (<ref>) can be 
viewed as a noisy-channel model, which has been widely used in the information retrieval and 
QA system <cit.> <cit.>. 



§ RECOMMENDATION

In recommendation applications, 
we are usually given a query item set Q={q_1, q_2,⋯, q_m} 
and a candidate item set C={c_1, c_2,⋯,c_n}, 
where the query item set is relatively small and the candidate item set is usually very large. 
For each query item q_i, we intend to query its K most complementary items from 
the candidate set C and rank them from high compatibility to low compatibility. 
When the item candidate set is very large, 
it is inefficient and even unacceptable to compute the compatibility for all item pairs (q_i,c_j) and then sort them. 

Our approach can be easily extended to handle these big data scenarios.
Given two items q and c, we first generate their representation vectors x_q and x_c respectively. 
Then their compatibility probability is computed according to (<ref>). 
We notice that the function σ (·) in (<ref>) is a monotonic increasing function and b is a learned constant. 
Thus for a query item q and two candidate items c_1, c_2, we have: 

    P(y=1|q,c_1)   ≤ P(y=1|q,c_2) 
    ⇔ x_q^ T M x_c_1   ≤ x_q^ T M x_c_2.


Based on this property, we transform the original problem of querying the K most complementary items 
of q from the item candidate set C 
into another problem, namely searching K nearest neighbors of x' (x'_q= x_q^ T M) 
from { x_c_1, ⋯,  x_c_n} under the linear kernel distance. 
It is well known as Maximum Inner Product Search (MIPS). 
There are many methods solving MIPS efficiently on the large scale data, 
such as tree techniques <cit.> and 
hashing techniques <cit.> <cit.> etc.  







§ TRAINING

We train the model to maximize the likelihood of a observed relationship training set ℛ, 
where r_ij∈ℛ: 

    r_ij=
    1    , if items  i and  j are compatible;
     
    0    , otherwise.
 
Maximizing the likelihood is equal to minimizing the binary-cross entropy loss function:

    L=-∑_r_ij∈ℛ[r_ijlog(p)
    
    +(1-r_ij)log(1-p)],

where p=P(y=1|i,j). 

The parameters to be optimized in our network are θ_1,θ_2, which have been mentioned above:

    θ_1={ W,  F,  B,  H} and θ_2={ M, b},

namely the word embeddings matrix W, filter bank F, bias bank B, 
dense matrix H, compatibility matrix M and compatibility bias b. 
Note that there are multiple filter banks and bias banks to be learned. 

In the following sections, we present several crucial details for training our deep learning model. 


 §.§ Regularization

To alleviate the overfitting issue, we use a popular and efficient regularization 
technique named dropout <cit.>. 
Dropout is applied to the flatted vector p (presented in (<ref>)) before 
transforming it with the dense matrix H. 
A portion of units in p are randomly dropped out by setting them to zero 
during the forward phase, which is helpful for preventing the feature co-adaptation. 
The dropout rate is a hyper-parameters of the model. 



 §.§ Hyper-parameters


The hyper-parameters in our deep learning model are set as follows: 
the embedding dimension is d=100; the size of filters at the first order representation is m=3; 
the number of max values selected by k-max pooling at the first order representation is k=5; 
the size of filters at the second order representation is m=2; 
the number of max values selected by k-max pooling at the second order representation is k=3; 
the dimension of the vector used to represent the sentence is n=100; 
the dropout rate is p=0.2. 
What's more, there are K_1=100 representations computed in parallel at the 
first order representation and  K_2=100 representations computed in parallel at the second order representation. 



 §.§ Optimization

To optimize our network, we use the Stochastic Gradient Descent (SGD) algorithm with shuffled mini-batches. 
The parameters are updated through the back propagation framework with Adagrad rule <cit.>. 
The batch size is set to 256 and the network is trained for 20 epochs. 
The training progress will be early stopped if there is no more update 
to the best loss on the validation set for the last 5 epochs. 

We train our network on a GPU for speeding up. 
A Python implementation using Keras[http://keras.io] 
powered by Theano <cit.> 
can process 428k text pairs per minute on a single NVIDIA K2200 GPU. 



§ EXPERIMENTS

We evaluate our method on two large datasets: 
a Chinese dataset from Taobao and an English dataset from Amazon. 


 §.§ Datasets



  §.§.§ Taobao.
 This dataset is collected from Taobao.com and provide 
by Alibaba Group[http://tianchi.aliyun.com/datalab/index.htm]. 
It includes a Clothing category and there are about 406k compatibility relationships covering 61k items. 
The compatibility relationships in this dataset are labelled 
manually by clothes collocation experts. 



  §.§.§ Amazon.
 This dataset is collected from Amazon.com and provided by <cit.>. 
Though it includes multiple categories, 
in order to investigate the performance of our approach on both datasets, 
we mainly focus on the Clothing category. 
In this category, there are about 12 million compatibility relationships covering 662k items. 
Unlike the Taobao dataset, the compatibility relationships in Amazon dataset are not labelled manually. They are the co-purchase data from Amazon's recommendations <cit.>. 



 §.§ Setup

Our goal is to differentiate compatibility relationships from non-compatibility ones. 
We consider all positive relationships (compatibility) and generate random non-relationship distractors 
of the equal size. That is to say the ratio between positive and negative samples in the dataset is 50:50. 
Then we separate the whole dataset into training, validation and testing sets according to the ratios 80:10:10. 
Although we do not expect overfitting to be a serious issue in our experiment with the large training set, we still carefully tune our model on the validation set to avoid overfitting on testing set. We compare our approach against baselines from two aspects: 
visual one and non-visual ones. 



  §.§.§ Visual baseline.
 We take the method in <cit.> as the visual comparison 
since it is also in the end-to-end fashion. 
In particular, we consider the specific setting configured with GoogLeNet 
and naive sampling for two considerations. First, in all situations of their experiments, 
GoogLeNet <cit.> outperforms AlexNet <cit.>. 
Second, naive sampling means sampling randomly from the dataset, 
which is consistent with the setup in our experiments. 
We experiment their method on the Taobao dataset and 
take the results on the Amazon dataset directly from <cit.>.



  §.§.§ Non-visual baselines.
 We take three methods as the non-visual comparison:

1) Naive Bayes on Bag of Words (NBBW). We treat the title sentences from an item pair as the bag-of-words and 
feed Naive Bayes classifier with it as the feature vector; 

2) Random Forest on Bag of Words (RFBW). Random Forest is capable of modeling extremely complex classification surface. 
We apply Random Forest classifier on the bag-of-words representation of the title sentences from an item pair; 

3) Random Forest on Topic Model (RFTM). 
For the given item pair {q, c}, we first generate the topic representations x_q,  x_c of items q,c 
by LDA model <cit.> respectively, where the topic number is set as 100. 
Then we concatenate them into a single feature vector x_q,c and process Random Forest classifier on it.  

The implementation of Naive Bayes and Random Forest is taken from scikit-learn <cit.>. 
We turned their parameters to obtaine the best loss on the validation set. 

There is no preprocess on images and texts. All results reported in the following section is on the testing set. 



 §.§ Results



  §.§.§ Comparison to baselines.

Tabel <ref> shows the corresponding areas under the ROC curves of compatibility prediction on the testing set . 
The results show clearly that our approach outperforms all other baselines. 



The visual method collapses on the Taobao dataset because 
unlike Amazon, Taobao is a Consumer to Consumer (C2C) platform and 
has few strict requirement about quality of item images uploaded by users. 
A majority of images are like Figure <ref>, 
where the information is mixed up and confusing to learning machines. 
In contrast, the title description is a highly condensed collection of more attributes besides appearances 
with few noises. When using title descriptions, 
a simple method like Naive Bayes on Bag of Words can 
achieve an acceptable performance and 
a more sophisticated method like Random Forest on Bag of Words 
can generate competitive results. 
However, using topic models on title descriptions is not a good idea since most title descriptions are short texts. One important reason why our approach achieves better performance 
is that our approach can recognize specific m-grams and  
more complicated patterns not captured by bag-of-words models. 
For instance, the complementary styles of the item titled with 
“white shirt with blue stripes” and “blue shirt with white stripes” 
are very different, but they have the same bag-of-words representation. 

The performance upper bound of our approach on Taobao dataset is 
limited by the segmentation quality of Chinese. This is one of the reasons that all AUC scores on 
the Taobao dataset are lower than that on the Amazon dataset. 



  §.§.§ Tuning sentence model.

There are several crucial setups in the sentence model: 
1) the word embedding dimension d; 
2) the sentence representation dimension n;
3) whether the word embedding matrix W is initialized or not. 



We show the first ten epochs of training processes of our model on the Taobao dataset with sentence models under different setups in 
Figure <ref>, where the standard setup means that we set d=100, n=100 and 
initialize the word embedding matrix with an unsupervised neural language model <cit.>. 
We can see that the setup with larger d or n claims better performance. 
Furthermore, the performance can get better when we continue to increase the value of d or n. 
In practice, there is a tradeoff between the performance and resources requirement 
according to specific situations. 
What's more, initializing the word embedding matrix W with an unsupervised neural language model 
is indeed benefit to the convergence rate and the final performance. 



 §.§ Discussion




  §.§.§ Toward general match.

While the previous section mainly focuses on clothes matching, 
we also train classifiers on the other twenty top-level categories from the Amazon dataset 
and present the results in Table <ref>. 
As can be seen, we obtain good accuracy in predicting compatibility relationships in 
a variety of categories. 
What's more, we have also tried to train a single model to predict compatibility relationships for all categories. 
There appears to be no “silver bullet” and the result is dissatisfactory: the AUC score of that single model is only 0.694. 

The comparison across categories is particularly interesting. 
Our approach performs relatively poor on the categories “CDs & Vinyl” 
and “Digital Music” since the content of music is too rich to be 
described very clearly in a short title description. 
In contrast, the title description is long enough to describe 
an item from the category `Musical Instruments' clearly and thus our approach performs very well on that. 
In a word, the better titles can describe the attributes of items in a category, 
the higher performance can be achieved on that category by our approach. 



§ CONCLUSIONS

In this paper, we present a novel approach to model the human 
sense of style compatibility between items. 
The basic assumption of our approach is that most of the important attributes for 
a product in an online store are included in its title description. 
We design a Siamese Convolutional Neural Network architecture to 
map the title descriptions of an item pair from the original space of symbolic words into some embedded style space. 
The compatibility probability between items can be then computed in the style space. 
Our approach takes only words as the input with few preprocessing and 
requires no laborious and expensive feature engineering. 
Moreover, it can be easily extended to big data scenarios with KNN searching techniques. 
The experiments on two large datasets confirm our assumption and 
show the possibility of modeling the human sense of style compatibility.  

There are several interesting problems to be investigated in our future work: 
(1) we would like to use more sophisticated sentence models 
without injuring the simplicity of our approach; 
(2) we are wondering whether it is possible to use the text and image information simultaneously, 
e.g. hybrid model or mapping the texts and images of items into the same embedded space 
for mutual retrieval and matching. 




§ ACKNOWLEDGMENTS

We would like to thank Alibaba Group and Julian McAuley for providing the valuable datasets. 
This work is supported by Zhejiang Provincial Natural Science Foundation of China (Grant no. LZ13F020001), 
Zhejiang Provincial Soft Science Project (Grant no. 2015C25053), 
National Science Foundation of China (Grant nos. 61173185, 61173186).
aaai
  

