<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Wah Loon Keng on Medium]]></title>
        <description><![CDATA[Stories by Wah Loon Keng on Medium]]></description>
        <link>https://medium.com/@kengz?source=rss-7f13442b032e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*AJxO6K6Unv5yWo1bgxb3UA.png</url>
            <title>Stories by Wah Loon Keng on Medium</title>
            <link>https://medium.com/@kengz?source=rss-7f13442b032e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 11:12:42 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kengz/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Soft Actor-Critic for continuous and discrete actions]]></title>
            <link>https://medium.com/@kengz/soft-actor-critic-for-continuous-and-discrete-actions-eeff6f651954?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/eeff6f651954</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[actor-critic]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Sun, 11 Aug 2019 18:27:23 GMT</pubDate>
            <atom:updated>2020-01-18T06:01:23.240Z</atom:updated>
            <content:encoded><![CDATA[<p>With the Atari benchmark complete for all the core RL algorithms in <a href="https://github.com/kengz/SLM-Lab">SLM Lab</a>, I finally had time to implement a new algorithm, Soft Actor-Critic (SAC). This came in two papers:</p><ul><li>the first which introduces the SAC algorithm <a href="https://arxiv.org/abs/1801.01290">https://arxiv.org/abs/1801.01290</a></li><li>the second which improves on it <a href="https://arxiv.org/abs/1812.05905">https://arxiv.org/abs/1812.05905</a></li></ul><p>I’ll let you read the papers, which should take just a day to digest, then quickly go through the implementation; the main goal of this post is to show that how it can be adapted easily to work on <strong>discrete actions</strong>, even though both the papers had only described and released implementations for <strong>continuous actions</strong>.</p><p>The implementation is divided into 3 portions: declaring the networks, defining the loss functions, and writing the training loop. In SLM Lab, since all the the components are reusable, implementing SAC took only a day, and testing it with benchmark took a few more. The first paper was implemented and tested in this PR <a href="https://github.com/kengz/SLM-Lab/pull/398">https://github.com/kengz/SLM-Lab/pull/398</a> , but let’s look at the second improved version.</p><p>First, declaring the networks and their optimizers. There are:</p><ul><li>a policy network to learn the policy and produce action. Note that a policy network produces the parameters used to construct action distributions, which can be discrete or continuous. This means that the algorithm can be applied to both discrete and continuous actions.</li><li>4 Q-value networks: 2 networks Q1 and Q2, and their target networks. The duplicity is to improve stability and training speed.</li><li>3 optimizers for learning the policy and two non-target Q-networks Q1 and Q2.</li><li>1 optimizer to learn the temperature parameter alpha, which automatically adjusts the entropy. Note that we learn the logarithm of alpha instead of alpha so the numeric range is more well-behaved.</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/51d28acc58e208da887f5d6ac1d23935/href">https://medium.com/media/51d28acc58e208da887f5d6ac1d23935/href</a></iframe><p>Second, the loss functions to train the networks in the SAC algorithm. There are:</p><ul><li>the Q-function loss for each of the two Q networks. This is just regression, so loss = MSE(q_pred, q_target). Implement a method to calculate q_pred = Q-network(state, action), and implement another method to calculate q_targets= reward + gamma * (target_Q(s’, a’) — alpha * log pi(a’|s’)). We’ll look at the log probability calculation later.</li><li>the policy loss = alpha*log pi(a|s) — q_preds</li><li>the alpha loss = log_alpha * (log_probs + target_entropy), where target_entropy = -np.prod(action_space.shape).</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5ded006137ddb97a4d696d6d70bc66f9/href">https://medium.com/media/5ded006137ddb97a4d696d6d70bc66f9/href</a></iframe><p>Before moving to the training loop, let’s see how the action log probabilities are calculation. A requirement for the policy loss is that the action and its log prob needs to be differentiable. This is typically done using a reparametrization trick — so that a sampled action tensor carries a gradient to be differentiable.</p><p>This is simple for any continuous distributions which supports a rsample() method. Additionally, continuous actions often needs to be bound within a range, say [-1, 1], so the log prob calculation needs to be bounded as well. The papers (in Appendix C) described a derivative function for doing so.</p><p>However for discrete action, the papers did not mention anything. As a result I have not seen any implementation which has a simple discrete counterpart to the action rsample() and log prob calculation. Most standard discrete distributions do not support rsample() and so its actions are not differentiable.</p><p>The key idea is that we need a discrete distribution that is reparametrizable. There is one such distribution — the GumbelSoftmax distribution. PyTorch does not have this built-in, so I simply extend it from a close cousin which has the right rsample() and add a correct log prob calculation method. With the ability to calculate a reparametrized action and its log prob, SAC works beautifully for discrete actions with minimal extra code, as seen below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5bccaed447ec997b41e527967a886e15/href">https://medium.com/media/5bccaed447ec997b41e527967a886e15/href</a></iframe><p>Third, the training loop. Given the loss functions defined above, this is straightforward. Train after every frame, and do a soft update for the Q target networks.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/393756b4be3a77233cb20cfa53c31982/href">https://medium.com/media/393756b4be3a77233cb20cfa53c31982/href</a></iframe><p>The <a href="https://github.com/kengz/SLM-Lab/blob/b8696faeb4cd8bf105d2c4abaa8936bd953fd0a7/slm_lab/agent/algorithm/sac.py">full code is available in SLM Lab</a>, so feel free to look at it.</p><p>Now, some benchmark results of SAC on continuous environments (Roboschool) and a discrete environment (LunarLander):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3bc84d8fc672e6d47ceacf626fe667f8/href">https://medium.com/media/3bc84d8fc672e6d47ceacf626fe667f8/href</a></iframe><p>To run SAC from <a href="https://github.com/kengz/SLM-Lab">SLM Lab</a>, just run: python run_lab.py slm_lab/spec/benchmark/sac/sac_halfcheetah.json sac_halfcheetah train .</p><blockquote>My book <a href="https://www.amazon.com/dp/0135172381"><strong>Foundations of Deep Reinforcement Learning</strong> is now available on Amazon</a>! It is an introduction to deep RL that closely combines both theory and implementation, and is written for people who wish to understand and get RL to work.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rPdzeHcdlqtVyewzULEXVw.png" /></figure><h3>References</h3><p><a href="https://arxiv.org/abs/1801.01290">[1] T. Haarnoja et al. 2018. <em>Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor</em></a></p><p><a href="https://arxiv.org/abs/1812.05905">[2] T. Haarnoja et al. 2018. <em>Soft Actor-Critic Algorithms and Applications.</em></a></p><p>[3] SLM Lab: Modular Deep Reinforcement Learning framework in PyTorch. <a href="https://github.com/kengz/SLM-Lab">https://github.com/kengz/SLM-Lab</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eeff6f651954" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Multi-inheritance magic in SLM Lab]]></title>
            <link>https://medium.com/@kengz/multi-inheritance-magic-in-slm-lab-35c666739b03?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/35c666739b03</guid>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Wed, 26 Sep 2018 06:08:56 GMT</pubDate>
            <atom:updated>2018-09-26T06:08:56.685Z</atom:updated>
            <content:encoded><![CDATA[<p>Deep RL is known to be complex in terms of engineering, because it involves so many things. One goal of SLM Lab is to reduce this complexity in both having less code, and simpler code.</p><p>When the base components are designed properly with standardized API, we can do some pretty crazy things in SLM Lab: you can actually implement things without writing any new code.</p><h4>A3C from A2C</h4><p>A3C is an asynchronous version of A2C. We can run it directly using the same <a href="https://github.com/kengz/SLM-Lab/blob/master/slm_lab/agent/algorithm/actor_critic.py">code in </a><a href="https://github.com/kengz/SLM-Lab/blob/master/slm_lab/agent/algorithm/actor_critic.py">slm_lab/agent/algorithm/actor_critic.py</a> by just specifying &quot;distributed&quot;: true in the spec file. This tells the Trial to run Sessions hogwild-style. The same thing means you can turn any of the SLM Lab algorithms into an asynchronous version by only changing that spec, without new code.</p><h4>PPO + SIL from A2C SIL</h4><p>Self Imitation Learning (SIL) is an add-on off-policy training to any onpolicy algorithm. The original SIL is implemented for A2C as an extension (<a href="https://medium.com/@kengz/fast-implementation-of-self-imitation-learning-ffcd0b2b6c6b">see post here</a>). Since PPO is also implemented as an extension of A2C, we can get PPO+SIL using multi-inheritance, i.e. pull the methods from PPO and SIL classes respectively:</p><pre>from slm_lab.agent.algorithm.actor_critic import ActorCritic<br>from slm_lab.agent.algorithm.ppo import PPO</pre><pre>class PPOSIL(SIL, PPO):<br>    &#39;&#39;&#39;<br>    SIL extended from PPO. This will call the SIL methods and use PPO as super().<br>    &#39;&#39;&#39;<br>    pass</pre><h4>AtariPrioritizedReplay from AtariReplay and PrioritizedReplay</h4><p>We already have AtariReplay, which handles the image normalization and concatenation for Atari environments, but it is just a common replay memory. PrioritizedReplay was implemented with prioritization, but it only works for a plain memory without preprocessing. To combine the two? You guessed it, multi-inheritance magic again:</p><pre>from slm_lab.agent.memory.replay import Replay, AtariReplay</pre><pre>class AtariPrioritizedReplay(PrioritizedReplay, AtariReplay):<br>    &#39;&#39;&#39;Make a Prioritized AtariReplay via nice multi-inheritance (python magic)&#39;&#39;&#39;<br>    pass</pre><h4>Conclusion</h4><p>The point is, when there’s less code, there’s fewer bugs. The things which get reused maximally are also more well-tested.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=35c666739b03" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[pip module for RL agents in SLM Lab]]></title>
            <link>https://medium.com/@kengz/pip-module-for-rl-agents-in-slm-lab-50e73872445d?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/50e73872445d</guid>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[pytorch]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Wed, 05 Sep 2018 07:31:07 GMT</pubDate>
            <atom:updated>2018-09-06T22:07:27.390Z</atom:updated>
            <content:encoded><![CDATA[<p>As part of the usability improvement in <a href="https://github.com/kengz/SLM-Lab/releases/tag/v2.0.0">SLM Lab v2.0.0</a>, we have also made it possible to just use the agents outside of the SLM framework, just like any installed pip module. It is now possible to just do a pip import slm_lab (or as one of the readers pointed out, python setup.py install without pip) and initialize its agents for use.</p><p>This is especially crucial for those who want to use these algorithms in an industrial application. Often the app is part of a massive industrial system, and it is difficult or impossible to wrap that inside the lab. The agent must be made into an importable module to be used inside the app, either for training or for inferencing in deployment.</p><p>For demonstration, we have created a standalone script to show how to do this. The solution is very lightweight. The proper spec format will initialize the agent as usual, and as long as the proper agent APIs are called, all agent functionalities will work. Of course, to make use of the lab’s full potential such as distributed training, parameter search, data analysis, you would still need to use the Lab.</p><p>The implementation below is in fact uses a simplified form of the lab’s original Session class. This shows that the main control loop and API methods are already generic.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dfd4ee36d714dbce2534d7dac857cfa4/href">https://medium.com/media/dfd4ee36d714dbce2534d7dac857cfa4/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=50e73872445d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Deep Reinforcement Learning with SLM Lab]]></title>
            <link>https://medium.com/@kengz/deep-reinforcement-learning-with-slm-lab-bebf87f531ac?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/bebf87f531ac</guid>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[dqn]]></category>
            <category><![CDATA[ai]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Wed, 05 Sep 2018 05:57:58 GMT</pubDate>
            <atom:updated>2018-09-05T05:57:58.322Z</atom:updated>
            <content:encoded><![CDATA[<p>SLM-Lab <a href="https://github.com/kengz/SLM-Lab/releases/tag/v2.0.0">v2.0.0 was recently released</a>. This version represents a major milestone, as it has grown to over a dozen algorithms while retaining its light light codebase due to modular component reuse. All the components are also distributable ala A3C-style. They can all run in both in OpenAI gym and Unity environments. See the full list here:</p><p><a href="https://github.com/kengz/SLM-Lab">kengz/SLM-Lab</a></p><p>The most important change is the API, which now defaults to single-agent-single-environment case, while still enabling the multi-agent-multi-environment as a natural extension. This change vastly improves usability — a common request from users.</p><p>All the algorithms are preconfigured in spec files, which share a standard format and use the modular components implemented in the lab. Users can choose from multiple spec files: sarsa, dqn, ddqn, reinforce, a2c, ppo, sil, etc. and initialize them.</p><pre>spec_file = &#39;ppo.json&#39;<br>spec_name = &#39;ppo_mlp_shared_cartpole&#39;<br>spec = spec_util.get(spec_file, spec_name)<br>info_space = InfoSpace()</pre><p>The environment and agent instantiation has also vastly simplified. Pass the spec file and info space from above to the init methods, which will call the proper RL modules accordingly to construct the agent and its components as specified. Starting from below, the logics are clearly encapsulated within a Session class.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d344aac900dec04e19469bfb6db7ffc5/href">https://medium.com/media/d344aac900dec04e19469bfb6db7ffc5/href</a></iframe><p>Next, a control loop which defines an episode will run the agent and env interactions. All the necessary updates, training, inference, etc. are properly structured within the lab’s API methods:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9dfdfdb7a17bdb4d4f713ef0d5f57b97/href">https://medium.com/media/9dfdfdb7a17bdb4d4f713ef0d5f57b97/href</a></iframe><p>The top level run loop will then run these episodes for as many times necessary:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4412a746dae210e84fa7c04790a25f5f/href">https://medium.com/media/4412a746dae210e84fa7c04790a25f5f/href</a></iframe><p>We will now give a quick tour of using Deep RL agents in the Lab.</p><h3>Installation</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/164b80e7f01d0141fd318b8aa2e07c9a/href">https://medium.com/media/164b80e7f01d0141fd318b8aa2e07c9a/href</a></iframe><h3>Demo</h3><p>To see the lab in action, let’s run a quick demo of a DQN agent to solve the CartPole environment.</p><ol><li>We will use a prepared spec file at slm_lab/spec/demo.json to specify the DQN agent parameters. The lab will read it to initialize an agent using many of its implementations. You can also change the value to experiment with DQN as well:</li></ol><pre>&quot;dqn_cartpole&quot;: {<br>  &quot;agent&quot;: [{<br>    &quot;name&quot;: &quot;DQN&quot;,<br>    &quot;algorithm&quot;: {<br>      &quot;name&quot;: &quot;DQN&quot;,<br>      &quot;action_pdtype&quot;: &quot;Argmax&quot;,<br>      &quot;action_policy&quot;: &quot;epsilon_greedy&quot;,<br>      &quot;action_policy_update&quot;: &quot;linear_decay&quot;,<br>      &quot;explore_var_start&quot;: 1.0,<br>      &quot;explore_var_end&quot;: 0.1,<br>      &quot;explore_anneal_epi&quot;: 20,<br>      &quot;gamma&quot;: 0.99,<br>      &quot;training_batch_epoch&quot;: 3,<br>...</pre><p>2. To tell the lab to use this spec file to run an experiment, go toconfig/experiments.json. It looks like this:</p><pre>{<br>  &quot;demo.json&quot;: {<br>    &quot;dqn_cartpole&quot;: &quot;dev&quot;<br>  }<br>}</pre><blockquote>To run faster, change lab mode from “dev” to “train” above and rendering will be disabled.</blockquote><p>3. Now, launch terminal in the repo directory, run the lab:</p><pre>conda activate lab<br>python run_lab.py</pre><p>You should then see the following. The DQN agent will start out poor at balancing the pole. But as the training goes on, it starts to learn, gets better, and balances the pole for longer before the environment resets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nIWoInl_ZOocbgG-NtcFXQ.png" /></figure><p>4. This demo experiment runs a single trial with 4 repeated sessions for reproducibility. When the demo finishes, it will save some analyzed data and graphs of the experiment, along with the DQN model, located at data/dqn_cartpole_2018_06_16_214527 (timestamp will differ). You should see some healthy graphs:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*h-Rf2JyVepW29HV99ubGfg.png" /><figcaption>Trial graph showing average envelope of repeated sessions.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*gRFSaJ9QJY76EQjLalEdgw.png" /><figcaption>Session graph showing total rewards, exploration variable and loss for the episodes.</figcaption></figure><p>5. Now, you can enjoy your trained model, with Enjoy mode! The graph above is trial 1 session 0, and you can see a pytorch model saved at data/dqn_cartpole_2018_06_16_214527/dqn_cartpole_t1_s0_model_net.py. Use the prepath (the string above without the model suffix) at config/experiments.json to tell the lab to run the enjoy mode using this model:</p><pre>{<br>  &quot;demo.json&quot;: {<br>    &quot;dqn_cartpole&quot;: &quot;enjoy@data/dqn_cartpole_2018_06_16_214527/dqn_cartpole_t1_s0&quot;<br>  }<br>}</pre><blockquote>enjoy mode will automatically disable learning and exploration. Graphs will still save.</blockquote><h3>Hyperparameter search</h3><p>Finally, let’s do a full experiment with hyperparameter search for DQN. Change the lab mode from &quot;train&quot; to &quot;search&quot; in config/experiments.json ,</p><pre>{<br>  &quot;demo.json&quot;: {<br>    &quot;dqn_cartpole&quot;: &quot;search&quot;<br>  }<br>}</pre><p>and run</p><pre>python run_lab.py</pre><p>The lab will now run experiments of multiple trials with hyperparameter search. For efficiency, environments will not be rendered, and everything will be ran at full speed.</p><p>When it ends, refer to {prepath}_experiment_graph.png and {prepath}_experiment_df.csv to find the best trials. The experiment graph will look like:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B8-sFbZbNnEh2fzQ7tgBYw.png" /><figcaption>Experiment graph summarizing the trials in hyperparameter search.</figcaption></figure><p>This experiment graph tells us how sensitive is DQN to some hyperparameters. For example, a single-hidden-layer, 64-unit neural network works better than 2-layers; tanh activation function allows a faster learning for this problem; learning rate around 0.01 works better.</p><p>That’s all for the quick demo. To see more algorithms, RL components and usage details, check out the documentation page:</p><p><a href="https://kengz.gitbooks.io/slm-lab/content/">Introduction · SLM Lab</a></p><p>If you wish to use this for research, teaching, or industrial applications, feel free to reach out! We would be delighted to hear any suggestions and provide support.</p><p>We will soon conduct a full benchmark by running all algorithms against all environments, although this will translate to thousands of experiments (including parameter search) and require some serious compute power. If you are interested in helping, please let us know.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bebf87f531ac" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[OpenAI Five DotA: Solving the Global Skill Problem]]></title>
            <link>https://medium.com/@kengz/dota-five-solving-the-global-skill-problem-5d521651667c?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/5d521651667c</guid>
            <category><![CDATA[openai]]></category>
            <category><![CDATA[gaming]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[dota-2]]></category>
            <category><![CDATA[ai]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Mon, 13 Aug 2018 07:33:23 GMT</pubDate>
            <atom:updated>2018-08-14T05:02:44.474Z</atom:updated>
            <content:encoded><![CDATA[<p>Laura and I were talking about how we would solve the global skill problem in OpenAI’s DotA Five, which is still evidently lacking from their latest 5 vs 5 benchmark event. Here’s the original post outlining the problem.</p><p><a href="https://medium.com/@kengz/dota-five-next-challenges-7556a3af1adc">OpenAI Five DotA: Next Challenges</a></p><p>So far, we still have not seen any proper global skills used by OpenAI Five. This is not surprising given <a href="https://s3-us-west-2.amazonaws.com/openai-assets/dota_benchmark_results/network_diagram_08_06_2018.pdf">the architecture they currently have</a>. Although absolute x, y positions for a unit is available as an input, the output action deals only with relative x, y offsets from a selected target unit. The usage of relative x, y in the policy assumes the property of locality, that is, it only concerns with the the neighborhood of a targeted unit. This is a fundamental limitation because global skills are inherently non-local.</p><p>Global skills in DotA does not have a range limit, and often don’t require a target unit. That is, global skills can be aimed at a dark spot on the map without visibility. This requires not focusing on a targetable unit, and the usage of absolute x, y coordinates on the map.</p><p>Invoker’s Sunstrike is worth studying because it reveals a few characteristics of global spells in DotA. A classic and the most amazing use of Sunstrike is to finish off an enemy hero that is out of reach. In this scenario, the enemy hero is wounded and retreating back to its base. Invoker would have to make a blind guess on the path the enemy is taking, its movement speed and pattern, then make a gamble by placing Sunstrike on some non-visible location on the map, hoping that the enemy would pass by there when the spell hits.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F5UvCzh4MJH8%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D5UvCzh4MJH8&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F5UvCzh4MJH8%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/80e781e822a6c7c43cc1a2cdf3f839b2/href">https://medium.com/media/80e781e822a6c7c43cc1a2cdf3f839b2/href</a></iframe><p>To perform this feat, first the player needs several things:</p><ol><li>understand the map globally, as in which paths are traversable, and which are the most optimal, commonly taken path given a scenario.</li><li>understand the context of the battle, the intent of the enemy player, and the path they are likely to take.</li><li>understand the enemy hero’s movement speed to predict how far and where it would have traveled in some amount of time.</li><li>choose where to cast the spell or ability using the above information.</li></ol><p>This also requires some mind game, as different players would choose to take different paths to counteract Invoker’s Sunstrike. But Invoker would also expect that the enemy is going to counteract and adjust accordingly, then the enemy is again going to account for that… and so on. It’s a matter of who can outplay the other’s mind game.</p><p>Mind game aside (it is just experience and intuition), we propose a method to construct a sub policy which accounts for all the listed requirements above.</p><p>For #1, save a global map with the absolute x, y coordinates, the terrains and path information with it. Update it with observations of how any players tend to take some common paths. This will be useful for a sub-map retrieval later.</p><p>For #2, the policy is already expected to learn and encode that as part of normal game play, so, no problem.</p><p>For #3, OpenAI’s current model can already predict the location of a hero a few seconds into the future, as shown in their video:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FpNfV5nQXVCQ%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DpNfV5nQXVCQ&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FpNfV5nQXVCQ%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/83c50bcf74e2a5123a33b2f77f77d524/href">https://medium.com/media/83c50bcf74e2a5123a33b2f77f77d524/href</a></iframe><p>However, we now need to combine #1 and #2. First, get the latest observed trajectory of the enemy hero to predict where it is going to move to. Suppose from now on the enemy hero is invisible due to the fog of war. Given its next predicted absolute x, y coordinates, say at x=6000 and y=8000, retrieve from the global map in memory a limited slice of the neighborhood of said location, say of radius 500. So, the sub-map retrieved is the slice from x=5500 to 6500, and y=7500 to 8500.</p><p>Given this sub-map, the agent will have information about the terrain and the the likeliness of some paths being taken within the radius. While the spell is still pending (e.g. in cooldown), the agent can predict the location of enemy hero in the next frame, say now it is x=6200 and and y=8100. Repeat the above and update the sub-map to the slice from x=5700 to 6700, and y=7600 to 8600. Repeat this as many times as needed until the spell is ready. In a real game, this may be 10 to 30 seconds.</p><p>This sub-map prediction method avoids the need to process the entire map on the policy, which is an extremely large space, and requires a lot more compute to do. It also avoids the need to process redundant part of the map and focus only of the neighborhood of its path-prediction.</p><p>Finally, for #4, since the agent will now be able to guess where the enemy hero is going to be via some sequential prediction using some experience about enemy movement, terrain, and the global map, it can now pick some candidate absolute x, y coordinates to target the spell, i.e. the final x, y in its chain of predictions which will coincide with the spell’s effect. All the policy needs now is some luck.</p><p>In fact, the same sub-policy can also work for a variety of cast-in-the-blind skills, such as Pudge’s Hook, Mirana’s Arrow, and Clockwerk’s Hookshot. These are not exactly global skills, but their cast ranges are sufficiently large that they go beyond the maximum offset x, y the current OpenAI policy uses. Also, they require the same skills at predicting enemy’s movements through familiar terrain in the dark. Moreover, pro players would use the constraints from the terrain to their advantage when using those skills. Just look at how Dendi plays his Pudge, or Sing Sing’s “Shoot arrow hit arrow”:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fps246y7cFbw%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dps246y7cFbw&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fps246y7cFbw%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/3d55cfaa7611f42bca51d94a725e8897/href">https://medium.com/media/3d55cfaa7611f42bca51d94a725e8897/href</a></iframe><p>The other case is going for Roshan, which can also be considered a global policy. It requires understanding where Roshan pit is (#1), guessing where the enemies would be at even if they are not visible on the map (maybe they are going for Roshan, and you can ambush them), or where our ally heroes are going to (#2, #3). If any of them or even the agent itself is going for that global strategic spot, then they could follow suit and use their ability to move to the pit (#4).</p><p>Global or blind strategies in DotA are a result of careful and thoughtful consideration. The sub-policy described above will give the agents the tools required to perform the same feat as well. As the players who manage to pull off those amazing high stake feats say “luck is no excuse”, here are more of those replays on numerous more heroes, performed by pro players. The second video showcases a lot of the creative (one-shot) strategies people have done.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FC0syIB3Fp-0%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DC0syIB3Fp-0&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FC0syIB3Fp-0%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/8189be14a372df5dc8f5f1817e59f209/href">https://medium.com/media/8189be14a372df5dc8f5f1817e59f209/href</a></iframe><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FwQUmZkOFkuE%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DwQUmZkOFkuE&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FwQUmZkOFkuE%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/98773503ee679e839678ae01b5d2046b/href">https://medium.com/media/98773503ee679e839678ae01b5d2046b/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d521651667c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Semantic Correspondence Part 2]]></title>
            <link>https://medium.com/@kengz/semantic-correspondence-part-2-1b26a266346?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/1b26a266346</guid>
            <category><![CDATA[grounding]]></category>
            <category><![CDATA[semantics]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Fri, 10 Aug 2018 06:42:28 GMT</pubDate>
            <atom:updated>2018-08-10T06:43:19.995Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Read part 1 here:</em></p><p><a href="https://medium.com/@kengz/semantic-correspondence-via-powernet-expansion-f8650b49c0b7">Semantic correspondence via PowerNet expansion</a></p><ul><li>From now on, let’s call Semantic Correspondence via PowerNet Expansion as simply SemCo. The first part did not address how to use semantics and memory module to control human-like behaviors like one-shot learning or any of our mental capabilities. This part will address them.</li><li>By the way SemCo makes sense: once trained, when deployed, it can be used directly. E.g. babies’ eyes and color vision, ears and etc. These raw inputs and direct muscle memory don’t require abstract mental faculty, and they work right out of the box, because the design had been evolved and reproduced using our DNA. For example we can see red and we can hear “red” once were born.</li><li>But of course the first instance we learn the concept “red”, when it is first noticed, the neural module must draw the boundary and create identification to say “okay, the thing in attention is red”. Then we have created a category for the concept “red” using our born-ready modules. The same goes for sound, when someone tells us that the red thing seen is called “red”. When this happens, we also internally link the visual and audio categories as different aspects of the same thing.<br>* Essentially, SemCo serves as the foundation for forming intelligence. It provides the tool to start forming categories, and category formation requires some also born-ready modules such as memory, spatial awareness, emotions etc. These non-IO modules can be trained with a lot of data like how we evolved ours, or be coded directly if we know how to design them. Together they allow full category creation and some set of computational functions which is Turing complete (that’s why we can have general intelligence). Then, SemCo is complete: first we form base concepts that can be easily categorized, such as “apples”, “red”, “water”. As we collect more categories, the pressure for informational efficiency, which are consequent of our memory size and the need of communicative efficiency, will force us to start creating compositional categories, e.g. “fruits”. As the snowball keeps rolling, we create more higher level, abstract categories, such as numbers, counting, and eventually hit the critical mass for categories formed.</li><li>These categories form the entirety of human culture and knowledge. We did not learn to count overnight. In fact, every bit of our knowledge is the produce of some painstaking journey of accidents and discovery, one building on another that came before it. But we can learn them quite rapidly in comparison, say in school. So, I expect SemCo, when constructed with the right modules and capacities, and taught with the right curriculum like human children are, it can develop intelligence as an emergent consequence of the categories formed due to pressure for informational efficiency and survival.</li><li>Notice how humans evolved through a long chain of selection from single cell organisms: first the basic modules for metabolism, locomotion, then more advanced organs like eyes, ears, nose, skin, limbs, etc. and later, mental capabilities, cultures, knowledge, and general intelligence, are evolved. SemCo will follow a quite similar path, although we can skip the slow process of evolution using some classic manual design. We already have cameras, mic, speakers, robotic arms etc. which have the potential to create categories like we do, e.g. cameras can see full colors.</li><li>The first step of SemCo is to evolve, train or code those basic born-ready modules, like vision, movement, spatial awareness, ability to see red, etc. I.e. we must train the modules to the stage where it can ground categories, in separate or integrated channels. Then we are ready for the second stage of SemCo, that is to use these modules to learn bootstrap and learn more categories by exposing the agents to a rich and properly designed curricula, and subjecting it to some efficiency or survival pressure. This stage is cumulative, where we try to add modules or curricula for whatever mental capacity it is missing, e.g. the ability to count, do arithmetics, then algebra; or the ability to memorize things, to utilize memory, the ability to generalize, then to meta-generalize, etc. The curricula serve to transfer as much of our culture and knowledge base to the agent, to the point where it can start learning autonomously, and start snowballing its own categories. Eventually, we will hit the categorical critical mass and get general intelligence.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1b26a266346" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Semantic correspondence via PowerNet expansion]]></title>
            <link>https://medium.com/@kengz/semantic-correspondence-via-powernet-expansion-f8650b49c0b7?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/f8650b49c0b7</guid>
            <category><![CDATA[semantics]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[grounding]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Thu, 09 Aug 2018 04:02:33 GMT</pubDate>
            <atom:updated>2018-08-10T06:43:03.916Z</atom:updated>
            <content:encoded><![CDATA[<ul><li>start with cartpole network, 4 inputs, 2 outputs, train network</li><li>then, start with 3D cartpole. we can manually correspond the 2D 4 inputs 2 outputs, then append the third dimension inputs and outputs. this extension can be seen as module extension, using PowerNet style to do sideway connections. When training, base module has a lower learning rate, new module higher. These are of course assuming that the goal is still similar (e.g. from “balance in 2D” to “balance in 3D”). The training should take less time than training from scratch in 3D.</li><li>We can consider the above as sideway extension, defined as no inputs from the new module is connected to the inputs of the old module, and likewise for outputs.</li><li>If we know some inputs/outputs are at different hierarchy, then we can do the power net extension vertically. I.e. the resultant network becomes taller, although not uniformly.</li><li>By swapping the two modules and sequence of training, we can perform the inverse of extension, which is interpolation. For example, if we train something harder, but we wish to extract a smaller module, we can do interpolation, and take it out for use elsewhere.</li><li>The above describe extension and its inverse. Next we can also do combination. This means taking two pretrained modules and use one to extend the other similar to above. However, the difference is when training, the pretrained weights should be subject to lower learning rate, while the newly formed connections in the combination has a higher learning rate. Combination can be done sideway symmetrically (bipartite connections), sideway asymmetrically, and vertically, using extension or its inverse.</li><li>Now, how does it relate to: PowerNet, multitask, correspondence, grounding, modularization?</li><li>PowerNet is obvious, as it serves as the enabler for network modularization and hierarchy differentiation (having clear differences between hierarchy of tasks). Besides, it also helps ensure completeness of operations above, i.e. we won’t miss crucial connections for all forms of extensions and combinations.</li><li>Correspondence and grounding: pretrained input and output units with their corresponding weights already have the first grounding, say left and right. The new module’s new connections to be adjusted with higher learning rate serve to learn to map new inputs and correspond to categories already known. E.g. say original unit 1 means left, unit 2 means right, and we are given new unit 5, 6 from the new module, and 5 corresponds to left and 6 to right, then we should use vertical extension, and adjust the weights so that unit 5 triggers unit 1 (or triggers like unit 1 to the hidden layers), and 6 for 2 similarly. With more learned inputs and outputs, if categories can correspond, it means the network learns to understand a category in more channel, e.g. the word vector for “red” with the vision RGB value for red.</li><li>If new units do not correspond, then the connection weights become 0, no big deal.</li><li>The other correspondence could also be from input to output, e.g. inputs from a new module needs to be controlled with outputs from the old module. This is usually the case in games, where controls are fixed and there are always correspondence in the output, e.g. the buttons for left, right, up, down. In fact, if this is the case, we can avoid doing outputs-outputs correspondence between modules at all, unless the task is to map between different controls.</li><li>The weights are adjusted using the loss determined by the task objective. That is, if the correspondence adjustment helps the agent reuse the old component and provide successful outputs, then reinforce it, and vice versa. This is up to the curriculum design to ensure that correspondence will produce a valid grounding and category expansion. A crucial thing to beware of is the task objective. Lets say, if the old module’s task is to move left, but the new module’s task is to move right, then the correspondence is going to be flipped and become new-right-to-old-left. Therefore, objective is an external factor which controls the grounding into new channels.</li><li>In contrast, for the same environment with grounded semantics, if the objective suddenly changes, e.g. from “move left” to “move right”, the module should not be relearned, otherwise it would be a huge change. Instead, objective should be fed to part of the module. E.g. there should be a context vector, and in training, if the vector says “move left”, then the reward is given if the proper action is done as per the objective statement. In training, cycle through different objectives. In fact, this is a crucial way to differentiate category for grounding, while also providing a bridge between our semantic and the agent’s, i.e. we know when we input “move left” (which is in English and means what we imply), then it will agree with out semantics to move left, as trained by curriculum we design properly as well. This shall be the main mechanism which we transfer the human’s grounded semantics to machines, so we can understand one another without translating from their arbitrary dictionary.</li><li>multitask: the design above actually incorporates the correspondence principle already (hence the name correspondence in it). E.g. train to balance a ball in 3D, then it must be able to balance without training in 2D. Moreover, it can handle semantic-multitask, where each subtask should correspond to a category, e.g. “left”, “right”. The vertical possibility of PowerNet means that it can learn meta-control, e.g. controlling the timescale which it acts, or having a hierarchical policy. The entire goal of semantic-multitask is so that agent “learns symbols, not signals”. Training efficiency is bad now because conventional algorithms always learn one-off weights from scratch, when they should be learning reusable components instead. If I already learn how to balance a thing by tilting left or right, then when given a new balancing task, I should only need to figure out what corresponds to left, right (e.g. if the video is now rotated, so the new left, right is up, down), and apply what I have already learned.</li></ul><p><em>credits: ideas are mine and Laura’s</em></p><p><em>Read part 2 here:</em></p><p><a href="https://medium.com/@kengz/semantic-correspondence-part-2-1b26a266346">Semantic Correspondence Part 2</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f8650b49c0b7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[OpenAI Five DotA: Next Challenges]]></title>
            <link>https://medium.com/@kengz/dota-five-next-challenges-7556a3af1adc?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/7556a3af1adc</guid>
            <category><![CDATA[dota-2]]></category>
            <category><![CDATA[openai]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[gaming]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Tue, 07 Aug 2018 08:57:34 GMT</pubDate>
            <atom:updated>2018-08-13T17:46:41.070Z</atom:updated>
            <content:encoded><![CDATA[<p>If you don’t already know, OpenAI’s Dota Five had just played against some pro players during the benchmark event. It was streamed on Twitch; more details here:</p><p><a href="https://blog.openai.com/openai-five-benchmark-results/">OpenAI Five Benchmark: Results</a></p><p>As someone who had played DotA/DotA 2 since high school and work in reinforcement learning, below are some thoughts on the upcoming challenges OpenAI Five must solve before going up against world-class teams at TI 2018.</p><p>As a quick recap, Five won the first two matches against humans with great confidence and seamless teamwork. The game plays were definitely interesting, and feel like a 6–7k MMR level games. Interestingly the third match Five had to play heroes drafted adversely by the audience, and it lost due to the handicap.</p><p>A crucial thing to notice is that the game is still quite restricted, hence the human players were also handicapped in the matches:</p><ul><li>the five humans players were individuals gathered separately to play, like in a pub match. Since they do not usually play together like a clan does, there was less team synergy, as observed. Considering team work alone, they were far less coordinated than Five, and this was the major difference in strength between the teams. DotA requires team work, and so the humans who are not used to playing together were at a disadvantage.</li><li>both teams were restricted to just 18 heroes to pick from <em>(Earthshaker, Razor, Shadow Fiend, Viper, Tide, Sniper, Witch Doctor, CM, Gryocopter, Necrolyte, Lich, Prophet, Sven, Axe, QOP, Lion, Riki, Slark)</em>. This severely restricts the draft strategy by humans. For example, humans may have some intuitive counter heroes to those picked by Five, but they were not available. Moreover, the available ones are not necessarily the strongest/favorite of the players, nor can they be always combined into an ideal draft. There were not a lot of strong combo heroes. To get an idea, out of the <a href="https://www.dotabuff.com/esports/events/195-ti7-group-stage/picks">20 most picked and banned heroes in TI 7</a>, only 5 of them <em>(Earthshaker, Lich, Prophet, Sven, QOP)</em> were available.</li><li>Pressure and surprises. Okay this is not strictly a handicap. Players mentioned that they constantly felt pressured because they could not get a break from the Five. How much of this is due to the knowledge that they were playing against machines is unknown. Normal expectations from human opponents could not be applied as well, so the humans were somewhat surprised by the styles of Five.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Syo6PWuahy4QoGzIuQpiew.jpeg" /><figcaption>The 18 Heroes available, with progressively updated winning probability predicted by Five. I know…either I’m old, or my TV doesn’t have screenshot function.</figcaption></figure><p>I was watching the event with my friend Laura, who also works with me on deep RL. We were discussing the game play while thinking how certain features may be implemented, and how certain behaviors may arise from the algorithm (vanilla policy gradient, with smart feature engineering and a lot of compute). Of course, besides the strengths, a few shortcomings became apparent as well.</p><p>For now, I can say that the main strengths of Five are strong teamwork, simple but well executed strategies, and the ability to maintain peak performance throughout the game. With these, they were able to beat the humans. However, world class teams have those strengths too, and more. There are several problems to be solved if Five wants to defeat the world class teams. If the version of Five that goes up against the TI finalist teams is not too different from the current version, I would bet my money in favor of the humans. These challenges are, not coincidentally, the well known hard problems in deep RL. We will break them into several topics.</p><p><em>If you need some introduction to how RL is applied to DotA, here’s a nice and humorous </em><a href="https://medium.com/@evanthebouncy/understanding-openai-five-16f8d177a957"><em>introduction by Evan Pu: Understanding OpenAI Five</em></a><em>.</em></p><h4><strong>Reward Design</strong></h4><p>We now know that the reward signal used by Five is not sparse, but we do not know the exact details. A good guess is that the dense intermediate reward signal is a function of some of these obvious quantities:</p><ul><li>gold advantage: game matches always use these to compare team/hero advantages; more gold earned the better. Since gold is spent on items, consider the cumulative earned gold, not the current amount.</li><li>experience advantage: likewise, more experience lead means the team is further ahead in the game and is stronger.</li><li>creeps, heroes, towers killed: these correspond to experience, but counting kills serve as a more direct indicator of good signal, and vice versa for getting killed.</li><li>ability levels: a higher skill level is more powerful, this will also encouraged heroes to level up. However, some heroes may want to wait on upgrading skill levels, such as Doombringer’s <em>LVL Death</em> skill, which multiplies damage based on specific level.</li><li>damage, regen, armor etc. attributes amplified due to items or skill effects: these will indicate the good/bad effects of items, e.g. Assault adds attack speed and armor; getting hit by Desolator decreases armor.</li></ul><p>Even with these reward signals, there are some behaviors that may seem to harm rewards, but are actually proper, strategic play. These behaviors will be tricky for the reward signal to encourage, unless one relaxes the reward signal, but that would mean longer training — there’s a tradeoff. Some of the tricky cases are:</p><ul><li>Techies’s <em>Suicide</em>: the hero chooses to commit suicide and loses a life, and it is not guaranteed to grant Techies kills. While waiting for respawn, techies also loses the previous farming time, and the team may lose some map control. The reward signal may actually encourage Techies to just farm like a normal support and never suicide.</li><li><em>Bloodstone</em>: this item also kills the targeted hero, although it heals allies in the surrounding. A proper usage is to deny enemy kills, or to sacrifice yourself to heal crucial ally heroes. A great replay is this Tinker played by EE, titled <em>“EESama Died for Your Sins”</em>. During a push, Tinker used Bloodstone to commit suicide while healing its allies taking heavy damages from Shadow Fiend.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F2dEvk0X4uOo%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D2dEvk0X4uOo&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F2dEvk0X4uOo%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/95b159b08aa6e5376702ffd5ae88461d/href">https://medium.com/media/95b159b08aa6e5376702ffd5ae88461d/href</a></iframe><ul><li><em>Armlet</em> toggle: Armlet is an item which adds strength and hp when toggled, but you will take damage over time when using it. When you untoggle it, the lost strength will translate into lost hp. Pretty bad item to use if the reward signal prefers higher hp. But here’s this masterful play by Dr. Lee using Armlet on Sniper (which is also an unusual build). Look at how Sniper is constantly at last-hit but managed to keep getting kills. This is one of my favorites.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FjZsoa2OXbZs%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DjZsoa2OXbZs&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FjZsoa2OXbZs%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/151c46352dbacf0db06657bd8ab0d018/href">https://medium.com/media/151c46352dbacf0db06657bd8ab0d018/href</a></iframe><ul><li>Oracle’s ultimate <em>False Promise</em>: this skill delays all damages and heals taken to after some long duration, then add up the damages and 2x heals. This can give the dying ally more time to keep fighting, and if the heal is sufficient, the hero will end up surviving. However, the reward is only observed after the spell effect ends, which can take 8–12 seconds.</li><li>Morphling’s <em>Attribute Shift</em>, Terrorblade’s <em>Sunder, Soul Ring</em> all trade hp in some ways, so they are tricky cases for reward design as well.</li></ul><h4>Exploration/Exploitation Problem</h4><p>We know that with sparse signals and a huge state/action space, exploration is difficult. This is something common to many RL algorithms, and it is even harder for those with low sample efficiency. Arthur Juliani from Unity wrote a great article illustrating a sparse reward problem PPO can’t solve, and an augmentation called Curiosity which addresses the issue:</p><p><a href="https://blogs.unity3d.com/2018/06/26/solving-sparse-reward-tasks-with-curiosity/">Solving sparse-reward tasks with Curiosity - Unity Blog</a></p><p>Coming back to DotA, even though they have a dense reward signal, it may still be insufficient. That reward signal may be sufficient to encourage ease-to-reach scenarios, and we do see a lot of common human strategies in the plays, such as last-hitting, creep-blocking, roaming, ganking, getting towers, baiting. However, there are also common human behaviors that we do not see:</p><ul><li><em>creep pulling:</em> pulling lane creeps to Neutrals to control the lane and get extra gold and experience</li><li><em>creep stacking:</em> pull away Neutrals at the right time for a new wave to spawn, and repeat to have many waves of Neutrals to farm later on for a lot of gold and experience</li><li><em>Roshan</em>: OpenAI has acknowledge that as well. By random exploration, it is hard to have all heroes gathered up at Roshan pit at the right time, and spend a long time and hp to kill it for the prize.</li></ul><p>These strategies are hard to discover by the algorithm because the explore based on random actions, whereas humans do that via deliberate planning. They also involve much longer time horizon. The chance of doing these things randomly are astronomically small. Humans know what the outcome they can get, then imagine and try out plans executed over a long time horizon to obtain the prize.</p><p>Then there are things that are slightly less difficult, but I suspect are nontheless possible:</p><ul><li><em>Invoker spells</em>: this hero can change the combination of 3 orbs he has to create 10 different spells to use. It is quite hard for humans to master, and figuring out the problem combo sequence will also take a lot of trials for humans (imagination) and machines (simulation). There are a lot of things to control, especially if you buy a Refresher and Aghanim. So, by random exploration, what are the chances of successfully pulling off those long combos? Here are some mad ones:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FyNrRoZ3UfJA%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DyNrRoZ3UfJA&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FyNrRoZ3UfJA%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/ecd17b9e8d4e457eca9db00882e391d6/href">https://medium.com/media/ecd17b9e8d4e457eca9db00882e391d6/href</a></iframe><ul><li><em>terrain exploitation-path blocking</em>: We have seen games where Venomancer’s ward blocks a path to prevent enemy from escaping. A narrow lane is easy to block, like the replay below, but a harder one is to block paths in between trees (unfortunately I could not find the replay). A new comer may think the trees in DotA are just for cosmetics, but a pro player actually knows where certain trees are, where paths exist among trees, if some lanes are narrow enough to block, etc. These can be explored by the algorithm with sufficient simulation.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FxkBwcYTOY-o%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DxkBwcYTOY-o&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FxkBwcYTOY-o%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/975caaf66ba10b9de03de1caf9ea13d3/href">https://medium.com/media/975caaf66ba10b9de03de1caf9ea13d3/href</a></iframe><ul><li><em>terrain-exploitation — river:</em> river is narrow, with banks on both sides. You can hook people over to your side and gank up on them, or corner your enemies in the river. An interesting double-hook replay below:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FDejAbpSkUmo%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DDejAbpSkUmo&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FDejAbpSkUmo%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/4852df65979a9bfc1fd4aab144758923/href">https://medium.com/media/4852df65979a9bfc1fd4aab144758923/href</a></iframe><ul><li><em>terrain-exploitation — Roshan pit</em>: the pit can be extremely dangerous, and may win or lose your team 6 Million USD. The combo below made EG the champion of TI 5. Combos like these can of course be learned by the AI.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F3ElXGllTpp0%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D3ElXGllTpp0&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F3ElXGllTpp0%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/70698131a4a08df60d65633162f4287c/href">https://medium.com/media/70698131a4a08df60d65633162f4287c/href</a></iframe><h4>Creative (One-shot) Strategies</h4><p>DotA TI events are so much fun to watch because of all kinds of crazy, inventive things those top players can pull off. A lot of them have actually never been done before, but came as a split-second light build moment from the players. These are extremely rare events, but it is precisely that reason which makes them so memorable, and separates TI from normal pro matches.</p><ul><li><em>Wisp juke</em>: In the replay below, Wisp is about to get teleported to its original place, and enemy heroes were waiting to slaughter it. When in the base, Wisp buys a Shadow Blade, and triggers it just on time to become invisible and escapes from the enemies. This strategy is uncommon, and it changes the build of the hero as well, but trading gold sacrifice for a life can make a huge difference in TI.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fx_TfBZoXDZQ%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dx_TfBZoXDZQ&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fx_TfBZoXDZQ%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/f14e4ca63ac840b5f1d6a82fe130435b/href">https://medium.com/media/f14e4ca63ac840b5f1d6a82fe130435b/href</a></iframe><ul><li><em>Fountain hook abuse</em>: Navi is one of the most creative teams out there. In a TI game which they were losing, a Pudge-Chen fountain hook combo helped turn the tide and secure Navi a comeback. The combo was later considered as a glitch, and subsequently removed from the game. We have seen deep RL discover various game exploits with the Atari games. DotA has quite a lot of these discovered over time as well, so I’m really eager to see if the agents reproduce/invent these unusual scenarios, also known as abuses sometime. However, they can be so unusual that they cannot readily be exploited repeatedly by AI without knowing their significant and how to reproduce; but humans immediately notice and abuse them only after seeing them once. One-shot learning is very crucial here.</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fd6H-HEpnlk8%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dd6H-HEpnlk8&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fd6H-HEpnlk8%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/eeb759d62e89e796381fe341a3da10fa/href">https://medium.com/media/eeb759d62e89e796381fe341a3da10fa/href</a></iframe><ul><li><em>gamble:</em> Invoker’s Sunstrike, Pudge’s Hook, Mirana’s Arrow, etc.; these actions can be targeted even without vision on enemy heroes, so they are often used to finish off heroes that would have escaped otherwise. Because they are done in the blind, it is hard for random actions to explore and exploit. First they need to know where the escaping heroes may go, then know where to place their bets. Only sometime an action may produce good outcome, so overall in training, these actions may seem bad (such as wasting mana and cooldown) to the algorithm. However, from experience just a few times, humans know that these actions can be promising, and will gamble for it. Some are shown below:</li><li>Dendi is the world’s best Pudge player, and it’s clear why. His hooks are calculated (a lot of mind game), and he hooks blind sometime too. With training of course, one can learn those intuitions as well, although they are not going to be perfect:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FPvKJ0LLUCSg%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DPvKJ0LLUCSg&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FPvKJ0LLUCSg%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/beb39610c470cf565ffb7b89a108ed5f/href">https://medium.com/media/beb39610c470cf565ffb7b89a108ed5f/href</a></iframe><ul><li>Invoker’s Sunstrike has global range, and the amazing kills are done when enemy hero is already nearly back to its base to heal:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FJuWbWbWZ0hM%3Fstart%3D340%26feature%3Doembed%26start%3D340&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DJuWbWbWZ0hM&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FJuWbWbWZ0hM%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/c7732eb5516a473f910cc40fbc2f806f/href">https://medium.com/media/c7732eb5516a473f910cc40fbc2f806f/href</a></iframe><h4>Plain Creative Styles</h4><p>Creativity combined with mastery is really what sets some players apart. There are ways to play a hero in such an unorthodox manner, that some may not consider them as common or optimal. I suspect these are just really narrow bands in the strategy space for the algorithm to come across and exploit. Some of the most creative, uncommon, masterful players play like no one else does:</p><ul><li>AR1SE has the most unusual Magnus style, with skill combos enemies can’t run from:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FGwaRkqxpyJE%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DGwaRkqxpyJE&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FGwaRkqxpyJE%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/518a9c7a64d1723d94e238503bb9d01f/href">https://medium.com/media/518a9c7a64d1723d94e238503bb9d01f/href</a></iframe><ul><li>Dendi is just plain fun to watch:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FlOC16qzJh1M%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DlOC16qzJh1M&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FlOC16qzJh1M%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/23ac7fb8efd784840a702db00897bdca/href">https://medium.com/media/23ac7fb8efd784840a702db00897bdca/href</a></iframe><ul><li>Mushi is brutal and has no mercy:</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fu7iTNUkdMcQ%3Fstart%3D98%26feature%3Doembed%26start%3D98&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Du7iTNUkdMcQ&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fu7iTNUkdMcQ%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/3ea6f6f4a1a0f693dfda5a375a3285f1/href">https://medium.com/media/3ea6f6f4a1a0f693dfda5a375a3285f1/href</a></iframe><ul><li>Sing Sing is one of the most <em>unserious</em> players. If you watch his pub stream, he usually just tries out stupid things, but they result in really interesting strategies. I bet he learns a lot from his fooling around too, although they are usually non-optimal, i.e. any algorithm that has nearly converged will not try out those stupid things. The first video is how he plays seriously, the second is when he trolls in pub. <em>WARNING: he cusses a lot.</em></li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F-iqf7i77ad0%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D-iqf7i77ad0&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F-iqf7i77ad0%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/d12229cf2aaa9b17d0b1a005d6dc4a1a/href">https://medium.com/media/d12229cf2aaa9b17d0b1a005d6dc4a1a/href</a></iframe><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FxMIKHTuhGPI%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DxMIKHTuhGPI&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FxMIKHTuhGPI%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/7a0d600c15260714015f7870cc04786a/href">https://medium.com/media/7a0d600c15260714015f7870cc04786a/href</a></iframe><h4>Conclusion</h4><p>OpenAI acknowledges there are still gaps to be addressed. However, I’m not so sure if all of the challenges laid out above can be tackled with vanilla PPO and massive compute. If their goal is to just see how far they can push it, then there are problems above that are inherently out of reach from the algorithm. Given the timeframe, seems like they will stick with PPO some more feature engineering. Then, I’ll say that the TI champions will win against Five.</p><p>Perhaps next year when better techniques which address exploration, reward design, planning, one-shot learning, etc. are combined, they’ll match TI-level play more closely. Either way, I’m very excited for their next game at TI 2018. Good luck OpenAI!</p><p><em>P/S: I might alsowrite about hero draft and item build, with link to multitask and transfer learning, if time permits.</em></p><p><em>update: the next post is now available:</em></p><p><a href="https://medium.com/@kengz/dota-five-solving-the-global-skill-problem-5d521651667c">OpenAI Five DotA: Solving the Global Skill Problem</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7556a3af1adc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Falsifiability and General Turing Test]]></title>
            <link>https://medium.com/@kengz/falsifiability-and-general-turing-test-a0a5d059f5b4?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/a0a5d059f5b4</guid>
            <category><![CDATA[agi]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[paradigm-shift]]></category>
            <category><![CDATA[turing-test]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Tue, 24 Jul 2018 00:15:47 GMT</pubDate>
            <atom:updated>2018-07-24T00:19:25.287Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Another continued note to my coauthor.</em></p><p>For any scientific theory to be considered truly scientific, it must be falsifiable. That is, there must exists test for which if it fails, the theory is rejected. Usually, the test provides a prediction tied to some observables; we design and perform experiments to observe the result and check for its agreement with prediction by some confidence level. The test is usually casted in a positive light, in the sense we predict a result which “confirms” the theory. But the main mechanism at work is actually rejection, that is, we only let the theory remain <em>as long as</em> we do not observe results which contradict it; otherwise we say it is falsified and toss it out.</p><p>Falsifiability is the corner stone of every modern scientific discipline. The ether theory was rejected after the Michelson-Morley interferometer experiment, which paved way for Einstein’s Special Relativity. EPR paradox together with classical mechanics was proved to be only an approximation theory after the Bell’s inequality test, which solidified acceptance for quantum mechanics during its early days.</p><p>In fact, falsifiability is the driving force behind every scientific revolutions. Every time, a new paradox emerges and plunges science into crisis. Scientists will first attempt several ad hoc fixes, but these may not survive and they may discover even more paradoxes in the process. Eventually, an replacement theory which directly tackle and resolve the paradoxes emerges and become accepted. It is important to note that the old theory does not always become obsolete; they become approximate theories of the new ones under special cases, for a lot of their components remain valid in the cases in which they were observed; these only become invalid in new settings which the paradoxes appear. For example, Newtonian mechanics is a special case of Special Relativity when the velocities are not close to the speed of light. This is why Newtonian physics is still being used widely; only when dealing with high velocities do we start correcting for relativistic effects. That said, besides resolving the paradoxes, a new theory must still accommodate all of the old theory as its subset or restriction. This is called the correspondence principle. Reality does not change; we only discover more of it in more extreme conditions.</p><p>For the falsifying mechanism to work, there must exists some strong objective criteria; otherwise the theory cannot be tested by experiments and fringes on the unscientific side.</p><p>Is the Turing test scientific? Is it falsifiable with sufficiently strong objective criteria? Notice that in artificial intelligence, there have been algorithms which pass the Turing test, in several forms. However, we would not really consider them to be intelligent. Another really bad habit in A.I. is that we propose a certain criteria to be the real manifest of artificial (general) intelligence, but when some algorithms finally attain them, we realize they are not and cease to call them A.I. The fact that today we have to use “artificial general intelligence” (AGI) instead of just “artificial intelligence” is itself a product of that habit. The endless criteria-chasing scenario is a weak form of paradox — something is defined as AGI; it is achieved; now it is not AGI. A common joke is “a definition for AGI something we can never achieve now”.</p><p>Certainly, every form of Turing test or criteria for intelligence we propose must satisfy the correspondence principle. So, we can say that there exists some eventual superset of these future criteria that will finally, truly be the test for general intelligence. But, how far is that? How do the new tests stand with respect to the older ones, and do they correspond? Are they just ad-hoc modifications or extensions? Most importantly, do any of them aim to address the AGI criteria paradox?</p><p>When we ask “how far are we from AGI?” the question should not be taken subjectively, as in “it feels like 10 years”, “we are getting close”, etc. It should be considered objectively, as any scientific question should be. We need to know what are the tests that have been passed, the tests proposed that are yet to be passed, and the tests we have yet to propose. What are the gaps among these sets of tests, which reflect the gaps to AGI.</p><p>The primary problem is, of course, that we do not know enough about intelligence to ask sufficiently critical questions. We do not currently have a theory of intelligence, let alone knowing the crucial characteristics or components of intelligence. But, this shall not be a hindrance. Just as any scientific theories mentioned above were unknown, and it was the paradoxes observed and the questions subsequently asked which led us to them. It was the scientific method applied on the long established, albeit imperfect, foundation.</p><p>At many times, it was one or a few particularly troublesome observations which sent a scientific theory right before its revolution into crisis. Einstein noted that absolute time made little sense, and by simply fixing the speed to light to be constant (a very counterintuitive idea) the entirety of Special Relativity can be derived using simple algebra. The classical theory applied to blackbody radiation predicted infinite energy, which violates the conservation of energy, and the solution was another counterintuitive idea of seeing radiation energy transmitted in quanta instead of in continuum; this eventually got developed into quantum mechanics. There are examples of paradigm shift — a phrase coined by Thomas Kuhn in The Structure of Scientific Revolutions.</p><p>This shows there needs not be a full theory in place. We just need a partial theory to provide a direction of investigation, then some experiment and discovery of paradox, a crisis, and finally its resolution. This is not to say that scientific theories are founded on paradoxes; the entire field of science is built progressively on the same paradigm; but when crisis arises and shakes an entire scientific field to its core, there will always be a paradigm shift to lay the foundation of the new scientific theory.</p><p>Coming back to our main topic, there is no Theory of Intelligence, but we do have some partial theories — Turing Machines, classical AI, machine learning, control theory, linguistics, evolutionary methods, psychology, Piaget’s theory of cognitive development, Tenenbaum’s Intuitive Theories, Heidegger’s Being and Time, and so on. What we do not (yet) have is a paradox in the traditional sense, although we may or may not end up with one as we begin to make progress in understanding intelligence. Intelligence, or cognitive science, feels markedly different from these traditional sciences. We do not have the same mechanism in place to integrate, build, extend, test, and falsify existing theories. Each theory claims its own narrow domain, safe from the others. Some of them are not subject with strict objective standards, as we will discuss below. Some may argue it cannot be as strictly objective as the natural sciences, but when combined with one of the most precise discipline, namely computer science, it has to stand up to that level of rigor.</p><p>Currently, the problem is that we keep missing the target. It is not a problem with the target per se, but with the way which we mark the target, i.e. the Turing tests we choose to carry out. If we push the tests to extreme cases, we can quickly see the paradoxes. With conversational test, a rule-based system equipped with a large database of every recorded pair of question-response from a person can beat it. The same is true for other forms of Turing test, such as image or sound-based ones — if brute-force, high resolution, high quality output produced by some machine which we consider to fail the test without a doubt, even if it’s practically hypothetical but theoretically possible.</p><p>With this in mind, it may still be hard to do a check on our Turing tests, simply because we are quite unused to how far “Turing-failing subjects” can go when equipped with a lot of compute resources. It is now clear that we can have these kinds of pseudo-intelligent behaviors which pass the Turing test of its time but not generally accepted a truly intelligent. Board games like chess and more recently, Go, used to be thought as the cornerstone of intelligence, but turns our we can solve them by throwing a lot of compute resources at some optimization and search algorithms. An even more extreme example is OpenAI’s 5vs5 DotA agents, with a staggering 120,000 CPUs used to train on centuries worth of game play. However we cannot consider these as AGI.</p><p>The first problem with Turing tests is that they are not falsifiable on their own. Every time when it gets passed and we don’t like it, we move the target to something harder. There is currently no way to check if a proposed test will be the true Turing test, i.e. one which only humans and equivalent AGIs can pass. We cannot falsify the test. Since to some extend experiments/tests are manifestations of some theory, we also cannot falsify the corresponding theory. What we do is just wait until it gets passed, judge if we “like” the subject, then verify or reject the test. This makes the tests quite useless to measure AGIs, although it can measure partial intelligence as some form of intermediate tests, so at least we have that. There should exists some criteria by which proposed Turing tests are tested against to discern whether or not it tests for general intelligence, or just some restricted aspects of it. For example, the conversational Turing test that was passed should be framed as restricted conversational test, with domain and knowledge scope in the subject’s responses as restriction (the subject which passed it pretended to be a young child, which excuses it from some questions). Perhaps there needs to be a “general Turing test” to distinguish it from the other Turing tests that have been passed, just like how we now have to use “artificial general intelligence” instead of “artificial intelligence”. So, Turing test would test for artificial intelligence, and general Turing test would test for artificial general intelligence, and the falsifiable criteria should check if the test is indeed general; and if the criteria come out false, the test is not general, i.e. restricted. There should exists some Turing test checks as falsifiability criteria for the generality of proposed Turing tests.</p><p>The second problem is also the most glaring one: there is no objective criteria, only subjective human judgements as proxy. This owes to the fact that we do not yet know how to properly measure intelligence, and what should be measured. There always needs to be a human proxy to provide subjective results, to pass or fail the subject. The less objective a theory is, the harder it is to be falsified. A fortune teller will always be right because the trick is to not make extremely accurate predictions. Predicting that the sun will rise tomorrow at 6:21am is precise, objective and falsifiable, whereas predicting that the sun will rise in the morning is safe, subjective, and non-falsifiable. When constructing Turing tests, we need to be like the former, and not be like the latter just for the fear of failure. A precise prediction may come out wrong, but the mistake will allow us to correct our theory. For now, the Stanford-Binet IQ test is an objective one, but it only measures a very narrow range of cognitive ability. More human-free objective tests like the Winograd schema and SHRLDU should be developed.</p><p>The third problem is the lack of restrictions for the test. Most of the proposed tests are open-ended, and so they do not prevent pseudo-intelligent subjects from cheating on the test. We have only prescribed what intelligent subject can do, but we never specified how it must do it or what restrictions must it be placed under. Think back in college, when your professor says you are allowed to have one sheet of notes to refer during the test, smart kids find workarounds. First they try to bring in a ridiculously large sheet of paper, then the professor restricts it to letter-size. Then they will ask if it could be double-sided, or it could be color-filtered (so that multiple pages can be written and viewed via filters on the same sheet), or if there’s restriction on the size of handwriting, and so on. Similarly, without restrictions, the Turing test subject can employ a ridiculous amount of compute resources, or pretend to be a young child to circumvent harder questions, and so on. Another side effects of the lack of restrictions is the same behavior we think only a truly intelligent subject can perform suddenly becomes doable for a pseudo-intelligence as well. Search algorithms with massive compute power or data can win Jeopardy, difficult board games, computer games, and Turing tests. Without restrictions, tests are quite meaningless in telling apart true and pseudo-intelligence.</p><p>The fourth problem with Turing test is that it is graded on a pass-fail, i.e. a binary scale. Intelligence is not binary; it ranges from “dumb as a rock”, a swimming Amoeba, a self-flushing toilet, a mosquito, a rat, a dog, to a human. Our canine friends are intelligent; although they cannot speak with us, we can still communicate, but they will fail the Turing test. When using such a coarse binary scale, we are blind to the intermediate levels of intelligence and the partial forms which could yield a lot more insights. When erecting a skyscraper, we don’t build only the top floor then choose to build this below it. Intelligence is measured on a spectrum, and so the tests shall reflect that. Piaget’s work informed us clearly on that, but we do not have Turing tests which correspond to the cognitive developmental stages he recorded.</p><p>The fifth problem is the narrowness of Turing tests. This relates to why a subject can cheat and pass the Turing test. The narrowness of Turing tests also means that we are not testing many aspects of intelligence we know are crucial, whether independently or wholly. It does not test for learning, inference, concept transfer, analogy, generalization, etc. This pertains to the “general Turing test” discussed in problem one. Intelligence is multi-faceted, and to be intelligent is to master and integrate all these different aspects. Imagine if a person can only do one thing extremely well, such as arithmetics, but cannot literally anything else like speaking, feeding, navigating, etc., then there is something seriously wrong. However we do not feel as strongly or critical about our algorithms when they only excel in literally one aspect. The conversational Turing test should not only be done via digital text, but be integrated with other dimensions such as spatial coordination, motor control, object recognition, etc. For example, the Winograd schema “The trophy would fit in the brown suitcase because it was not too big. What was not too big?” can be combined with a followed up instruction “Now try to put it in.” by giving the subject an arm to control, a vision module to see, and an actual arena with the objects (multiple suitcases, a trophy, other random objects). Since it would test for grounded semantics, we can call this the “grounded Winograd schema”. If someone who has never encountered an apple reads all about it on Wikipedia, we do not consider the person to completely understand the concept of “apple”; likewise for machines. We can say that understanding completely is the sum and integration of understanding individually from multiple independent channels. Understanding, and general intelligence as per the name, works generally, across channels and domains. This relates to the concept of semantics grounding (to be discussed separately), which requires multiple perception/motor channels. The test must examine the subject’s understanding of the same concept in different channels to make sure it is more robust, more complete.</p><p>When Alan Turing described the test for intelligence, it was not a complete, rigorous pursuit, and there was no objective criteria, restrictions, metrics defined. In other words, it was not a rigorous science. We need to fix it.</p><p>To summarize, first, there needs to be a list of falsifiability criteria, i.e. Turing test checks, for any proposed Turing tests to check of they are general Turing tests, or restrictions in some aspects. Second, the Turing test checks and the tests needs to have more objective metrics and less subjective ones, except for qualitative criteria wherever necessary. Third, to prevent loopholes exploitable by pseudo-intelligence, the tests shall also include restrictions, with compute resource as a good start. Fourth, the metrics for intelligence needs to reflect the fact that it is distributed on a spectrum and move away from the binary measurement. Fifth, Turing tests need to move away from the narrow, single-domain focus into a wider, integrated, and more general form.</p><p>A less restricted Turing test proposed from above is the grounded Winograd schema. To falsify it from being a general Turing test, we can clearly see that it does not account for the full aspects of intelligence, but it tests common sense, linguistics, visual perception, motor control, semantics grounding, and a few more things such as spatial coordination, shape-understanding, generalization, etc. The falsifying criteria alone invite further discussions after this. Winograd schema is objective, since it is easy to define the test score by the success percentage or fraction of task completed; it also gives us the non-binary, spectral metric. We need to restrict the amount of compute used on tiny subset of the schema. The cross-domain test itself tests more than just the independent parts, as it requires the integration of parts to solve the problem properly. There should also be more test tasks — simply add more objects to the environment, and invent more test statements for the subject. Then, we can slowly expand the test across domains by adding new channels of perception/motor, new types of tasks such as conversation about the environment, new factors such as metabolism, survival objectives, multiple agents, communication, and more.</p><p>This started from the thought “is the Turing test and its corresponding theory falsifiable?” and ended with the list of problems above. There are still a lot to work out, especially for the complete falsifiability criteria, and there are more thoughts on grounding yet to be written. For a near start, we now have the tool to build this entire test in a simulation (with Unity, RL, NLP, robotics), and the grounded Winograd test in on the roadmap for SLM Lab.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a0a5d059f5b4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Stages of Semantics Grounding]]></title>
            <link>https://medium.com/@kengz/stages-of-semantics-grounding-3cad04e390c5?source=rss-7f13442b032e------2</link>
            <guid isPermaLink="false">https://medium.com/p/3cad04e390c5</guid>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[semantics]]></category>
            <category><![CDATA[philosophy]]></category>
            <category><![CDATA[grounding]]></category>
            <dc:creator><![CDATA[Wah Loon Keng]]></dc:creator>
            <pubDate>Thu, 19 Jul 2018 06:31:26 GMT</pubDate>
            <atom:updated>2018-07-19T06:31:26.097Z</atom:updated>
            <content:encoded><![CDATA[<p><em>This is a correspondence to my coauthor.</em></p><p>Results about AlphaGo and OpenAI dota this year showed how far computation can be pushed, when large amount of complexity is tackled. It is also blurring the line between what I used to think as purely mechanical, lifeless optimization processes and our components of mechanisms. Likely our intelligence is emergent of many of these components, although it cannot be at such extreme scale (crazy-deep tree search, super long training, we can’t process that much info). Scale may make up for a certain things, but not everything. There are still components missing. Just as it is naive to think if we throw more compute at deep learning AGI will emerge.</p><p>A full circle back to semantics grounding. Thought about the outline for designing an intelligent agent we had ago that was built on some training/eval method, a human knowledge base, semantics grounding, evolution. I’d still draw a very similar design now, but I’m recently thinking about about what is the most crucial part that is missing.</p><p>The most basic component is still semantics grounding. For a creative can be stupid and unable to do all the fancy computation, but something common to many lifeforms is the ability to ground semantics. The main differences in the intelligence scale is a few folds, and these differences can be listed as stages toward general intelligence:<br>1. how many basic categories can a creature form? This is the easiest, i.e. direct point and label. This is limited by how many things a lifeform can point to, i.e. perceive (Heidegger’s throwness and biological capacity). Example: baby learns about food, papa, mama.<br>2. can it form compositional categories? This is impossible without sufficient base categories. That’s why mosquitos are stupid. This is a category-bootstrapping mechanism to form even more categories. This is easier as it just involves identifying the compositional categories and assigning labels to them. This is the precursor to intelligence. Also this is creation of new compositional categories, and it should learn to experiment with different combinations, or even identify novel combinations when encountering them (how many things are invented by accident). Example: baby moves arm by exploration, contacts and moves object; this composed concept is “pushing”, and baby will keep using it. Composition can be less abstract too, such as “apple cider”.<br>3. can it transfer categories by analogy? This require even more categories, and clusters of categories, so analogy among clusters can happen. It is also a category-bootstrapping mechanism. semantics grounding become “stabler” when analogizing can happen, as one symbol’s grounding is expanded. Think “if you understand something, u can explain it in many different ways”. There’ll be some critical number of the ways in which a symbol (concept) is understood, it can generate endless examples. i.e. “if you full understand something, you can explain it in all the possible ways”. Transfer and composition allows for horizontal expansions (add more ground concepts) and limited vertical expansion (add more compositional, higher level concepts). Example: baby now learns that she can control her legs too, and applies “pushing” from arms to legs. In general a lot of our problem solving are analogy-transfer.<br>4. Finally, can it create category generalization? Can it level-jump and meta-generalize, i.e. generalize recursively (like how I always do :P). This will be the final component for completeness. The categories can now suddenly become compactly organized in more abstract symbols. Whereas in the previous stage we can only have horizontal and vertical network of categories, now we can have recursive, generative categories. An example is how we humans have not seen all the integers in our life, yet we can produce any new integer when asked to, because we have a generative, generalized concept of numbers. We suddenly have the power to touch infinity, because a generalization is both generative and compact (just symbols). When we have this generative ability and recursion, we can also cross-apply categories, imagine novel compositions, analogies, and so on. Example: many different controls of body generalized into “movement”; explore different body movements give rise to body-coordination such as movement, or more advanced application such as rock climbing and yoga. Another example is learning counting &gt; arithmetics &gt; multiplication &gt; exponentiation &gt; tetration &gt; n-ation, where each level is a generalization of the concept before it, and the entire chain is an example of meta-generalization. Meta-generalization may not always happen because it can be subtle, e.g. how not everyone thought about the generalization chain above after they have learned exponentiation.</p><p>These are the theoretical outlines. The less theoretical outline I was thinking are the supportive mechanisms to allow the above to emerge. This again goes back to the “complexity matters” theme, because we can have a Turing-complete set of functions, but it still won’t do those things. These mechanism can include NN architecture, algorithms, curriculum, tests, etc.</p><p>So, the most basic test for grounding I thought of was Hydra-network, and curriculum up to stage 2 (composition). The separation and sharing of neuron modules sourcing from different heads (the PowerNet example) should capture composition. With some luck, we may even push towards stage 3 with this architecture alone, but I doubt it will be successful for rich domains.</p><p>One reason of failure is related to why the above will fail with stage 4. Recursiveness is not built in, and the current mode interaction between plain network and the environment only goes in 1 direction, i.e. input. But RL can close the loop by allowing interaction. Even then, it still needs the necessary perception/motor (I/O) components, for grounding is essentially grounding via these (missing category cannot be made up if there is not preceptor for it, e.g. how we cannot ask a born-blind person to imagine colors). So, we need I/O, and we need a network architecture and training/weight update methods which can tame the complexity of the tasks (it is not very good now, obviously, given the data-hunger of our NN methods).</p><p>I still have some thoughts above semantics grounding itself, and its basic mechanisms, what it means for something to be grounded, etc. They are brewing in my brain now. Till next time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3cad04e390c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>