�ݺ�ߣ

GESIS - Leibniz Institute for the Social Sciences
HypTrails: A Bayesian Approach for Comparing
Hypotheses about Human Trails on the Web
Philipp Singer, Denis Helic, Andreas Hotho
and Markus Strohmaier
www.philippsinger.info/hyptrails

Vannevar Bush
227.05.2015 HypTrails - Philipp Singer
image courtesy of brucesterling on Flickr
Bush, V. (1945). As we may think. The Atlantic
Monthly, 176(1):101– 108. Bush, V. (1945).
As we may think. The Atlantic Monthly,
176(1):101– 108.
“[The human brain] operates by association.
With one item in its grasp, it snaps instantly to the
next that is suggested by the association of thoughts.”

Human trails on the Web
27.05.2015 HypTrails - Philipp Singer 3
image courtesy of user Mmxx on Wikipedia

Human trails on the Web
image courtesy of user Mmxx on Wikipedia
?
?
?
?
?
What are the mechanisms
producing human trails on
the Web?

Example: Human navigational trails
• Humans prefer to navigate …
– H1: over semantically similar websites
– H2: via self-loops (e.g., refreshing)
– H3: by using the structural link network
– H4: by preferring similar categories
– H5: by utilizing structural properties
– H6: by information scent
[West et al. IJCAI 2009], [Singer et al. IJSWIS 2013], [West & Leskovec WWW 2012], [Chi et al. CHI 2001]

Example: Human navigational trails
• Humans prefer to navigate …
– H1: over semantically similar websites
– H2: via self-loops (e.g., refreshing)
– H3: by using the structural link network
– H4: by preferring similar categories
– H5: by utilizing structural properties
– H6: by information scent
[West et al. IJCAI 2009], [Singer et al. IJSWIS 2013], [West & Leskovec WWW 2012], [Chi et al. CHI 2001]
What is the relative
plausibility of these
hypotheses given data?

HypTrails in a nutshell
• Goal: Express and compare hypotheses about human trails
in a coherent research approach
• Method:
– First-order Markov chain model
– Bayesian inference
• Idea:
– Incorporate hypotheses as priors
– Utilize sensitivity of marginal likelihood on the prior
• Outcome: Partial ordering of hypotheses

Markov chain model
• Stochastic model
• Transition probabilities between states
S1
S2 S3
1/2 1/2
1/3
2/3
1

Structure of HypTrails
MC Model

How to express hypotheses?

Structural hypothesis
1/3
1
1/3
1
1/3

Uniform hypothesis
1/3

Empirical observations
1.0
2/3
1/3
1

MC Model
Hypothesis
(H1)
Belief in parameters

Which hypothesis is
the most plausible one?

Bayesian model comparison:
Marginal likelihood
Probability of data given hypothesis
= Model evidence

Marginal likelihood
Model evidence
Parameters are marginalized out
Probability of observing data
given parameters and hypothesis

Marginal likelihood
Model evidence
given parameters and hypothesis Probability of parameters
before observing data

Marginal likelihood
Model evidence
given parameters and hypothesis Probability of parameters
before observing data
Hypothesis

MC Model
Hypothesis
(H1)
Belief in parameters
Prior (H1)
Elicitation
Data (Trails)
Marginal
likelihood (H1)
Influence
Influence

How to elicit priors from hypotheses?

Eliciting priors
• (Trial) roulette method

Eliciting priors

Prior distribution
Eliciting priors

Conjugate Dirichlet prior
• Hyperparameters  pseudo counts
MC parameters Dirichlet hyperparameters

Eliciting priors from hypotheses
about human trails
• Adaption of (trial) roulette method
#Chips = β
Strength of hypothesis
β = 18

Eliciting priors from hypotheses
about human trails
• Adaption of (trial) roulette method
#Chips = β
Strength of hypothesis
β = 18
 Dirichlet hyperparameters

Example: Structural hypothesis
1/3
1
1/3
1
1/3

®i
1
2
3 ®j
1
2
3
nr.ofchips
1
2
3
0.00 0.33 0.00 h3
1.00 0.33 1.00 h2
0.00 0.33 0.00 h1
h3 h2 h1
®i
1
2
3 ®j
1
2
3
nr.ofchips
1
2
3
0.00 0.99 0.00 h3
3.01 0.99 3.01 h2
0.00 0.99 0.00 h1
h3 h2 h1
®i
1
2
3 ®j
1
2
3
nr.ofchips
1
2
3
0.00 0.99 0.00 h3
0.01 0.99 0.01 h2
0.00 0.99 0.00 h1
h3 h2 h1
Input
Hypothesis
Output
Dirichlet prior

®i
1
2
3 ®j
1
2
3
nr.ofchips
1
2
3
0.00 0.33 0.00 h3
1.00 0.33 1.00 h2
0.00 0.33 0.00 h1
h3 h2 h1
®i
1
2
3 ®j
1
2
3
nr.ofchips
1
2
3
0.00 0.99 0.00 h3
3.01 0.99 3.01 h2
0.00 0.99 0.00 h1
h3 h2 h1
®i
1
2
3 ®j
1
2
3
nr.ofchips
1
2
3
0.00 0.99 0.00 h3
0.01 0.99 0.01 h2
0.00 0.99 0.00 h1
h3 h2 h1

MC Model
Hypothesis
(H1)
Prior (H1)
Data (Trails)
Marginal
likelihood (H1)
Hypothesis
(H2)
Prior (H2)
Marginal
likelihood (H2)
Compare

Demonstration of general applicability
• Synthetic data
• Human song trails (Last.fm)
• Human review trails (Yelp)
• Human navigation trails (Wikigame)

Wikigame
0 1 2 3 4
hypothesis weighting factor k
−1.40
−1.35
−1.30
−1.25
−1.20
−1.15
−1.10
−1.05
−1.00
−0.95
evidence
1e8
uniform
self-loop
structural
similarity
Higher
plausibility
Higher belief
(more chips)

Wikigame
0 1 2 3 4
hypothesis weighting factor k
−1.40
−1.35
−1.30
−1.25
−1.20
−1.15
−1.10
−1.05
−1.00
−0.95
evidence
1e8
uniform
self-loop
structural
similarity

Summary
• Studying mechanisms producing human trails
• HypTrails: A coherent approach for expressing and
comparing hypotheses about human trails
• Can be applied to all kinds of human trails
• Implementations: www.philippsinger.info/hyptrails

GESIS - Leibniz Institute for the Social Sciences
for your attention!
@ph_singer
www.philippsinger.info
T
H
A
N
K
S
www.philippsinger.info/hyptrails

References 1/2
• [West et al. WWW 2015]
– Robert West, Ashwin Paranjape, and Jure Leskovec: Mining Missing Hyperlinks from Human
Navigation Traces: A Case Study of Wikipedia. 24th International World Wide Web Conference
(WWW'15), Florence, Italy, 2015.
• [De Choudhury et al. HT 2010]
– De Choudhury, Munmun and Feldman, Moran and Amer-Yahia, Sihem and Golbandi, Nadav and
Lempel, Ronny and Yu, Cong: Automatic construction of travel itineraries using social breadcrumbs.
21st ACM conference on Hypertext and hypermedia, 2010.
• [Bestavros CIKM 1995]
– Bestavros, Azer: Using speculation to reduce server load and service time on the WWW.” 4th International conference
on Information and knowledge management. 1995.
• [Perkowitz IJCAI 1997]
– Perkowitz, Mike, and Oren Etzioni: Adaptive web sites: an AI challenge. 15th international joint
conference on Artifical intelligence. 1997.
• [West et al. IJCAI 2009]
– West, Robert, Joelle Pineau, and Doina Precup. "Wikispeedia: An Online Game for Inferring Semantic
Distances between Concepts." IJCAI. 2009.

References 2/2
• [Singer et al. IJSWIS 2013]
– Philipp Singer, Thomas Niebler, Markus Strohmaier and Andreas Hotho, Computing Semantic
Relatedness from Human Navigational Paths: A Case Study on Wikipedia, International Journal on
Semantic Web and Information Systems (IJSWIS), vol 9(4), 41-70, 2013
• [West & Leskovec WWW 2012]
– Robert West and Jure Leskovec: Human Wayfinding in Information Networks 21st International
World Wide Web Conference (WWW'12), pp. 619–628, Lyon, France, 2012.
• [Chi et al. CHI 2001]
– Chi, Ed H., et al. "Using information scent to model user information needs and actions and the
Web." Proceedings of the SIGCHI conference on Human factors in computing systems. ACM, 2001.

�ݺ�ߣ

HypTrails: A Bayesian Approach for Comparing Hypotheses about Human Trails on the Web

Recommended

More Related Content

Similar to HypTrails: A Bayesian Approach for Comparing Hypotheses about Human Trails on the Web (20)

Recently uploaded (20)

HypTrails: A Bayesian Approach for Comparing Hypotheses about Human Trails on the Web