A Method of User Preference Elicitation by Pairwise Comparisons

Abstract

-In this paper, we consider the problem of reconstructing functions defined implicitly by the results of pairwise comparisons. In the proposed approach, we apply an adaptive transformation to the high-dimensional space. Then we classify the comparisons using linear or non-linear classifiers. In this work, we consider linear regression and random forest as classification algorithms. In experimental analysis, we compare different methods of transformation to the high-dimensional space and investigate the effectiveness of the proposed method.

Keywords

• utility preferences elicitation
• learning

-

function, pairwise preference comparisons, function, machine

I. INTRODUCTION

The method of pairwise comparisons is one of the methods used in recommendation systems. Analyzing pairwise comparisons, we try to determine some pattern in the choice of the preferred option. The method of pairwise comparisons uses information about comparing pairs of objects, in contrast to the classical methods of machine learning, which use data about a specific object [ 1-4 ]. The task of providing recommendations for a particular user is the task of preference elicitation.

Three main types of tasks are specified according to different types of objects and classes [ 3,5 ]:

- label ranking – search for preferred ordering among labels for any example. The traditional classification problem can be generalized as part of the label ranking problem when the classification result of the example is a label of the highest rank;

- instance ranking – ranking a set of examples for a fixed label order;

- object ranking – similar to ranking examples, however, labels are not associated with examples.

In this paper, we consider the task of ranking objects where the objects may be the transport routes proposed by the recommender system [ 6,7 ], and the preferences are the routes selected by the user. In the second section of the paper, we briefly describe the existing approaches to the construction of recommender systems. In the third section, we give the problem formulation and problem statement. The fourth section describes the method of pairwise comparisons. The fifth section shows the results of experimental studies. At the end of the work, conclusions and possible directions for further research are presented.  j and  j  i . In the case  i   j   j   i , the objects are indistinguishable and ≪ . Absolute preference is characterized by utility function u :   R , and relative preference is described by preference function p :     R . For utility function u  i   u  j  denote as  i  j , u  i   u  j    i   j

and ( ) = ( ) ⇔ ≪ .

For preference function p  i , j   0 denote as  i  j and ( , ) = 0 ⇔ ≪ . The preference function has restrictions based on the properties of the corresponding order relations such as asymmetry in argument, transitivity, etc.

A preference function can be defined through a utility function p  j , i   u  j   u  i  and u  j   p  j , *   u  *   p  * , *   0  .

Objects are defined by the feature vector x  x    X of N-dimensional space. The utility and preference function will be written as p  x , x j  , u  x  .

Let x j  x  j  and p ij  p  i , j  , u j  u  j  to shorten the record.

Information about pairwise comparisons can be presented in the form of values of the preference function p  j ,  i  or in the form of a symbolic representation:  1,   z ij  z  j ,  i    0 ,    1,  p  j ,  i   0 , p  j ,  i   0 , . p  j ,  i   0 .

The choice of a specific route from the route list proposed by the system is an example of information on paired comparisons in a transport recommendation system.

The number of incorrectly reconstructed relationships, the Kendall distance for pairwise comparisons, is a criterion for the reconstruction quality of the preference and utility function: d   (i , j ) : z  i , j   z  x  i  , x  j   , (i , j )  I  , This value in the normalized form is an estimate of the corresponding relation errors probability d  d  I 1 .

IV. METHOD

A. Pairwise Comparison Method

Pair comparison methods were initially used to range objects that cannot be described by a feature vector. Each element of the matrix  c ij  is the absolute frequency of the i-th object over j-th [ 14 ]. To analyze such data, the Thurstone model was proposed [ 15 ], in which it is assumed that the utility of an object is determined by a normally distributed random variable. Thus, for objects  0 , 1 we get f u  u  j     j , 2j  , which with u  1   u  0 

   1   0 , 120  ,  120   12   02  2  10 1  0 and the Laplace function  

 we get: P  1  0   P  u  1   u  0   0      1   0  .   10 

In the numerical estimation of the probability (5) as the relative frequency of the corresponding preferences calculated using the matrix  c ij  , we have the following estimation:  1   0 ˆ  10   1  с10  .

 с10  с 01 

The simplified Thurstone model assumes the absence of correlation and equal variances in the utility function, which can be represented as:  12   02  0 .5 ,  10  0 ,  120  1 .

Another featureless method is the Bradley-Terry model. [ 1 ]. Estimating the probability (5) in the following form:  1  1   0 P  1  0   ,  j  e x p   j s  , where s is a numerical non-negative parameter. Thus, we have the following estimate of the preferences between the objects:  1   0 ˆ s  ln  с10 с10 с 01   ln  1  с10   .

 с10  с 01  

The analytic hierarchy process (AHP) is used for the multicriteria ranking of objects that are defined by features. In this case, at the initial step matrices  m inj  i , j J , n  0 , N  1 are calculated. Each element of the matrix is the result of a user response regarding the preferences of the i-th object over the jth objects according to the n-th criterion. The resulting utility N 1 of the objects as a scalar product u  j    w n v nj , where n  0 v n   v 0n ,

T , v nJ 1  is the right eigenvector of the preference matrix, and w – eigenvector of the matrix of alternatives. The main problem of this method is a large number of pairwise comparisons. Therefore, in practice, they often use a model

N 1 u  x      w n  v n  x n    , based on a generalized additive n  0 model.

B. Proposed method description

The following features should be considered reconstructing the utility function and preference function: when - reconstruction of functions is practically impossible with a small amount of information or in its absence, as in the case of a system cold start;

- it must be able to automatically transform to nonlinear models. Classes will be separable almost surely when using transformation the original features space to a new feature space Y with a higher dimension;

- the regression task of reconstructing the utility function can be reduced to the classification problem by reconstructing the symbolic representation.

The method of function reconstruction by their symbolic representation contains the following steps: – feature values normalization in the range [ 0,1 ]; – selection of a new feature space (basis) Y; – transformation of the original feature vector x into the new feature space Y with a higher dimension K=dim(Y)  N; – building a linear or nonlinear classifier in the feature space Y;

– quality assessment of the building classifier on the test dataset.

In the case when the evaluation of the preference function is unsatisfactory, go to the selection of a new basis and transformation of the feature space.

The described steps are presented as a diagram in Fig. 1.

KS synthesis model dimension

Classifier parameters for a particular training set  x j , r j  j J are determined from the condition:

J  w    ln 1  e x p   r j  d  x j     m in ,

j J where r j    1,1 – is a random variable of the correct classification that determines the true class of the corresponding j-th object.

A random forest is a voting method implementation of several tree classifiers. A random forest avoids retraining, unlike a decision tree. Each tree is built independently of the rest on a random subset of the training set. The components of the feature vector are selected from a random subset of features for each partition when learning trees.

User decisions may be erroneous, especially with a small difference in the proposed alternatives. Therefore, in this work we use the Thurstone’s model with the probability estimation to add errors in the ideal preferences. For the case  j   i :  z  j ,  i  , z ij     z  j ,  i  , o th e r w is e . 

r n d  P  u  j   u  i   0  , where rnd <R[ 0,1 ] - random variable.

We train and test the model several times, averaging the results of the error calculation, in order to avoid the effect of unsuccessful partitioning of the set on the training and test datasets.

V. EXPERIMENTAL RESEARCH

We used the following parameters during the experiments: – The synthesis model dimension Ks = 15, 35; – The transformation model dimension Ka = 15, 35, 63; – The paired comparisons number InstNum 50000; = 10000,

– The number of random partitions of the dataset nIter = 100.

Comparison of the effectiveness of various bases is presented in Table I.

An increase in the number of pairwise comparisons led to a decrease in the error value, however, it significantly increased the program execution time, especially for the random forest method. We can state, based on the results, that the proposed approach has demonstrated efficiency and effectiveness.

VI. CONCLUSION

The paper proposes an approach to the reconstruction of functions defined implicitly by the results of pairwise comparisons. The approach is based on the transformation into the symbolic space of a greater dimension with the subsequent classification of the comparison results. It is shown that the proposed method allows us to effectively solve the problem of evaluating the user preference function. Logistic regression has a significant advantage in speed and stability. A further area of research is the application of the developed approach on data on preferred routes for users on public and private transport.

ACKNOWLEDGMENT The work was funded by the Ministry of Science and Higher Education of the Russian Federation (unique project identifier RFMEFI57518X0177).

References

[1] R.A. Bradley and M.E. Terry , “ Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons,” Biometrika , vol. 39 , no. 3 /4, pp. 324 - 345 , 1952 . DOI: 10 .2307/2334029.

[2] P.C. Fishburn , “ Utility theory for decision making,” Huntington , N.Y: R.E. Krieger Pub . Co, 1979 .

[3] J. Fürnkranz and E. Hüllermeier, “Preference Learning,” Berlin Heidelberg: Springer-Verlag, 2011 .

[4] K.P. Murphy , “ Machine Learning: A Probabilistic Perspective ,” Cambridge, MA: The MIT Press, 2012 .

[5] V.V. Myasnikov , “ Reconstruction of functions and digital images using sign representations,” Computer Optics , vol. 43 , no. 6 , pp. 1041 - 1052 , 2019 . DOI: 10 .18287/ 2412 -6179-2019-43-6- 1041 -1052.

[6] A.A. Agafonov , A.S. Yumaganov and V.V. Myasnikov , “ Big data analysis in a geoinformatic problem of short-term traffic flow forecasting based on a K nearest neighbors method,” Computer Optics , vol. 42 , no. 6 , pp. 1101 - 1111 , 2018 . DOI: 10 .18287/ 2412 -6179-2018- 42-6- 1101 -1111.

[7] A.A. Agafonov and V.V. Myasnikov , “ Numerical route reservation method in the geoinformatic task of autonomous vehicle routing ,” Computer Optics , vol. 42 , no. 5 , pp. 912 - 920 , 2018 . DOI: 10 .18287/ 2412 -6179-2018-42-5- 912 -920.

[8] Y. Koren , R. Bell and C. Volinsky , “ Matrix Factorization Techniques for Recommender Systems ,” Computer, vol. 42 , no. 8 , pp. 30 - 37 , 2009 . DOI: 10 .1109/ MC . 2009 . 263 .

[9] Z. Cao , T. Qin , T.-Y. Liu, M.-F. Tsai and H. Li , “ Learning to rank: From pairwise approach to listwise approach ,” ACM International Conference Proceeding Series, vol. 227 , pp. 129 - 136 , 2007 . DOI: 10 .1145/1273496.1273513.

[10] T. Joachims , “ Optimizing search engines using clickthrough data , ” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pp. 133 - 142 , 2002 .

[11] X. He , “ Practical lessons from predicting clicks on ads at Facebook,” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , 2014 . DOI: 10 .1145/2648584.2648589.

[12] P. Covington , J. Adams and E. Sargin, “ Deep neural networks for youtube recommendations , ” RecSys - Proceedings of the 10th ACM Conference on Recommender Systems , pp. 191 - 198 , 2016 . DOI: 10 .1145/2959100.2959190.

[13] P. Campigotto , C. Rudloff , M. Leodolter and D. Bauer , “Personalized and Situation-Aware Multimodal Route Recommendations: The FAVOUR Algorithm,” IEEE Transactions on Intelligent Transportation Systems , vol. 18 , no. 1 , pp. 92 - 102 , 2017 . DOI: 10 .1109/TITS. 2016 . 2565643 .

[14] K. Tsukida and M. Gupta , “How to Analyze Paired Comparison Data,” 2011 .

[15] L.L. Thurstone , “ A law of comparative judgment,” Psychological Review , vol. 34 , no. 4 , pp. 273 - 286 , 1927 . DOI: 10 .1037/h0070288.