Understanding SpringRank through Random Utility Models, Identifiability, and Online Updates

Venkateswaran, Aparajithan

Undergraduate Honors Thesis

Understanding SpringRank through Random Utility Models, Identifiability, and Online Updates 公开 Deposited

Analytics

下载PDF文件

Citations

Citeable URL: https://scholar.colorado.edu/concern/undergraduate_honors_theses/2227mr24m

Abstract

A special class of complex systems arises when the agents involved are in competition with one another. The outcomes of these interactions make it possible to reveal a latent ordinal hierarchy of the entities in the system. SpringRank is a ranking method that models the network as a physical system comprised of springs. It estimates ranks as locations of the springs that minimize the total energy of the system.

This thesis explores SpringRank in three ways, two of which are extensions to the model. Firstly, we make connections between SpringRank and the Boltzmann distribution, Random Utility Models, and linear regression. We characterize SpringRank as a Random Utility Model by using the Boltzmann distribution to notice that SpringRank makes a decision between the choices itself as opposed to the choice items. We reconcile an ordinary least squares interpretation of SpringRank with the results from the Boltzmann distribution. We conclude that various interpretations of SpringRank o er the same insights but in di erent ways. Secondly, we extend SpringRank to identify the e ect of group characteristics on the outcomes of interactions. We develop three models { two where group memberships are xed and one where group memberships can change. The two models when group memberships are xed correspond to cases where the group e ects stay constant or are allowed to change. Both these models are non-identi able { we cannot identify the e ect of group characteristics. We recover identi ability in the third model. Finally, we propose an online update algorithm to accurately and eciently update ranks inferred by SpringRank. Our algorithm forces boundary conditions and only updates a small neighborhood. This algorithm fails the accuracy-eciency trade-o as it is computationally expensive. Instead, we suggest other possible online update mechanisms.

Creator