TY - GEN
T1 - A scalable preference elicitation algorithm using group generalized binary search
AU - Ren, Yi
AU - Scott, Clayton
AU - Papalambros, Panos Y.
PY - 2013
Y1 - 2013
N2 - We examine the problem of eliciting the most preferred designs of a user from a finite set of designs through iterative pairwise comparisons presented to the user. The key challenge is to select proper queries (i.e., presentations of design pairs to the user) in order to minimize the number of queries. Previous work formulated elicitation as a blackbox optimization problem with comparison (binary) outputs, and a heuristic search algorithm similar to Efficient Global Optimization (EGO) was used to solve it. In this paper, we propose a query algorithm that minimizes the expected number of queries directly, assuming that designs are embedded in a known space and user preference is a linear function of design variables. Besides its theoretical foundation, the proposed algorithm shows empirical performance better than the EGO search algorithm in both simulated and real-user experiments. A novel approximation scheme is also introduced to alleviate the scalability issue of the proposed algorithm, making it tractable for a large number of design variables or of candidate designs.
AB - We examine the problem of eliciting the most preferred designs of a user from a finite set of designs through iterative pairwise comparisons presented to the user. The key challenge is to select proper queries (i.e., presentations of design pairs to the user) in order to minimize the number of queries. Previous work formulated elicitation as a blackbox optimization problem with comparison (binary) outputs, and a heuristic search algorithm similar to Efficient Global Optimization (EGO) was used to solve it. In this paper, we propose a query algorithm that minimizes the expected number of queries directly, assuming that designs are embedded in a known space and user preference is a linear function of design variables. Besides its theoretical foundation, the proposed algorithm shows empirical performance better than the EGO search algorithm in both simulated and real-user experiments. A novel approximation scheme is also introduced to alleviate the scalability issue of the proposed algorithm, making it tractable for a large number of design variables or of candidate designs.
UR - http://www.scopus.com/inward/record.url?scp=84896963136&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84896963136&partnerID=8YFLogxK
U2 - 10.1115/DETC2013-13059
DO - 10.1115/DETC2013-13059
M3 - Conference contribution
AN - SCOPUS:84896963136
SN - 9780791855898
T3 - Proceedings of the ASME Design Engineering Technical Conference
BT - 39th Design Automation Conference
PB - American Society of Mechanical Engineers
T2 - ASME 2013 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, IDETC/CIE 2013
Y2 - 4 August 2013 through 7 August 2013
ER -