-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathword-embeddings-and-dota2.html
208 lines (199 loc) · 14.2 KB
/
word-embeddings-and-dota2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Gavagai</title>
<link rel="stylesheet" href="http://federicov.github.io/theme/css/main.css" />
<link href="http://federicov.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="Federico's Blog Atom Feed" />
<!--[if IE]>
<script src="https://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
<![endif]-->
</head>
<body id="index" class="home">
<header id="banner" class="body">
<h1><a href="http://federicov.github.io/">Federico's Blog </a></h1>
<nav><ul>
<li><a href="http://federicov.github.io/pages/about.html">About</a></li>
<li class="active"><a href="http://federicov.github.io/category/machine-learning.html">Machine Learning</a></li>
<li><a href="http://federicov.github.io/category/misc.html">misc</a></li>
<li><a href="http://federicov.github.io/category/optimization.html">Optimization</a></li>
<li><a href="http://federicov.github.io/category/programming.html">Programming</a></li>
<li><a href="http://federicov.github.io/category/science.html">Science</a></li>
</ul></nav>
</header><!-- /#banner -->
<section id="content" class="body">
<article>
<header>
<h1 class="entry-title">
<a href="http://federicov.github.io/word-embeddings-and-dota2.html" rel="bookmark"
title="Permalink to Gavagai">Gavagai</a></h1>
<a href="https://twitter.com/share" class="twitter-share-button" data-count="horizontal" data-via="f_vaggi">Tweet</a><script type="text/javascript" src="https://platform.twitter.com/widgets.js"></script>
</header>
<div class="entry-content">
<footer class="post-info">
<abbr class="published" title="2016-04-22T00:00:00+02:00">
Published: Fri 22 April 2016
</abbr>
<address class="vcard author">
By <a class="url fn" href="http://federicov.github.io/author/federico-vaggi.html">Federico Vaggi</a>
</address>
<p>In <a href="http://federicov.github.io/category/machine-learning.html">Machine Learning</a>.</p>
<p>tags: <a href="http://federicov.github.io/tag/video-games.html">video games</a> <a href="http://federicov.github.io/tag/machine-learning.html">machine learning</a> <a href="http://federicov.github.io/tag/dota2.html">dota2</a> </p>
</footer><!-- /.post-info --> <p>Last time I talked about Dota2, I covered the
<a href="http://www.datdota.com/blog/?p=1323">evolution of the metagame across patches</a>.
This time, I'll focus on analyzing the way pros draft - but looking at it using tools from
<a href="https://en.wikipedia.org/wiki/Natural_language_processing">NLP</a> in a very novel way.</p>
<h2>Introduction:</h2>
<p>How would you teach someone what the word 'rabbit' means? You could go out in a
field, and every time a rabbit shows up you could point to it and exclaim
'rabbit'. However, even this highly simplified vignette assumes that you are
trying to explain the concept of rabbit to someone who has a mental model of
the world very similar to yours. Now, imagine that instead of teaching the
meaning of words to a human who sees the world as you do, you are trying to
teach them to a computer. Where do you start?</p>
<p>This is where <a href="https://en.wikipedia.org/wiki/Word_embedding">Word Vectors</a>
come in. The key assumption behind word vectors is that words which occur in
similar contexts have similar meanings - and this is known as the
<a href="https://en.wikipedia.org/wiki/Distributional_semantics">Distributional Hypothesis</a>.</p>
<p>In the case of linguistics, this means that if you find the word 'negotiate' in
similar contexts as the word 'bargain', their meaning is probably similar. Using
word vectors, it means that if you calculate the <a href="https://en.wikipedia.org/wiki/Cosine_similarity">cosine similarity</a>
(a measure of how similar two vectors are) between the word vector for 'negotiate'
and 'bargain' you'll get a value close to 1. Another neat property of word
vectors is that they allow us to reason by analogy: a common example is that
(King - Man) ~= (Queen - Woman). For an awesome example of the power of
word vectors, check out <a href="https://sense2vec.spacy.io/?natural_language_processing%7CNOUN">an analysis</a>
of every single reddit post done using <a href="https://twitter.com/spacy_io">spacy</a>.</p>
<h2>From Word Vectors to Hero Vectors:</h2>
<p>How can word vectors help us understand Dota2 teams? Imagine that you treat every Dota2 team as a sentence, with heroes making up the words. For example, this would be a valid sentence in Dota2ese:</p>
<p><strong>Batrider Disruptor Leshrac Naga Siren Weaver</strong></p>
<p>and so would this:</p>
<p><strong>Dragon Knight Weaver Crystal Maiden Windranger Treant Protector</strong></p>
<p>Recall the Distributional Hypothesis that we discussed above. Instead of trying to understand what words mean by looking at the sentences in which they occur, we want to understand what heroes are like by looking at the kinds of team they show up in. Concretely, if we see that heroes like <strong>Witch Doctor</strong> and <strong>Lion</strong> tend to show up in similar teams, this indicates that they have similar roles.</p>
<p>We will use <a href="http://www.datdota.com/">datdota</a> as our database of drafts, and the excellent <a href="https://radimrehurek.com/gensim/index.html">gensim library</a> to learn
our hero vectors.</p>
<p>When learning our hero vectors, we have to specify how many dimensions we want to use to represent our heroes. In general, more dimensions means that we get higher quality representations, but we require more computing power and more data.</p>
<p>For example, after training on our dataset, this is what the hero vector for <strong>Shadowfiend</strong> looks like.</p>
<p>[-0.06813218, -0.00902375, 0.10162564, -0.01908037, 0.03013835,<br />
0.16538762, 0.03104097, 0.02496031, -0.16785616, 0.3313826 ,<br />
-0.21904311, -0.07945664, 0.19140202, 0.12729862, 0.36308175,<br />
0.19962946, 0.13561839, 0.23637122, -0.32607114, 0.05647549,<br />
0.09655968, -0.21899879, 0.04926173, 0.12474103, 0.14504923,<br />
0.06281823, 0.14728694, -0.03583163, -0.00227163, 0.1205247 ,<br />
0.01127683, 0.01522848, 0.13806115, 0.0216765 , 0.13671157,<br />
-0.1683237 , 0.00408782, 0.10514087, -0.17610508, 0.04697264,<br />
-0.03406512, -0.14956233, 0.20201634, 0.00907436, -0.05804597,<br />
-0.00481437, 0.11493918, -0.07718568, -0.13443205, -0.01155808]</p>
<p>The hero <strong>Shadow Fiend</strong> is now represented as a point in 50 dimensional space,
but that's still not that useful: we turned a word we can understand into 50
numbers that don't seem to mean anything. However, I promise that we can do
some really cool things: for example - let's look at the other heroes
whose vectors are most similar to that <strong>Shadow Fiend</strong>:</p>
<ol>
<li><strong>Queen of Pain</strong>: 0.9340388774871826</li>
<li><strong>Storm Spirit</strong>: 0.9170020818710327</li>
<li><strong>Viper</strong>: 0.9082884788513184</li>
<li><strong>Sniper</strong>: 0.8958033919334412</li>
<li><strong>Zeus</strong>: 0.8526902794837952</li>
</ol>
<p>And here it is in a more visual form - each row corresponds to the vector for a
particular hero:</p>
<p><a href="url"><img src="http://federicov.github.io/images/Top_5_SF.png" align="left" width="800" ></a></p>
<p>Wow - those actually all make a lot of sense. Let's try a tougher task now and
see if we can use hero vectors to reason about analogies. <strong>Lion</strong> is
to <strong>Anti Mage</strong> as <strong>Witch Doctor</strong> is to ....:</p>
<ol>
<li><strong>Spectre</strong>: 0.9638912677764893</li>
<li><strong>Phantom Lancer</strong>: 0.9185065031051636</li>
<li><strong>Phantom Assassin</strong>: 0.9039324522018433</li>
<li><strong>Morphling</strong>: 0.858444333076477</li>
<li><strong>Lifestealer</strong>: 0.8570600748062134</li>
</ol>
<p>Again, pretty neat! While these synergies won't exactly let you outdraft PPD,
hero vectors can pick up on the notion of pairing a ranged support with a
melee carry.</p>
<h2>A Global View:</h2>
<p>It's possible to plot the hero vectors of every single hero at the same time,
but the results can be a bit <a href="http://federicov.github.io/images/Hero_Clusters.png">overwhelming</a>.</p>
<p>In that figure, every column corresponds to a hero vector, and we have sorted
rows and columns in a dendogram. Unless you are used to looking at those kinds
of graphs all the time, it's not very obvious which heroes form groups and which
heroes are similar to each other.</p>
<p>Ignoring the hero vectors for a minute, we can cut the
<a href="http://federicov.github.io/images/Hero_Dendogram.png">dendogram</a> (the tree-like structure at
the top of the previous graph) and look at
which heroes end up close to each other.</p>
<p>We see that we have recovered some pretty meaningful (although not flawless)
groups. We can notice an 'offlane-like' group with Doom, Nyx, Dark Seer,
Bristleback and Centaur. We have a hard carry group with Drow Ranger, Slark,
Phantom Lancer and Lifestealer. We have a 'strength support' group with
Wraith King, Tusk and Abbadon.</p>
<p>There's one more way to visualize our groups. We can project our 50 dimensional
dataset in 2d using t-SNE](https://lvdmaaten.github.io/tsne/). t-SNE is a very
clever technique where we look for a lower dimensional representation that
still maintains as much of the high level structure as possible.</p>
<p>After manipulating the data and plotting it in 2d, here is what we get:</p>
<p><a href="http://federicov.github.io/images/Heroes_TNSE.png"><img src="http://federicov.github.io/images/Heroes_TNSE.png" align="left" width="750" ></a></p>
<p>The hero colors come from the groups we identified above. Again - notice that
there are easily discrete clusters that are quite meaningful.</p>
<h2>What do the vectors mean?:</h2>
<p>What exactly do the numbers that we obtain for each hero mean though? For
example, what does it mean that that the first dimension of <strong>Shadow Fiend</strong>
has value -0.06813218? Usually, we'd just say that it is a 'latent feature'
and leave it at that, but in this case, we can do a little bit more.</p>
<p>The <a href="http://dota2.gamepedia.com/">dota2 gamepedia</a> assigns a series of roles
for each hero. They are of course debatable, and heroes can often change from
support to carry across different patch - but it's still a good starting point.
<a href="filename}/images/Hero_Roles.png">Here</a> is a simple table of all the roles assigned to each hero.</p>
<p>Now, we have all the ingredients for the next step. Recall that each hero is
described by 50 numbers (from our embedding procedure) and that hero has
certain roles (from the dota2 gamepedia).</p>
<p>What we want to do now is to see if there is any relationship between the
embedding and a hero's role. There's lots of ways to do this - but perhaps
the easiest way is to use <a href="https://en.wikipedia.org/wiki/Logistic_regression">logistic regression</a>.<br />
For the math nerds - to insure that we get a sparse set of basis, we will
also use a strong L1 penalty (which, as a bonus, regularizes our predictions).</p>
<p>Here are the results of that:</p>
<p><a href="http://federicov.github.io/images/LR_Weights.png"><img src="http://federicov.github.io/images/LR_Weights.png" align="left" width="750" ></a></p>
<p>What does that mean, in practice? We see that the 46th vector is strongly
associated with being a support, and the 38th vector is strongly associated
with being a ranged hero. Let's plot the 38th and 46th vector of all heroes:</p>
<p><a href="http://federicov.github.io/images/Weights_vs_Roles.png"><img src="http://federicov.github.io/images/Weights_vs_Roles.png" align="left" width="750" ></a></p>
<p>As we can see - heroes that have higher values on axis 46, are a lot more
likely to be support heroes. Similarly, heroes that have higher values on axis
38 are more likely to be ranged - you may notice that the two axis are somewhat
correlated (but not perfectly so) - as support heroes are a lot more likely to
be ranged. Incidentally, this correctly identifies <strong>Undying</strong>, <strong>Elder Titan</strong>
and <strong>Abbadon</strong> as melee supports (high support, low ranged) but
incorrectly identifies <strong>Drow Ranger</strong> (and, to a certain extent, <strong>Clinkz</strong>
as melee heroes.</p>
<h2>Conclusion:</h2>
<p>When training those embeddings, we did not use any information about Dota2:
as far as the computer is concerned, each draft is an arbitrary sequence of
symbols without any meaning... yet, starting from that, we were able to recover
informative representations which have meaningful high level interpretation.<br />
We treated Dota2 drafts as a foreign language that we do not speak, and, by
looking at patterns in how those words are used, managed to figure out what
the words mean relative to each other.</p>
<p>Further, by connecting the features that we learned in an unsupervised way to
class roles, we were even able to give an interpretation to our latent features.</p>
</div><!-- /.entry-content -->
</article>
</section>
<section id="extras" class="body">
<div class="social">
<h2>social</h2>
<ul>
<li><a href="http://federicov.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate">atom feed</a></li>
<li><a href="http://twitter.com/f_vaggi">@f_vaggi</a></li>
</ul>
</div><!-- /.social -->
</section><!-- /#extras -->
<footer id="contentinfo" class="body">
<address id="about" class="vcard body">
Proudly powered by <a href="http://getpelican.com/">Pelican</a>, which takes great advantage of <a href="http://python.org">Python</a>.
</address><!-- /#about -->
<p>The theme is by <a href="http://coding.smashingmagazine.com/2009/08/04/designing-a-html-5-layout-from-scratch/">Smashing Magazine</a>, thanks!</p>
</footer><!-- /#contentinfo -->
</body>
</html>