Anatomy of reference services (Part 1)
We are glad to publish an interesting, in our opinion, article by our friend Nikolai Mikhailovsky (habropoznik nickm197 ). We think that it will be interesting to everyone who works professionally in ecommerce.
Introduction
When we come to potential customers to talk about the crossss personalization service , one of the frequent questions is: “How does it work inside?”. Using the CentroBit friendly blog, I’ll tell you a little about the theory and practice of recommender services.
It turned out that in the course of writing the article began to become too big, so I decided to limit myself now to the first part, after which I will have to write at least one more, or even two.
')
Let's start with the basics and philosophy.
What is personalization?
The tape that you see on Facebook or VKontakte is yours alone, no one else has one. Why do all other sites look the same for me and for you? The answer is that social networks are naturally personalized, while other sites, as a rule, do not.
Thus, the personalization of a website is its automatic adjustment to the current needs of a particular visitor.
In personalization can be divided into two opposing approaches.
The first one is expanding personalization, when on the basis of some knowledge about the user, he is offered additional information that is supposedly useful to him. A typical example is the product recommendations, most often found in online stores, for example, with the inscription "With this product buy."
The second is narrowing personalization. A typical example of this is the Facebook ribbon algorithm, which selects and shows the user only those posts that are supposed to involve him most of all from the flow of friends' posts.
These two approaches solve opposite tasks. The first - offers previously unknown information. The second - on the contrary, saves from overloading information.
What is a recommendation system?
The recommendation system is a software package that determines the interests and preferences of the visitor and gives recommendations in accordance with them.
There are various approaches to the development of recommendation systems, which can be used depending on:
• available data about users and recommended entities
• types of explicit and implicit user feedback
• subject area
At the same time, the purpose of the classical recommendation system is to recommend products that were previously unknown to the user, but are useful or interesting for him in the current context.
In other words, the recommendation system answers the question about a specific site visitor: “Which product will this visitor want to buy right now?”
There may be several different points of view on this main goal of the recommendation system, causing different criteria for evaluating the success of the recommendation system:
From the point of view of the visitor - how much he likes the recommended products. The metrics for this are the quality of the approximation of the estimate or CTR by the recommendation system and the proportion of visitors who bought the recommended product.
From the point of view of an online store or online publication - maximizing the expected income from the user or the depth of viewing.
Paradigms of recommendation systems
The ideal recommendation system for building recommendations uses data about the current user, about the behavior of all users in general, about the properties of the recommended products and about the context of the current interest of the user. So, for example, we act in http://crossss.ru . But for this it is necessary to process huge data arrays, therefore, historically, until such a possibility appeared just a few years ago, recommendation systems used subsets of such an array of data. And today, such systems are still quite common.
I will describe the main approaches to building recommendation systems for online stores and online publications.
Manual recommendations
If you look at the recommendation blocks in Russian online stores, then most of them are manually filled lists of related products. If the product range is small and rarely changes, then this may be a good way out. If he is great, and the connections between the goods are not obvious, then selecting recommendations becomes too time consuming, or they become ineffective.
Content recommendation systems
Systems based solely on the properties of products are called content.
For example, a widely distributed (over 2 million installations) plugin to Wordpress Yet Another Related Posts Plugin (YARPP). In the video http://wordpress.tv/2011/01/29/michael-%E2%80%9Cmitcho%E2%80%9D-erlewine-the-yet-another-related-posts-plugin-algorithm-explained/ author explains the principle of its work.
Another, a purely Russian, and quite unique example of a content recommendation system is Kuznech 's http://similar4.ru/ . It recommended clothing and shoes are selected on the principle of visual similarity to the current subject.
Let us examine in a little more detail how the content recommendation engine is arranged in the open source easyrec recommendation system ( http://easyrec.sourceforge.net ).
In eacyrec, you can embed various recommendation engines as plug-ins into a common framework. This, in particular, is due to the fact that easyrec (apparently) is used as a framework by the commercial system SmartEngine, which has about 10 clients in Russia and a client in Singapore (although the developers are Austrians).
One of the 4 algorithms available in the easyrec open-source delivery is the Product Similarity Calculator ( Profile Similarity Calculator ). For his work requires profiles of goods that store the properties of goods.
Product profiles are described, for example, as follows:
These properties of the goods are loaded by the plugin, and a quick deke duplicator duke is used to calculate the similarity measure for each of the properties of the goods. He uses comparators to compare each of the properties. The comparator must output 0 if the properties are completely different, and 1 if they are identical. For example, if you want to compare two strings, you can use ExactComparator, which returns 1 if the strings are identical, and 0 otherwise. Alternatively, you can use a comparator on Levinshtein distance (specifically put a separate reference to Vladimir Iosifovich), Levinshtein's weighted distance, Yaro-Winkler measure , Q-grams, as well as a variety of specialized measures, starting from numerical to geo-position and phonetic comparison.
From individual measures of the similarity of properties, a general measure of the similarity of goods is derived. For each pair of goods for which the similarity measure exceeds a certain threshold, a recommendation link is established between the goods (if there is such a link between goods A and B, then A is recommended to B, and vice versa).
The pros and cons of such recommendation systems are understandable. On the one hand, they are relatively easy computationally - recalculation of the relevance of items / articles is made when new items are added, which happens infrequently. In this case, all visitors are shown the same recommendations. On the other hand, the assumption that the current page fully defines the user's needs is, in a large number of cases, an exaggeration.
Collaborative Item Filtering (Item-To-Item Collaborative Filtering)
Collaborative filtering (CF) methods generate recommendations based on data about the estimates or use of the goods (buying goods, watching movies, reading articles) without regard to the characteristics of a particular product.
The basis of collaborative filtering of products, as well as the basis of content systems, is the idea that interest in a particular product is an indication that the user will also be interested in another product (as replacing or supplementing the current product). I leave the respected readers to consider the extent to which this assumption is true.
Such methods gained popularity after Amazon employees Greg Linden, Brent Smith and Jeremy York published in IEEE INTERNET COMPUTING in early 2003 a note on the device of Amazon's Amazon.com Recommendations: Item-to-Item Collaborative Filtering.
In order to receive recommendations, the systems of collaborative filtering of goods link two main entities: users and products. The simplest method of communication is the explicitly specified by the user rating (rating) of the goods.
If we have data on the evaluation of goods by different users, then we get a user-product matrix:
Question: what product to recommend, if the user is now looking Product1? The answer given by Item-to-Item CF: one that is most similar to Item1. In a more mathematical language, this means that there is a proximity metric between products based on user ratings.
The simplest measure of proximity is the cosine of the angle between the corresponding valuation vectors for a product by users:
For example, in our case, the cosines between the vector of Commodity 1 and other products are:
Thus, the closest in our metric to Commodity1 is Commodity5.
However, in real-world applications, difficulties begin to arise, for example, due to the fact that different products value a different number of users, and the ratings of each user are often shifted to one of the parties. To get around this problem, you can apply a modified cosine metric:
where U is the set of users who rated both a and b.
Further problems arise when large applications find that only a very small number of products can receive a rating from each user. Thus, it is necessary to add implicit ones to the explicit estimates, based on what products the customer has been viewing for how long, what products they bought, etc. Naturally, the interpretation of implicit data is a more difficult task, and its solution is always approximate, and therefore, leads to the appearance of noise.
Thus, in real problems the matrix is ​​user - the product is obtained
1. Huge
2. Very sparse
3. Noisy
Fortunately, applied mathematics has long known what to do with such matrices. Namely, the singular value decomposition is remarkable in that it optimally approximates a given matrix
another matrix 
lower rank 
.:
where are the matrices
, 
and 
are obtained from the corresponding matrices in the singular decomposition of the matrix circumcision to exactly first columns (matrix elements 
ordered by non-increment).
Thus, we perform a kind of compression of the information contained in . This compression occurs with losses - only the most significant part of the matrix is ​​preserved in the approximation. , and the noise is filtered out. Another glance at such an approximation is that all products are projected into a space of lower dimension in which the distance between them is determined.
A similarly large number of recommender systems works according to this scheme.
In the following series: “How to compare people with refrigerators?”, “What did Yandex lose to Tencent?” And answers to other burning questions.
Introduction
When we come to potential customers to talk about the crossss personalization service , one of the frequent questions is: “How does it work inside?”. Using the CentroBit friendly blog, I’ll tell you a little about the theory and practice of recommender services.
It turned out that in the course of writing the article began to become too big, so I decided to limit myself now to the first part, after which I will have to write at least one more, or even two.
')
Let's start with the basics and philosophy.
What is personalization?
“If I have 3 million customers on the Web, I should have 3 million stores on the Web.”
–Jeff Bezos, CEO of Amazon.comThe tape that you see on Facebook or VKontakte is yours alone, no one else has one. Why do all other sites look the same for me and for you? The answer is that social networks are naturally personalized, while other sites, as a rule, do not.
Thus, the personalization of a website is its automatic adjustment to the current needs of a particular visitor.
In personalization can be divided into two opposing approaches.
The first one is expanding personalization, when on the basis of some knowledge about the user, he is offered additional information that is supposedly useful to him. A typical example is the product recommendations, most often found in online stores, for example, with the inscription "With this product buy."The second is narrowing personalization. A typical example of this is the Facebook ribbon algorithm, which selects and shows the user only those posts that are supposed to involve him most of all from the flow of friends' posts.
These two approaches solve opposite tasks. The first - offers previously unknown information. The second - on the contrary, saves from overloading information.
What is a recommendation system?
The recommendation system is a software package that determines the interests and preferences of the visitor and gives recommendations in accordance with them.
There are various approaches to the development of recommendation systems, which can be used depending on:
• available data about users and recommended entities
• types of explicit and implicit user feedback
• subject area
At the same time, the purpose of the classical recommendation system is to recommend products that were previously unknown to the user, but are useful or interesting for him in the current context.
In other words, the recommendation system answers the question about a specific site visitor: “Which product will this visitor want to buy right now?”
There may be several different points of view on this main goal of the recommendation system, causing different criteria for evaluating the success of the recommendation system:
From the point of view of the visitor - how much he likes the recommended products. The metrics for this are the quality of the approximation of the estimate or CTR by the recommendation system and the proportion of visitors who bought the recommended product.
From the point of view of an online store or online publication - maximizing the expected income from the user or the depth of viewing.
Paradigms of recommendation systems
The ideal recommendation system for building recommendations uses data about the current user, about the behavior of all users in general, about the properties of the recommended products and about the context of the current interest of the user. So, for example, we act in http://crossss.ru . But for this it is necessary to process huge data arrays, therefore, historically, until such a possibility appeared just a few years ago, recommendation systems used subsets of such an array of data. And today, such systems are still quite common.
I will describe the main approaches to building recommendation systems for online stores and online publications.
Manual recommendations
If you look at the recommendation blocks in Russian online stores, then most of them are manually filled lists of related products. If the product range is small and rarely changes, then this may be a good way out. If he is great, and the connections between the goods are not obvious, then selecting recommendations becomes too time consuming, or they become ineffective.
Content recommendation systems
Systems based solely on the properties of products are called content.
For example, a widely distributed (over 2 million installations) plugin to Wordpress Yet Another Related Posts Plugin (YARPP). In the video http://wordpress.tv/2011/01/29/michael-%E2%80%9Cmitcho%E2%80%9D-erlewine-the-yet-another-related-posts-plugin-algorithm-explained/ author explains the principle of its work.
Another, a purely Russian, and quite unique example of a content recommendation system is Kuznech 's http://similar4.ru/ . It recommended clothing and shoes are selected on the principle of visual similarity to the current subject.
Let us examine in a little more detail how the content recommendation engine is arranged in the open source easyrec recommendation system ( http://easyrec.sourceforge.net ).
In eacyrec, you can embed various recommendation engines as plug-ins into a common framework. This, in particular, is due to the fact that easyrec (apparently) is used as a framework by the commercial system SmartEngine, which has about 10 clients in Russia and a client in Singapore (although the developers are Austrians).
One of the 4 algorithms available in the easyrec open-source delivery is the Product Similarity Calculator ( Profile Similarity Calculator ). For his work requires profiles of goods that store the properties of goods.
Product profiles are described, for example, as follows:
These properties of the goods are loaded by the plugin, and a quick deke duplicator duke is used to calculate the similarity measure for each of the properties of the goods. He uses comparators to compare each of the properties. The comparator must output 0 if the properties are completely different, and 1 if they are identical. For example, if you want to compare two strings, you can use ExactComparator, which returns 1 if the strings are identical, and 0 otherwise. Alternatively, you can use a comparator on Levinshtein distance (specifically put a separate reference to Vladimir Iosifovich), Levinshtein's weighted distance, Yaro-Winkler measure , Q-grams, as well as a variety of specialized measures, starting from numerical to geo-position and phonetic comparison.
From individual measures of the similarity of properties, a general measure of the similarity of goods is derived. For each pair of goods for which the similarity measure exceeds a certain threshold, a recommendation link is established between the goods (if there is such a link between goods A and B, then A is recommended to B, and vice versa).
The pros and cons of such recommendation systems are understandable. On the one hand, they are relatively easy computationally - recalculation of the relevance of items / articles is made when new items are added, which happens infrequently. In this case, all visitors are shown the same recommendations. On the other hand, the assumption that the current page fully defines the user's needs is, in a large number of cases, an exaggeration.
Collaborative Item Filtering (Item-To-Item Collaborative Filtering)
Collaborative filtering (CF) methods generate recommendations based on data about the estimates or use of the goods (buying goods, watching movies, reading articles) without regard to the characteristics of a particular product.
The basis of collaborative filtering of products, as well as the basis of content systems, is the idea that interest in a particular product is an indication that the user will also be interested in another product (as replacing or supplementing the current product). I leave the respected readers to consider the extent to which this assumption is true.
Such methods gained popularity after Amazon employees Greg Linden, Brent Smith and Jeremy York published in IEEE INTERNET COMPUTING in early 2003 a note on the device of Amazon's Amazon.com Recommendations: Item-to-Item Collaborative Filtering.
In order to receive recommendations, the systems of collaborative filtering of goods link two main entities: users and products. The simplest method of communication is the explicitly specified by the user rating (rating) of the goods.
If we have data on the evaluation of goods by different users, then we get a user-product matrix:
Question: what product to recommend, if the user is now looking Product1? The answer given by Item-to-Item CF: one that is most similar to Item1. In a more mathematical language, this means that there is a proximity metric between products based on user ratings.
The simplest measure of proximity is the cosine of the angle between the corresponding valuation vectors for a product by users:
For example, in our case, the cosines between the vector of Commodity 1 and other products are:
Thus, the closest in our metric to Commodity1 is Commodity5.
However, in real-world applications, difficulties begin to arise, for example, due to the fact that different products value a different number of users, and the ratings of each user are often shifted to one of the parties. To get around this problem, you can apply a modified cosine metric:
where U is the set of users who rated both a and b.
Further problems arise when large applications find that only a very small number of products can receive a rating from each user. Thus, it is necessary to add implicit ones to the explicit estimates, based on what products the customer has been viewing for how long, what products they bought, etc. Naturally, the interpretation of implicit data is a more difficult task, and its solution is always approximate, and therefore, leads to the appearance of noise.
Thus, in real problems the matrix is ​​user - the product is obtained
1. Huge
2. Very sparse
3. Noisy
Fortunately, applied mathematics has long known what to do with such matrices. Namely, the singular value decomposition is remarkable in that it optimally approximates a given matrix
another matrix lower rank .:where are the matrices
, and are obtained from the corresponding matrices in the singular decomposition of the matrix circumcision to exactly first columns (matrix elements ordered by non-increment).Thus, we perform a kind of compression of the information contained in
. This compression occurs with losses - only the most significant part of the matrix is ​​preserved in the approximation. , and the noise is filtered out. Another glance at such an approximation is that all products are projected into a space of lower dimension in which the distance between them is determined.A similarly large number of recommender systems works according to this scheme.
In the following series: “How to compare people with refrigerators?”, “What did Yandex lose to Tencent?” And answers to other burning questions.
Source: https://habr.com/ru/post/193960/
All Articles