<?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 Benjamin on Medium]]></title>
        <description><![CDATA[Stories by Benjamin on Medium]]></description>
        <link>https://medium.com/@benjamin22-314?source=rss-b9a3ad00eeea------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*oDDZQ1mctqlJ9g5oNqIeOA.jpeg</url>
            <title>Stories by Benjamin on Medium</title>
            <link>https://medium.com/@benjamin22-314?source=rss-b9a3ad00eeea------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 03:09:15 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@benjamin22-314/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[Automating Test Driven Development with LLMs]]></title>
            <link>https://medium.com/@benjamin22-314/automating-test-driven-development-with-llms-c05e7a3cdfe1?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/c05e7a3cdfe1</guid>
            <category><![CDATA[code-generation]]></category>
            <category><![CDATA[llm-applications]]></category>
            <category><![CDATA[genai]]></category>
            <category><![CDATA[tdd]]></category>
            <category><![CDATA[llm]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Sun, 21 Jul 2024 01:02:59 GMT</pubDate>
            <atom:updated>2024-07-21T04:34:26.739Z</atom:updated>
            <content:encoded><![CDATA[<p>Before ChatGPT, my process for writing a function was to write it, then remember I try to do Test Driven Development (TDD) and write the unit tests. If the function was something tricky, I would probably need to consult Stack Overflow. Then I would begin the process of finding the failing unit tests, updating the function (or the unit test if there was a bug in it), and repeating until all the unit tests passed.</p><p>LLMs have sped up the writing parts of the process. I can describe what I want my function to do, and ask the LLM to write the function and unit tests. Now more of my time is spent debugging the function and unit tests instead of writing them. I decided to see if I could automate this part of the TDD process too. To restrict the scope of my project, I focus on functions that use <a href="https://en.wikipedia.org/wiki/Regular_expression">Regex</a>. All the code shared in this blog post and more is available in this <a href="https://github.com/benjamin22-314/regex_gen">repository</a>.</p><h4>Which model to use?</h4><p>I would have preferred to use Anthropic’s Claude Sonnet 3.5, but Anthropic only gives businesses access to their API, they don’t give individuals access, so I went with OpenAI’s models. I tested out the gpt-3.5-turbo and the gpt-4o models with a moderately difficult regex request.</p><blockquote>Write a python function that uses regex to extract emails (including instances of ‘name at email dot com’) from a text. Use pytest to write useful unit tests.</blockquote><p>Here is the code to query the OpenAI API;</p><pre>from openai import OpenAI<br><br>client = OpenAI()<br><br>completion = client.chat.completions.create(<br>  model=&quot;gpt-3.5-turbo&quot;, # &quot;gpt-4o&quot;,<br>  messages=[<br>    {&quot;role&quot;: &quot;system&quot;, &quot;content&quot;: &quot;You give short and best practice python code.&quot;},<br>    {&quot;role&quot;: &quot;user&quot;, &quot;content&quot;: &quot;&quot;&quot;<br>      Write a python function that uses regex to extract emails<br>       (including instances of &#39;name at email dot com&#39;) from a text.<br>      Use pytest to write useful unit tests.<br>      &quot;&quot;&quot;<br>}<br>  ],<br>  temperature=0,<br>)<br><br>print(completion.choices[0].message.content)</pre><p>gpt-3.5-turbo’s output;</p><pre>```python<br>import re<br><br>def extract_emails(text):<br>    email_pattern = r&#39;\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Z|a-z]{2,}\b&#39;<br>    emails = re.findall(email_pattern, text)<br>    return emails<br><br># Unit tests using pytest<br>import pytest<br><br>def test_extract_emails():<br>    text = &quot;Contact us at email@example.com or name at example dot com for more information.&quot;<br>    assert extract_emails(text) == [&#39;email@example.com&#39;, &#39;name at example dot com&#39;]<br><br>    text = &quot;No emails in this text.&quot;<br>    assert extract_emails(text) == []<br><br>    text = &quot;Multiple emails: test@example.com, another.email@test.com&quot;<br>    assert extract_emails(text) == [&#39;test@example.com&#39;, &#39;another.email@test.com&#39;]<br><br>    text = &quot;Invalid email: test@example&quot;<br>    assert extract_emails(text) == []<br><br>if __name__ == &quot;__main__&quot;:<br>    pytest.main()<br>```<br>This code defines a function `extract_emails` that uses regex to extract emails from a given text. It also includes unit tests using pytest to ensure the function works as expected.</pre><p>gpt-4o’s output;</p><pre>```python<br>import re<br><br>def extract_emails(text):<br>    # Regex pattern to match standard emails and &#39;name at email dot com&#39; format<br>    pattern = r&#39;[\w\.-]+@[\w\.-]+\.\w+|[\w\.-]+\s+at\s+[\w\.-]+\s+dot\s+\w+&#39;<br>    <br>    # Find all matches in the text<br>    matches = re.findall(pattern, text)<br>    <br>    # Normalize &#39;name at email dot com&#39; to &#39;name@email.com&#39;<br>    normalized_emails = []<br>    for match in matches:<br>        if &#39; at &#39; in match and &#39; dot &#39; in match:<br>            normalized_emails.append(match.replace(&#39; at &#39;, &#39;@&#39;).replace(&#39; dot &#39;, &#39;.&#39;))<br>        else:<br>            normalized_emails.append(match)<br>    <br>    return normalized_emails<br>```<br><br>### Unit Tests with `pytest`<br><br>```python<br>import pytest<br>from your_module import extract_emails  # Replace &#39;your_module&#39; with the actual module name<br><br>def test_extract_emails():<br>    text = &quot;&quot;&quot;<br>    Here are some emails: test.email@example.com, another.email@domain.org.<br>    Also, consider this format: user at example dot com and admin at domain dot org.<br>    &quot;&quot;&quot;<br>    expected = [<br>        &#39;test.email@example.com&#39;,<br>        &#39;another.email@domain.org&#39;,<br>        &#39;user@example.com&#39;,<br>        &#39;admin@domain.org&#39;<br>    ]<br>    assert extract_emails(text) == expected<br><br>def test_no_emails():<br>    text = &quot;This text contains no emails.&quot;<br>    assert extract_emails(text) == []<br><br>def test_mixed_formats():<br>    text = &quot;&quot;&quot;<br>    Mixed formats: first.last@domain.com, first at last dot com, and another.one@domain.org.<br>    &quot;&quot;&quot;<br>    expected = [<br>        &#39;first.last@domain.com&#39;,<br>        &#39;first@last.com&#39;,<br>        &#39;another.one@domain.org&#39;<br>    ]<br>    assert extract_emails(text) == expected<br><br>def test_edge_cases():<br>    text = &quot;&quot;&quot;<br>    Edge cases: user@sub.domain.com, user at sub dot domain dot com, and invalid@domain, user@domain.<br>    &quot;&quot;&quot;<br>    expected = [<br>        &#39;user@sub.domain.com&#39;,<br>        &#39;user@sub.domain.com&#39;<br>    ]<br>    assert extract_emails(text) == expected<br><br>if __name__ == &quot;__main__&quot;:<br>    pytest.main()<br>```<br><br>### Explanation<br><br>1. **Function `extract_emails`**:<br>   - Uses a regex pattern to match both standard email formats and the &#39;name at email dot com&#39; format.<br>   - Normalizes the &#39;name at email dot com&#39; format to the standard email format.<br><br>2. **Unit Tests**:<br>   - `test_extract_emails`: Tests the function with a mix of standard and &#39;name at email dot com&#39; formats.<br>   - `test_no_emails`: Ensures the function returns an empty list when no emails are present.<br>   - `test_mixed_formats`: Tests the function with mixed email formats.<br>   - `test_edge_cases`: Tests edge cases, including subdomains and invalid email formats.<br><br>To run the tests, save the function and tests in appropriate files and run `pytest` in your terminal.</pre><p>gpt-3.5-turbo’s function doesn’t even try to address the requirement to match “name at email dot com”. In November 2022, this type of output blew my mind. These days I have higher standards. gpt-4o does a good first go at writing the function, so I stuck with gpt-4o.</p><h4>Let’s get into the code</h4><p>For the rest of this blog post, I will use the following query to demonstrate how the code works;</p><blockquote>“For a given string, please extract all the email addresses. Including instances of ‘name at email dot com’, for example ‘cat at gmail dot com’ should extract ‘cat@gmail.com’ and ‘dog at hotmail dot com’ should extract ‘dog@hotmail.com’. It should should work for any email domain.”</blockquote><p>Usually I “forget” to write unit tests first, but since I’m automating the process, I may as well automate it to do best practices. Here is the function I use to generate the unit tests from the query;</p><pre>def llm_generate_unit_tests(<br>    llm: langchain_openai.chat_models.base.ChatOpenAI, query: str<br>) -&gt; str:<br>    &quot;&quot;&quot;<br>    Generate unit tests for a hypothetical function that does what is described in `query`.<br>    &quot;&quot;&quot;<br><br>    unit_test_system_prompt_string = &quot;&quot;&quot;<br>    You are a specialized assistant designed to create thorough unit tests for functions involving regular expressions (regex). \<br>    Your task is to generate comprehensive, self-contained unit tests based on a natural language \<br>    description of the function&#39;s intended behavior.<br><br>    Instructions:<br>    1. Carefully analyze the given description.<br>    2. Create diverse unit tests that cover all aspects of the function&#39;s expected behavior, including:<br>    - Basic functionality<br>    - Edge cases<br>    - Corner cases<br>    - Boundary conditions<br>    - Invalid inputs<br>    - Empty inputs<br>    - Large inputs<br>    - Special characters<br>    - Unicode characters (if applicable)<br>    - Case sensitivity (if applicable)<br>    - Multiline inputs (if applicable)<br>    - Non-matching scenarios<br>    3. If you need to use a unit test framework, use pytest.<br>    4. Write individual test functions, not a test class.<br>    5. Use descriptive test names that clearly indicate the specific scenario being tested.<br>    6. Include detailed assertions that thoroughly check expected outcomes.<br>    7. Each assert statement should have a message with the expected output and the observed output.<br>    8. Do not test input longer than 200 characters.<br>    9. For regex functions, consider testing:<br>    - Pattern matching accuracy<br>    - Capturing groups<br>    - Non-capturing groups<br>    - Lookahead and lookbehind assertions<br>    - Greedy vs. non-greedy quantifiers<br>    - Character classes and negated character classes<br>    - Anchors (start, end, word boundaries)<br>    - Flags (e.g., re.IGNORECASE, re.MULTILINE, re.DOTALL)<br>    - Escape sequences<br>    10. Do not write the actual function implementation or code to run the tests.<br>    11. Write the name of the function you are testing as a comment at the top of the code block (do not write a place holder function).<br>    12. Generate at least 10-15 diverse tests to ensure comprehensive coverage.<br><br>    Provide your response as a Python code block containing only the unit tests. \<br>    Ensure that the tests are varied and cover a wide range of scenarios to thoroughly validate the regex function.<br><br>    Example input: &quot;Create tests for a function that extracts all valid email addresses from a given text.&quot;<br><br>    Your task is to generate appropriate unit tests based on similar natural language descriptions, \<br>    focusing on comprehensive testing of regex functionality.<br>    &quot;&quot;&quot;<br><br>    unit_test_prompt = ChatPromptTemplate.from_messages(<br>        [(&quot;system&quot;, unit_test_system_prompt_string), (&quot;user&quot;, &quot;{input}&quot;)]<br>    )<br><br>    unit_test_chain = unit_test_prompt | llm | PythonCodeExtractorParser()<br>    unit_test_code_as_string = unit_test_chain.invoke({&quot;input&quot;: query})<br>    return unit_test_code_as_string</pre><p>The function takes the query, and an LLM. It creates a short chain;</p><blockquote>prompt -&gt; llm -&gt; python code extractor</blockquote><p>Here is the output, the unit tests;</p><pre># Function to test: extract_emails<br><br>import re<br>import pytest<br><br>def test_extract_emails_basic():<br>    text = &quot;Please contact us at support@example.com for further information.&quot;<br>    expected = [&quot;support@example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_multiple():<br>    text = &quot;Send an email to admin@example.com or sales@example.com.&quot;<br>    expected = [&quot;admin@example.com&quot;, &quot;sales@example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_with_at_dot_format():<br>    text = &quot;You can reach me at john.doe at gmail dot com or jane.doe at yahoo dot com.&quot;<br>    expected = [&quot;john.doe@gmail.com&quot;, &quot;jane.doe@yahoo.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_mixed_formats():<br>    text = &quot;Contact us at support@example.com or john.doe at gmail dot com.&quot;<br>    expected = [&quot;support@example.com&quot;, &quot;john.doe@gmail.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_no_emails():<br>    text = &quot;There are no email addresses in this text.&quot;<br>    expected = []<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_invalid_emails():<br>    text = &quot;Invalid emails like user@com and user@.com should not be extracted.&quot;<br>    expected = []<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_special_characters():<br>    text = &quot;Emails with special characters like user.name+tag+sorting@example.com should be extracted.&quot;<br>    expected = [&quot;user.name+tag+sorting@example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_unicode_characters():<br>    text = &quot;Emails with unicode characters like üser@example.com should be extracted.&quot;<br>    expected = [&quot;üser@example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_case_insensitive():<br>    text = &quot;Emails like User@Example.com should be extracted in a case-insensitive manner.&quot;<br>    expected = [&quot;User@Example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_multiline():<br>    text = &quot;&quot;&quot;Please contact:<br>    support@example.com<br>    or<br>    john.doe at gmail dot com<br>    for more information.&quot;&quot;&quot;<br>    expected = [&quot;support@example.com&quot;, &quot;john.doe@gmail.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_non_matching_scenarios():<br>    text = &quot;This text contains no valid email addresses like user@com or user@.com.&quot;<br>    expected = []<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_edge_case_empty_string():<br>    text = &quot;&quot;<br>    expected = []<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_edge_case_only_spaces():<br>    text = &quot;     &quot;<br>    expected = []<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_edge_case_special_format():<br>    text = &quot;Emails like user@sub.example.com and user at sub dot example dot com should be extracted.&quot;<br>    expected = [&quot;user@sub.example.com&quot;, &quot;user@sub.example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;<br><br>def test_extract_emails_large_input():<br>    text = &quot;user&quot; + &quot;a&quot; * 180 + &quot;@example.com&quot;<br>    expected = [&quot;user&quot; + &quot;a&quot; * 180 + &quot;@example.com&quot;]<br>    result = extract_emails(text)<br>    assert result == expected, f&quot;Expected {expected}, but got {result}&quot;</pre><p>Next, I have a function that takes the unit tests, and writes the function;</p><pre>def llm_generate_function_from_unit_tests(<br>    llm: langchain_openai.chat_models.base.ChatOpenAI,<br>    unit_test_code_as_string: str,<br>    query:  str<br>) -&gt; str:<br>    &quot;&quot;&quot;<br>    Generate a function that will pass the given unit tests.<br>    &quot;&quot;&quot;<br><br>    function_writer_system_prompt_string = &quot;&quot;&quot;<br>    You are a Python code generation assistant. Your task is to create a Python function that satisfies all the provided pytest unit tests. Follow these guidelines:<br><br>    1. Consider the function description and the unit tests carefully to understand the function&#39;s required behavior.<br>    2. Write a single Python function that passes all the provided tests.<br>    3. Use type hints for parameters and return values.<br>    4. Include a clear and concise docstring explaining the function&#39;s purpose and parameters.<br>    5. Follow Python best practices and PEP 8 style guidelines.<br>    6. Do not include comments within the function body.<br>    7. Ensure the function handles all edge cases and scenarios covered in the tests.<br>    8. If the tests imply the use of regular expressions, import the &#39;re&#39; module and use it appropriately.<br>    9. Provide only the function definition and its implementation, nothing else.<br><br>    Your response should be a Python code block containing only the requested function.<br>    &quot;&quot;&quot;<br>    function_writer_prompt = ChatPromptTemplate.from_messages(<br>        [(&quot;system&quot;, function_writer_system_prompt_string), (&quot;user&quot;, &quot;{input}&quot;)]<br>    )<br>    function_writer_chain = function_writer_prompt | llm | PythonCodeExtractorParser()<br>    target_function_code_as_string = function_writer_chain.invoke(<br>        {&quot;input&quot;: &quot;Function description: &quot; + query + &quot;\n&quot; + unit_test_code_as_string}<br>    )<br>    return target_function_code_as_string</pre><p>This outputs the regex function;</p><pre>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ([a-zA-Z0-9.-]+) dot ([a-zA-Z]{2,})&#39;<br>    <br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain}.{tld}&quot; for user, domain, tld in at_dot_emails]<br>    <br>    return standard_emails + converted_emails</pre><p>I also have similar LLM functions; llm_find_bug and llm_fix_bug <a href="https://github.com/benjamin22-314/regex_gen/blob/main/llm_calls.py">here</a>. At first I was tempted to have everything as one long LangChain chain, but that felt like a bad idea for several reasons;</p><ol><li>Testing — modular code is easier to test.</li><li>Readability — I don’t normally chain together disparate kinds of functions, why would I do that here?</li><li>Time to POC — much of the code I wrote for this project doesn’t need to be integrated with a chain. Why go to the effort of fitting it into the LangChain framework, when I can just write functions like I always do?</li></ol><p>So far I haven’t done anything that I couldn’t already do while logged in to OpenAI’s or Anthropic’s chatbots. If I’m going to automate the TDD process, I need to automate the running of the unit tests. As always, be careful. Running arbitrary code can be dangerous.</p><p>Here is the code that runs the unit tests;</p><pre>from langchain_experimental.tools import PythonREPLTool<br>from function_code_with_unit_tests import FunctionCodeWithUnitTests<br><br><br>class FindFirstFailingUnitTestFunctionMessage:<br>    def __init__(self, test_pass_status: bool, unit_test_name: str, output: str):<br>        self.test_pass_status = test_pass_status<br>        self.unit_test_name = unit_test_name<br>        self.output = output<br><br>    def print_message_details(self):<br>        print(&quot;\ntest_pass_status: &quot; + str(self.test_pass_status))<br>        print(&quot;unit_test_name: &quot; + self.unit_test_name)<br>        print(&quot;output: &quot; + self.output + &quot;\n&quot;)<br><br><br>def find_first_failing_unit_test(<br>    function_code_with_unit_tests: FunctionCodeWithUnitTests,<br>) -&gt; FindFirstFailingUnitTestFunctionMessage:<br><br>    for i, unit_test_name in enumerate(function_code_with_unit_tests.unit_tests):<br>        # Example code to execute<br>        message = run_unit_test(<br>            function_code_with_unit_tests=function_code_with_unit_tests,<br>            unit_test_name=unit_test_name,<br>        )<br>        if message.test_pass_status == False:<br>            return message<br>        print(f&quot;unit test {unit_test_name}() is currently passing. {i+1}/{len(function_code_with_unit_tests.unit_tests)} tests pass.&quot;)<br>    return message<br><br><br>def run_unit_test(<br>    function_code_with_unit_tests: FunctionCodeWithUnitTests, unit_test_name: str<br>) -&gt; FindFirstFailingUnitTestFunctionMessage:<br>    code_to_run = f&quot;&quot;&quot;<br><br>{function_code_with_unit_tests.unit_test_imports}<br><br>{function_code_with_unit_tests.get_function_code()}<br><br>{function_code_with_unit_tests.get_unit_test_code(unit_test_name=unit_test_name)}<br><br>try:<br>    {unit_test_name}()<br>    message = &quot;test passed&quot;<br>except AssertionError as e:<br>    message = &quot;Assertion failed: &quot; + str(e)<br>except Exception as e:<br>    message = &quot;Error: &quot; + str(e)<br><br>print(message)<br>        &quot;&quot;&quot;<br><br>    # Execute the code<br>    # print(code_to_run)<br>    output = PythonREPLTool().run(code_to_run)[:-1]<br>    if not output.endswith(&quot;test passed&quot;):<br>        return FindFirstFailingUnitTestFunctionMessage(<br>            test_pass_status=False,<br>            unit_test_name=unit_test_name,<br>            output=output,<br>        )<br>    return FindFirstFailingUnitTestFunctionMessage(<br>        test_pass_status=True,<br>        unit_test_name=&quot;Na&quot;,<br>        output=&quot;The test passes&quot;,<br>    )</pre><p>The run_unit_test runs the unit test, and the find_first_failing_unit_test function loops over all the unit tests, and stops when it finds one that fails.</p><p>Now let’s automate the TDD process;</p><pre>for i in range(10):<br><br>    first_failing_unit_test_message = find_first_failing_unit_test(<br>        function_code_with_unit_tests=function_code_with_unit_tests<br>    )<br><br>    first_failing_unit_test_message.print_message_details()<br><br>    if first_failing_unit_test_message.test_pass_status:<br>        print(&quot;All tests are passing&quot;)<br>        break<br><br>    print(&quot;Ask llm if the function or unit test needs to be updated.&quot;)<br>    bug_report_dict = llm_find_bug(<br>        llm=llm,<br>        query=query,<br>        function_code_with_unit_tests=function_code_with_unit_tests,<br>        first_failing_unit_test_message=first_failing_unit_test_message,<br>    )<br><br>    if bug_report_dict[&quot;Likely Bug Location&quot;] == &quot;Unit Test&quot;:<br>        <br>        print(&quot;The llm said the unit test should be updated.\nAsk the llm to fix the unit test.\n&quot;)<br>        updated_unit_test_code = llm_fix_bug(<br>            llm=llm,<br>            query=query,<br>            bug_report_dict=bug_report_dict,<br>            function_code_with_unit_tests=function_code_with_unit_tests,<br>            first_failing_unit_test_message=first_failing_unit_test_message,<br>        )<br>        <br>        print(&quot;Unit test before update;&quot;)<br>        print(function_code_with_unit_tests.get_unit_test_code(first_failing_unit_test_message.unit_test_name) + &quot;\n&quot;)<br>        <br>        function_code_with_unit_tests.replace_unit_test(<br>            unit_test_name=first_failing_unit_test_message.unit_test_name,<br>            new_unit_test_code=updated_unit_test_code,<br>        )<br>        <br>        print(&quot;Unit test after update;&quot;)<br>        print(function_code_with_unit_tests.get_unit_test_code(first_failing_unit_test_message.unit_test_name) + &quot;\n&quot;)<br><br>    elif bug_report_dict[&quot;Likely Bug Location&quot;] == &quot;Function&quot;:<br>        <br>        print(&quot;The llm said the function should be updated.\nAsk the llm to fix the function.\n&quot;)<br>        updated_function_code = llm_fix_bug(<br>            llm=llm,<br>            query=query,<br>            bug_report_dict=bug_report_dict,<br>            function_code_with_unit_tests=function_code_with_unit_tests,<br>            first_failing_unit_test_message=first_failing_unit_test_message,<br>        )<br>        <br>        print(&quot;Function before update;&quot;)<br>        print(function_code_with_unit_tests.get_function_code() + &quot;\n&quot;)<br>        <br>        function_code_with_unit_tests.replace_function_code(<br>            new_function_code=updated_function_code,<br>        )<br>        <br>        print(&quot;Function after update;&quot;)<br>        print(function_code_with_unit_tests.get_function_code() + &quot;\n&quot;)<br>        <br>    else:<br>        raise ValueError(&quot;bug_report_dict keys not as expected&quot;)<br><br>    unit_test_message = run_unit_test(<br>        function_code_with_unit_tests=function_code_with_unit_tests,<br>        unit_test_name=first_failing_unit_test_message.unit_test_name,<br>    )<br>    <br>    if unit_test_message.test_pass_status:<br>    <br>        print(f&quot;Unit test {first_failing_unit_test_message.unit_test_name}() now passing.&quot;)<br>    <br>    else:<br>    <br>        unit_test_code_to_delete = function_code_with_unit_tests.get_unit_test_code(<br>            first_failing_unit_test_message.unit_test_name<br>        )<br>        print(<br>            f&quot;Unable to make this unit test pass\n{unit_test_code_to_delete}It will be deleted\n&quot;<br>        )<br>        function_code_with_unit_tests.delete_unit_test_code(<br>            first_failing_unit_test_message.unit_test_name<br>        )<br>        if bug_report_dict[&quot;Likely Bug Location&quot;] == &quot;Function&quot;:<br>            print(&quot;Roll back update to function.&quot;)<br>            function_code_with_unit_tests.delete_function_changes()<br><br><br>if first_failing_unit_test_message.test_pass_status == False:<br>    print(&quot;Some tests are still not passing&quot;)</pre><p>Here is the high level logic; Find a failing unit test. Ask the LLM “is it a bug in the function or the unit test?”. If it’s a bug in the unit test, ask the LLM to update the unit test. If it’s a bug in the function, ask the LLM to update the function. If the LLM’s update doesn’t make the unit test pass, delete the unit test (but print it so the user can decide what to do with it). Do this until all the unit tests pass. Why does the for loop have a max of 10 iterations, because it’s possible for the LLM to get into an infinite loop, where fixing one unit test causes another unit test to fail.</p><p>How well does this Auto-TDD work for our “extract emails” query? I share the whole output for completeness, but feel free to skip that and read my summary of the output.</p><pre>unit test test_extract_emails_basic() is currently passing. 1/15 tests pass.<br>unit test test_extract_emails_multiple() is currently passing. 2/15 tests pass.<br>unit test test_extract_emails_with_at_dot_format() is currently passing. 3/15 tests pass.<br>unit test test_extract_emails_mixed_formats() is currently passing. 4/15 tests pass.<br>unit test test_extract_emails_no_emails() is currently passing. 5/15 tests pass.<br>unit test test_extract_emails_invalid_emails() is currently passing. 6/15 tests pass.<br>unit test test_extract_emails_special_characters() is currently passing. 7/15 tests pass.<br><br>test_pass_status: False<br>unit_test_name: test_extract_emails_unicode_characters<br>output: Assertion failed: Expected [&#39;üser@example.com&#39;], but got [&#39;ser@example.com&#39;]<br><br>Ask llm if the function or unit test needs to be updated.<br>The llm said the function should be updated.<br>Ask the llm to fix the function.<br><br>Function before update;<br>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ([a-zA-Z0-9.-]+) dot ([a-zA-Z]{2,})&#39;<br>    <br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain}.{tld}&quot; for user, domain, tld in at_dot_emails]<br>    <br>    return standard_emails + converted_emails<br><br><br>Function after update;<br>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ([a-zA-Z0-9.-]+) dot ([a-zA-Z]{2,})&#39;<br>    unicode_email_pattern = r&#39;[\w\.-]+@[\w\.-]+\.[a-zA-Z]{2,}&#39;<br><br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    unicode_emails = re.findall(unicode_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain}.{tld}&quot; for user, domain, tld in at_dot_emails]<br>    <br>    return list(set(standard_emails + converted_emails + unicode_emails))<br><br><br>Unable to make this unit test pass<br>def test_extract_emails_unicode_characters():<br>    text = (<br>        &#39;Emails with unicode characters like üser@example.com should be extracted.&#39;<br>        )<br>    expected = [&#39;üser@example.com&#39;]<br>    result = extract_emails(text)<br>    assert result == expected, f&#39;Expected {expected}, but got {result}&#39;<br>It will be deleted<br><br>Roll back update to function.<br>unit test test_extract_emails_basic() is currently passing. 1/14 tests pass.<br>unit test test_extract_emails_multiple() is currently passing. 2/14 tests pass.<br>unit test test_extract_emails_with_at_dot_format() is currently passing. 3/14 tests pass.<br>unit test test_extract_emails_mixed_formats() is currently passing. 4/14 tests pass.<br>unit test test_extract_emails_no_emails() is currently passing. 5/14 tests pass.<br>unit test test_extract_emails_invalid_emails() is currently passing. 6/14 tests pass.<br>unit test test_extract_emails_special_characters() is currently passing. 7/14 tests pass.<br>unit test test_extract_emails_case_insensitive() is currently passing. 8/14 tests pass.<br>unit test test_extract_emails_multiline() is currently passing. 9/14 tests pass.<br>unit test test_extract_emails_non_matching_scenarios() is currently passing. 10/14 tests pass.<br>unit test test_extract_emails_edge_case_empty_string() is currently passing. 11/14 tests pass.<br>unit test test_extract_emails_edge_case_only_spaces() is currently passing. 12/14 tests pass.<br><br>test_pass_status: False<br>unit_test_name: test_extract_emails_edge_case_special_format<br>output: Assertion failed: Expected [&#39;user@sub.example.com&#39;, &#39;user@sub.example.com&#39;], but got [&#39;user@sub.example.com&#39;, &#39;user@sub.example&#39;]<br><br>Ask llm if the function or unit test needs to be updated.<br>The llm said the function should be updated.<br>Ask the llm to fix the function.<br><br>Function before update;<br>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ([a-zA-Z0-9.-]+) dot ([a-zA-Z]{2,})&#39;<br>    <br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain}.{tld}&quot; for user, domain, tld in at_dot_emails]<br>    <br>    return standard_emails + converted_emails<br><br><br>Function after update;<br>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ((?:[a-zA-Z0-9-]+ dot )+[a-zA-Z]{2,})&#39;<br>    <br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain.replace(&#39; dot &#39;, &#39;.&#39;)}&quot; for user, domain in at_dot_emails]<br>    <br>    return standard_emails + converted_emails<br><br><br>Unit test test_extract_emails_edge_case_special_format() now passing.<br>unit test test_extract_emails_basic() is currently passing. 1/14 tests pass.<br>unit test test_extract_emails_multiple() is currently passing. 2/14 tests pass.<br>unit test test_extract_emails_with_at_dot_format() is currently passing. 3/14 tests pass.<br>unit test test_extract_emails_mixed_formats() is currently passing. 4/14 tests pass.<br>unit test test_extract_emails_no_emails() is currently passing. 5/14 tests pass.<br>unit test test_extract_emails_invalid_emails() is currently passing. 6/14 tests pass.<br>unit test test_extract_emails_special_characters() is currently passing. 7/14 tests pass.<br>unit test test_extract_emails_case_insensitive() is currently passing. 8/14 tests pass.<br>unit test test_extract_emails_multiline() is currently passing. 9/14 tests pass.<br>unit test test_extract_emails_non_matching_scenarios() is currently passing. 10/14 tests pass.<br>unit test test_extract_emails_edge_case_empty_string() is currently passing. 11/14 tests pass.<br>unit test test_extract_emails_edge_case_only_spaces() is currently passing. 12/14 tests pass.<br>unit test test_extract_emails_edge_case_special_format() is currently passing. 13/14 tests pass.<br>unit test test_extract_emails_large_input() is currently passing. 14/14 tests pass.<br><br>test_pass_status: True<br>unit_test_name: Na<br>output: The test passes<br><br>All tests are passing</pre><p>The first 7 unit tests pass, then the test_extract_emails_unicode_characters() unit test failed and had the following output;</p><blockquote>Assertion failed: Expected [‘üser@example.com’], but got [‘ser@example.com’]</blockquote><p>The LLM decided it was the function that needed to be updated. It updated the function, but the update didn’t make the function pass the unit test, so the unit test was deleted and the function update was rolled back.</p><p>After that, the first 12 unit tests pass, and the test_extract_emails_edge_case_special_format()unit test failed with the following output;</p><blockquote>Assertion failed: Expected [‘user@sub.example.com’, ‘user@sub.example.com’], but got [‘user@sub.example.com’, ‘user@sub.example’]</blockquote><p>The LLM decided the function needed to be updated. Here is the function before and after the update</p><pre>Function before update;<br>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ([a-zA-Z0-9.-]+) dot ([a-zA-Z]{2,})&#39;<br>    <br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain}.{tld}&quot; for user, domain, tld in at_dot_emails]<br>    <br>    return standard_emails + converted_emails<br><br><br>Function after update;<br>import re<br>from typing import List<br><br>def extract_emails(text: str) -&gt; List[str]:<br>    &quot;&quot;&quot;<br>    Extracts all email addresses from the given text. This includes both standard email formats<br>    and those written in the &#39;name at domain dot com&#39; format.<br><br>    Parameters:<br>    text (str): The input text from which to extract email addresses.<br><br>    Returns:<br>    List[str]: A list of extracted email addresses.<br>    &quot;&quot;&quot;<br>    standard_email_pattern = r&#39;[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}&#39;<br>    at_dot_email_pattern = r&#39;([a-zA-Z0-9._%+-]+) at ((?:[a-zA-Z0-9-]+ dot )+[a-zA-Z]{2,})&#39;<br>    <br>    standard_emails = re.findall(standard_email_pattern, text)<br>    at_dot_emails = re.findall(at_dot_email_pattern, text)<br>    <br>    converted_emails = [f&quot;{user}@{domain.replace(&#39; dot &#39;, &#39;.&#39;)}&quot; for user, domain in at_dot_emails]<br>    <br>    return standard_emails + converted_emails</pre><p>The difference between these two functions is in the regular expression pattern used in at_dot_email_pattern and the argument for the replace function for the list comprehension defined for the converted_emails variable.</p><p>After that, all (remaining) tests pass!</p><h4>Testing the tester</h4><p>When it comes to testing LLM applications, basic unit testing (shown below) is enough to give me confidence to make changes to the respective functions. If this was an application that was going to be productionised, I would also need integration tests, as well as a large number of end to end tests with different queries — to analyse the typical behaviour of the system, and where it does well and struggles. Since this is just a project for myself, I didn’t go overboard with testing.</p><pre>import pytest<br>from langchain_openai import ChatOpenAI<br>from llm_calls import llm_find_bug<br>from function_code_with_unit_tests import FunctionCodeWithUnitTests<br>from run_tests import FindFirstFailingUnitTestFunctionMessage<br><br><br>@pytest.fixture<br>def llm():<br>    return ChatOpenAI(temperature=0, model=&quot;gpt-4&quot;)<br><br><br>def test_llm_find_bug_add_function_incorrect_function(llm):<br>    query = &quot;Add two numbers&quot;<br>    function_code = [&quot;def add(a, b):\n    return a - b&quot;]<br>    unit_tests = {&quot;test_add&quot;: [&quot;def test_add():\n    assert add(2, 3) == 5&quot;]}<br>    unit_test_imports = &quot;import unittest&quot;<br>    function_code_with_unit_tests = FunctionCodeWithUnitTests(<br>        function_code, unit_tests, unit_test_imports<br>    )<br>    failing_test_message = FindFirstFailingUnitTestFunctionMessage(<br>        False, &quot;test_add&quot;, &quot;AssertionError: assert -1 == 5&quot;<br>    )<br><br>    result = llm_find_bug(<br>        llm, query, function_code_with_unit_tests, failing_test_message<br>    )<br>    assert result[&quot;Likely Bug Location&quot;] == &quot;Function&quot;<br><br><br>def test_llm_find_bug_add_function_incorrect_unit_test(llm):<br>    query = &quot;Add two numbers&quot;<br>    function_code = [&quot;def add(a, b):\n    return a + b&quot;]<br>    unit_tests = {&quot;test_add&quot;: [&quot;def test_add():\n    assert add(2, 4) == 5&quot;]}<br>    unit_test_imports = &quot;import unittest&quot;<br>    function_code_with_unit_tests = FunctionCodeWithUnitTests(<br>        function_code, unit_tests, unit_test_imports<br>    )<br>    failing_test_message = FindFirstFailingUnitTestFunctionMessage(<br>        False, &quot;test_add&quot;, &quot;AssertionError: assert 6 == 5&quot;<br>    )<br><br>    result = llm_find_bug(<br>        llm, query, function_code_with_unit_tests, failing_test_message<br>    )<br>    assert result[&quot;Likely Bug Location&quot;] == &quot;Unit Test&quot;</pre><h4>Reflections</h4><p>Claude Sonnet 3.5 is better than I am at writing prompts. I found that telling Claude what I wanted the prompt to do, and then tweaking its output worked better than writing prompts from scratch.</p><p>Anything that was possible to do without an LLM, I did without an LLM. Every LLM call adds complexity. I found myself thinking about trade offs such as:</p><ul><li>Giving the LLM as much contextual information as possible, versus giving the LLM too much irrelevant information.</li><li>Simplifying a process by asking the LLM for a long output versus how much quality might be lost if I ask for a long output.</li></ul><p>E.g. Is it better to tell the LLM about all the failing unit tests so it has more context, or just one unit test at a time so it can focus on a specific issue? I chose “one issue at a time”, as this provided an easier and more standard output to handle.</p><p>I used LangChain for the API calls, but I didn’t really need to for this project. Using the OpenAI package would have been sufficient for my purposes.</p><p>Debugging LLM calls requires lots of print statements. The LangChain company have a product called LangSmith, which tracks and monitors input/output for LLM applications. I had thought that if I didn’t make long LangChain chains, I wouldn’t need something like LangSmith. But a for loop with many LLM calls is essentially a long chain, and I can see now how a product like that would be helpful.</p><p>Costs were low. Overall I spent less than $3.</p><p>Coming up with examples where the LLM initially had a bug in the function was harder than I thought. gpt-4o is quite a strong model for code.</p><p>LLMs can’t read your mind. If I under specified the problem, the LLM would work with the ambiguity on it’s own, instead of working with me. If I decide to continue with this project, I will refactor what I’ve written into a LangChain Tool, which a Chatbot could then use. The Chatbot could ask clarifying questions, and keep the human in the loop when it came to which unit tests to delete or update.</p><p>Thanks for reading!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*c0z5mY2JwzXuDNaH" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c05e7a3cdfe1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Get All Four Toys]]></title>
            <link>https://medium.com/@benjamin22-314/get-all-four-toys-b8653c2c46c5?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/b8653c2c46c5</guid>
            <category><![CDATA[puzzle]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[combinatorics]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Sun, 26 Feb 2023 20:43:50 GMT</pubDate>
            <atom:updated>2024-07-22T11:03:08.432Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*re4QncYUPeZSJcX8EG2qSA.jpeg" /></figure><p>I recently encountered this puzzle on <a href="https://news.ycombinator.com/item?id=34897701&amp;ref=upstract.com">hacker news</a>;</p><blockquote>A fast food franchise includes a toy in their child-size meals, selected randomly. There are four different toys. How many meals do you expect to buy before you have all four toys?</blockquote><p>I was unsatisfied with the analysis and discussion, but intrigued by the puzzle, so I dove into it.</p><p>Whenever a puzzle has the word <em>expect</em> in it, this is a big clue that we need to calculate the <a href="https://en.wikipedia.org/wiki/Expected_value">expected value</a>, so let’s do that.</p><pre>E[meals until you have four unique toys] = <br>  <br>  E[number of meals until you have your first unique toy] + <br>  <br>  E[number of meals until you have your second unique toy <br>    once you have your first unique toy] + <br>  <br>  E[number of meals until you have your third unique toy<br>    once you have your second unique toy] +<br><br>  E[number meals until you have your fourth unique toy<br>    once you have your third unique toy] <br><br><br># It takes one meal to get your first unique toy.<br>E[number of meals until you have your first unique toy] = 1<br><br># There is a 3/4 chance the next meal will provide<br># a new unique toy. On average (in expectation),<br># you would expect it to take 4/3 meals to get your<br># next unique toy. A 3/4 probability multiplied by<br># 4/3 meals gives 1 unique toy (in expectation).<br>E[number of meals until you have your second unique toy <br>    once you have your first unique toy] = 4/3<br><br># Once you have two unique toys, there is a<br># 1/2 chance that next meal will provide a new<br># unique toy. This means you expect it to take<br># 2 meals to get your third unique toy.<br>E[number of meals until you have your third unique toy<br>    once you have your second unique toy] = 2<br><br># Once you have three unique toys, there is a<br># 1/4 chance that next meal will provide a new<br># unique toy. This means you expect it to take<br># 4 meals to get your fourth unique toy.<br>E[number meals until you have your fourth unique toy<br>    once you have your third unique toy] = 4<br><br>E[meals until you have four unique toys] = 1 + 4/3 + 2 + 4 = 8.3333333</pre><p>So we would expect to buy 8–9 meals before we have all four toys.</p><p>This tells us something specific about this problem. If I conduct an experiment, where I continue to purchase meals until I have all four toys, and repeat the experiment many times, I would expect the average number of meals purchased over all my experiments to be ~8.333.</p><p>But I find this answer lacking. It doesn’t tell me the probability of having all four toys after purchasing 8 meals, or any number of meals. It doesn’t tell me how many meals I should expect to buy before being more than 50% sure I’ll collect all four toys, or more than 99% sure. To answer these questions, we’ll need to delve into combinatorics.</p><p>Let’s keep these formulae handy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/714/1*z6HTqhBcHIZiU19LKSbxKA.jpeg" /><figcaption>`n` unique items. `r` selections. The two formulae on the left are without replacement. The two formulae on the right are with replacement</figcaption></figure><p>Combination —<em> How many ways can we combine these items. Order doesn’t matter.</em></p><p>Permutation —<em> How many ways can we permutate these items? Order matters.</em></p><p>Replacement <em>— When we make a selection from the available items, we return the item afterwards, to allow it to be selected again.</em></p><p><strong>What is the probability of having all four toys if I commit to buying </strong><strong>x meals?</strong></p><p>In this case, we are considering the situation where we commit to buying x meals, and won’t stop early, even if we have all four toys before the xth meal.</p><p>To calculate this, we need two things.</p><ul><li>The number of permutations of the four unique items for x meals (with replacement).</li><li>The number of permutations of the four unique items for x meals (with replacement) where we have all four toys.</li></ul><p>Why use permutations (order matters) instead of combinations (order doesn’t matter)? Because when you have replaced items, order matters. Consider flipping a coin twice. The outcomes are (HH, HT, TH, TT). The combination of one head and one tail is twice as likely as the combination of two heads. That’s why we care about permutations.</p><p>From our formulae above, the number of permutations of the four items for x meals (with replacement) is n^r where n=4 (the number of unique toys) and r=x (the number of meals).</p><p>The second part, “The number of permutations of the four unique items for x meals (with replacement) where we have all four toys”, is a bit trickier. We need to use the <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle">inclusion–exclusion principle</a>. Let’s consider the case for x=5, we have bought five meals.</p><pre>The answer is;<br>4^5 - (4 * (3^5)) + (6 * (2^5)) - (4 * (1^5)) = 240<br><br>Let&#39;s go through each bit to understand why.<br><br>4^5 is the number of permutations of the four items<br>for 5 meals (with replacement).<br><br>Then we want to subtract all the permutations of the <br>five toys that have no more than three unique toys. This<br>will leave only the number of permutations that have<br>exactly four unique toys. There are 3^5 permutations of<br>three unique toys, and there are nCr(4,3) = 4 ways to <br>combine four items into a set of three. So we <br>subtract (4 * (3^5)).<br><br>But we have just double counted permutations where there<br>are no more than two unique toys, as these permutations occur<br>when you sample three items with replacement. We need <br>to add those back in. There are 2^5 permutations of two<br>items, and there are nCr(4,2) = 4! / (2! * (4-2)!) = 6 <br>ways to combine four unique items into groups of two.<br>So we add back (6 * (2^5)).<br><br>But we have over counted permutations where there<br>were only one unique toy. We counted them once<br>in 4^5, then nCr(3,2) = 3 times when subtracting the<br>permutations with no more than three unique toys, <br>then counted them nCr(3,1) = 3 times when we added<br>the permutations with no more than two unique toys.<br>We need to subtract it on last time. There is 1^5<br>way to permutate an item five times, and nCr(4,1) = 4<br>ways to combine four unique items into groups of 1. <br>So we subtract (4 * (1^5)).<br><br>For x meals, we can generalise the above to;<br>4^x - (4 * (3^x)) + (6 * (2^x)) - (4 * (1^x))</pre><p>Now we can calculate the probability of having all four unique toys after x meals as;</p><pre>Y = having all four unique toys after x meals<br>P(Y) = (4^x - (4 * (3^x)) + (6 * (2^x)) - (4 * (1^x))) / 4^x</pre><pre>import numpy as np<br><br>def probability_of_having_all_four_toys_after_x_meals(x: int) -&gt; float:<br>    return np.around(<br>        (4**x - (4 * (3**x)) + (6 * (2**x)) - (4 * (1**x))) / 4**x, 6<br>    )<br><br><br>[<br>    f&quot;meal {x}, prob = {probability_of_having_all_four_toys_after_x_meals(x)}&quot;<br>    for x in range(1, 26)<br>]<br><br><br># [&#39;meal 1, prob = 0.0&#39;,<br>#  &#39;meal 2, prob = 0.0&#39;,<br>#  &#39;meal 3, prob = 0.0&#39;,<br>#  &#39;meal 4, prob = 0.09375&#39;,<br>#  &#39;meal 5, prob = 0.234375&#39;,<br>#  &#39;meal 6, prob = 0.380859&#39;,<br>#  &#39;meal 7, prob = 0.512695&#39;,<br>#  &#39;meal 8, prob = 0.622925&#39;,<br>#  &#39;meal 9, prob = 0.711365&#39;,<br>#  &#39;meal 10, prob = 0.780602&#39;,<br>#  &#39;meal 11, prob = 0.833988&#39;,<br>#  &#39;meal 12, prob = 0.874759&#39;,<br>#  &#39;meal 13, prob = 0.905703&#39;,<br>#  &#39;meal 14, prob = 0.929094&#39;,<br>#  &#39;meal 15, prob = 0.946729&#39;,<br>#  &#39;meal 16, prob = 0.960001&#39;,<br>#  &#39;meal 17, prob = 0.969978&#39;,<br>#  &#39;meal 18, prob = 0.977472&#39;,<br>#  &#39;meal 19, prob = 0.983098&#39;,<br>#  &#39;meal 20, prob = 0.987321&#39;,<br>#  &#39;meal 21, prob = 0.990489&#39;,<br>#  &#39;meal 22, prob = 0.992866&#39;,<br>#  &#39;meal 23, prob = 0.994649&#39;,<br>#  &#39;meal 24, prob = 0.995987&#39;,<br>#  &#39;meal 25, prob = 0.99699&#39;]</pre><p>For our first three meals, the probability of having all four toys is 0, as we don’t even have 4 toys yet. The probability of getting all four toys after 4 meals in 9.4%. If we commit to buying 7 meals, we have a greater than 50% chance of having all four unique toys. We would need to commit to 21 meals to have a 99% chance.</p><p>This is real life, not school, so we can’t check the back of our maths book to see if we got the correct answer. Let’s see if we can check our answer by brute forcing the solution.</p><pre>import numpy as np<br>from itertools import product<br><br><br>def brute_force_probability_of_having_all_four_toys_after_x_meals(x: int) -&gt; float:<br>    &quot;&quot;&quot;<br>    this function uses a generator, so there won&#39;t be any<br>    memory issues, but it may take a very long time for large <br>    values of x.<br>    &quot;&quot;&quot;<br>    items = [&quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;]<br>    permutations_with_replacement = product(items, repeat=x)<br><br>    sum_permutation = 0<br>    sum_has_all_four_toys = 0<br>    for permutation in permutations_with_replacement:<br>        sum_permutation += 1<br>        sum_has_all_four_toys += len(np.unique(permutation)) == 4<br><br>    return np.around(sum_has_all_four_toys / sum_permutation, 6)<br><br><br>[<br>    f&quot;meal {x}, prob = {brute_force_probability_of_having_all_four_toys_after_x_meals(x)}&quot;<br>    for x in range(1, 10)<br>]<br><br># [&#39;meal 1, prob = 0.0&#39;,<br>#  &#39;meal 2, prob = 0.0&#39;,<br>#  &#39;meal 3, prob = 0.0&#39;,<br>#  &#39;meal 4, prob = 0.09375&#39;,<br>#  &#39;meal 5, prob = 0.234375&#39;,<br>#  &#39;meal 6, prob = 0.380859&#39;,<br>#  &#39;meal 7, prob = 0.512695&#39;,<br>#  &#39;meal 8, prob = 0.622925&#39;,<br>#  &#39;meal 9, prob = 0.711365&#39;]</pre><p>It matches!</p><p><strong>What is the distribution of having all four toys after purchasing </strong><strong>x meals?</strong></p><p>In this case, we will continue to buy meals until we have all four unique toys, and stop when we have achieved this. If this were a repeated experiment, how often would we stop after four meals? seven meals? x meals?</p><p>To calculate probability of stopping after x meals, we can use the probability_of_having_all_four_toys_after_x_meals function we wrote earlier. Since that is a cumulative function, we simply take the difference of the probability of having all 4 toys after x meals minus the probability of having all toys after x-1 meals.</p><pre>import numpy as np<br><br>def probability_of_having_all_four_toys_after_x_meals(x):<br>    return np.around(<br>        (4**x - (4 * (3**x)) + (6 * (2**x)) - (4 * (1**x))) / 4**x, 6<br>    )<br><br><br>def probability_of_stopping_after_x_meals(x: int) -&gt; float:<br>    return np.around(<br>        probability_of_having_all_four_toys_after_x_meals(x)<br>        - probability_of_having_all_four_toys_after_x_meals(x - 1),<br>        6,<br>    )<br><br><br>[f&quot;meal {x}, prob = {probability_of_stopping_after_x_meals(x)}&quot; for x in range(4, 26)]<br><br># [&#39;meal 4, prob = 0.09375&#39;,<br>#  &#39;meal 5, prob = 0.140625&#39;,<br>#  &#39;meal 6, prob = 0.146484&#39;,<br>#  &#39;meal 7, prob = 0.131836&#39;,<br>#  &#39;meal 8, prob = 0.110229&#39;,<br>#  &#39;meal 9, prob = 0.08844&#39;,<br>#  &#39;meal 10, prob = 0.069237&#39;,<br>#  &#39;meal 11, prob = 0.053387&#39;,<br>#  &#39;meal 12, prob = 0.040771&#39;,<br>#  &#39;meal 13, prob = 0.030944&#39;,<br>#  &#39;meal 14, prob = 0.023391&#39;,<br>#  &#39;meal 15, prob = 0.017635&#39;,<br>#  &#39;meal 16, prob = 0.013272&#39;,<br>#  &#39;meal 17, prob = 0.009977&#39;,<br>#  &#39;meal 18, prob = 0.007494&#39;,<br>#  &#39;meal 19, prob = 0.005626&#39;,<br>#  &#39;meal 20, prob = 0.004223&#39;,<br>#  &#39;meal 21, prob = 0.003168&#39;,<br>#  &#39;meal 22, prob = 0.002377&#39;,<br>#  &#39;meal 23, prob = 0.001783&#39;,<br>#  &#39;meal 24, prob = 0.001337&#39;,<br>#  &#39;meal 25, prob = 0.001003&#39;]</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JBjsB8N0g1MSI61Whug7VQ.png" /></figure><p>Now that we’ve got these probabilities, we can use them to calculate the number of meals we would <em>expect</em> to buy before having all four unique toys, and validate the expected value we calculated earlier.</p><pre>np.sum([x*probability_of_stopping_after_x_meals(x) for x in range(4, 1000)])<br># 8.333335</pre><p>Now that’s satisfying!</p><p>Again, this is real life, not school. I don’t want to accidentally build any assumptions into a brute force approach, so let’s verify our solution with a simulation.</p><pre>import numpy as np<br>import collections<br><br><br>def purchase_meals_until_we_have_all_four_toys() -&gt; int:<br>    &quot;&quot;&quot;returns the number of meals bought before obtaining<br>    all four unique toys<br>    &quot;&quot;&quot;<br>    p = []<br>    meals = 0<br>    while True:<br>        meals += 1<br>        p.append(np.random.choice(a=[&quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;], size=1)[0])<br>        if len(np.unique(p)) == 4:<br>            break<br>    return meals<br><br><br>def repeat_experiment_k_times(k: int) -&gt; list[int]:<br>    &quot;&quot;&quot;returns a list of length k, with<br>    the results from purchase_meals_until_we_have_all_four_toys<br>    run k times<br>    &quot;&quot;&quot;<br>    return [purchase_meals_until_we_have_all_four_toys() for _ in range(k)]<br><br><br>experiment_results = repeat_experiment_k_times(k=1_000_000)<br><br>freq = collections.Counter(experiment_results)<br>total = sum(freq.values())<br><br>for key, value in sorted(freq.items()):<br>    percentage = round(value / total, 9)<br>    print(f&quot;meal {key}, prob = {percentage}&quot;)<br><br><br># meal 4, prob = 0.093689<br># meal 5, prob = 0.140501<br># meal 6, prob = 0.1467925<br># meal 7, prob = 0.13173<br># meal 8, prob = 0.110042<br># meal 9, prob = 0.0885735<br># meal 10, prob = 0.069224<br># meal 11, prob = 0.0533185<br># meal 12, prob = 0.040913<br># meal 13, prob = 0.0309445<br># meal 14, prob = 0.023476<br># meal 15, prob = 0.017594<br># meal 16, prob = 0.013228<br># meal 17, prob = 0.010011<br># meal 18, prob = 0.007517<br># meal 19, prob = 0.0055785<br># meal 20, prob = 0.0041545<br># meal 21, prob = 0.0031305<br># meal 22, prob = 0.00243<br># meal 23, prob = 0.001767<br># meal 24, prob = 0.001334<br># meal 25, prob = 0.000992<br># meal 26, prob = 0.0007625<br># meal 27, prob = 0.0005565<br># meal 28, prob = 0.0004215<br># meal 29, prob = 0.000328<br># meal 30, prob = 0.0002515<br># meal 31, prob = 0.000179<br># meal 32, prob = 0.00014<br># meal 33, prob = 0.000106<br># meal 34, prob = 7.6e-05<br># meal 35, prob = 6.25e-05<br># meal 36, prob = 3.7e-05<br># meal 37, prob = 3.85e-05<br># meal 38, prob = 2.2e-05<br># meal 39, prob = 2e-05<br># meal 40, prob = 1.45e-05<br># meal 41, prob = 1.15e-05<br># meal 42, prob = 8.5e-06<br># meal 43, prob = 4.5e-06<br># meal 44, prob = 4e-06<br># meal 45, prob = 3.5e-06<br># meal 46, prob = 1.5e-06<br># meal 47, prob = 3e-06<br># meal 48, prob = 3.5e-06<br># meal 49, prob = 2e-06<br># meal 50, prob = 5e-07<br># meal 51, prob = 5e-07<br># meal 52, prob = 1e-06</pre><p>It matches (as much as a simulation with randomness would be expected to match)!</p><p><strong>A final thought</strong></p><p>I asked my brother how many meals would he would expect to buy before having all four toys. He said four meals, if you ask nicely for a different toy each time.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b8653c2c46c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How I use ChatGPT to write Python functions]]></title>
            <link>https://medium.com/@benjamin22-314/how-i-use-chatgpt-write-python-functions-92817bcffe0e?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/92817bcffe0e</guid>
            <category><![CDATA[python-programming]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[unit-testing]]></category>
            <category><![CDATA[chatgpt]]></category>
            <category><![CDATA[regex-in-python]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Fri, 06 Jan 2023 11:43:45 GMT</pubDate>
            <atom:updated>2023-01-07T03:27:52.257Z</atom:updated>
            <content:encoded><![CDATA[<p>In this post I will share my process on how I use ChatGPT to help me program. We will see where it does well, and where it does not so well.</p><p><strong>TLDR:</strong></p><ul><li><strong>Give ChatGPT lots of context and clear instructions.</strong></li><li><strong>Create just one function at a time.</strong></li><li><strong>Ask ChatGPT to write unit tests, and then fix the unit tests.</strong></li><li><strong>Use the tests to find where the function fails.</strong></li><li><strong>Ask ChatGPT to fix the function, and if it can’t, ask ChatGPT to try solve the problem in a different way.</strong></li><li><strong>Ask ChatGPT to create a Docstring and descriptive variable names if necessary.</strong></li></ul><p>Let’s say I want a function that removes white space from the beginning and end of a string, removes duplicated white space, and makes sure the first word of each sentence is capitalised.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/797/1*EPqj3cz7eHO12i1aBsm_rg.png" /></figure><p>This result is actually incorrect (in at least two ways). The first mistake is that string.capitalize() will make sure the first letter of the string in capitalised, and every other letter will be changed to lowercase. This isn’t what I want. If a letter is already uppercase, I want it to remain so. If there is more than one sentence in the string, I want the first word of each sentence to be a capital. The second mistake is the example and output. The actual output would be Hello, world! how are you today? .</p><p>I could tell ChatGPT about the mistake and ask for it to be fixed, but instead I’m going to change tact. I’d prefer a function that used Regex. I will open a new chat and start again.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/793/1*JSAMu5QyQn53eqq1n0RBbg.png" /></figure><p>This is looking a lot better. Regex can be difficult to understand, so I appreciate that ChatGPT explains it. I think this function will still fail to capitalise the first word of sentences that start after a ‘?’ or a ‘!’. Perhaps it will fail in some ways I can’t tell by looking. I’ll ask ChatGPT.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/798/1*IhPldR8wDbJPSwz6xGx7Ug.png" /></figure><p>ChatGPT answer yes, but it is wrong. Not only is it wrong about that, but after running the function, I now know that it fails to capitalise anything at all.</p><p>This tells me that what I was asking for may have been too ambitious. I’ll try again, adding a lot more context, in a new chat.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/804/1*9kAlWqEjE-CkG55p4nu6eg.png" /></figure><p>This code is also wrong. It does not capitalise words at the beginning of each sentence. I suspect it’s the lambda function that is giving us trouble here. In a new chat, I will ask it to avoid using the lambda function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/815/1*rSCH5tsq6BMk9QUZS8v_4w.png" /></figure><p>This function is the best result so far, but it is also wrong. It does not capitalise the first word in the string. It is tempting to forgive ChatGPT this mistake, as the instructions could be considered ambiguous, but the output from the example is unambiguously wrong. Let’s leave it for now.</p><p>No matter what your coding experience, it’s always good practice to write unit tests. ChatGPT is great at this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/793/1*PYv_glQJuH6mUBvCd56chQ.png" /></figure><p>Well…. ChatGPT is okay at this. It didn’t create a function for each unit test, and the input and expected result for the first two tests aren’t consistent. The first test expects the first letter to remain lower case, and the second test expects it to make first letter upper case.</p><p>It’s not perfect, but it’s a good start for us to build off. Let’s see if we can improve readability.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/801/1*r4im9opoV9QyOz8kD4_LzA.png" /></figure><p>The next step would be to fix the unit tests, add my own, and find where this function fails. When I find an error, I will ask ChatGPT to fix it (or just fix it myself).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/821/1*NBytdw6-f8aftxvLOfG1iQ.png" /></figure><p>This fixes the issue when the first element in the string is a letter, but will fail when there is white space before the beginning of the first word. Lucky we wrote unit tests to catch those issues. I could ask ChatGPT to fix this, but I can see it can be fixed by moving the s = re.sub(r&#39;\s+&#39;, &#39; &#39;).strip() line to the top of the function.</p><p>Lastly, I want to tidy up the function. Comments should answer “why”, not “how”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/1*wbJ6-XxGtToMoZSgGOrsBw.png" /></figure><p>The Docstring is pretty good. I reiterated to ChatGPT that I wanted the comments removed, and it still didn’t remove them. I’ll have to remove the comments myself.</p><p>If I’m feeling a bit whimsical, I might ask ChatGPT to be creative with the Docstring.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/810/1*k2VdKSdx2GIZOysszaFv1A.png" /></figure><p>In this case, it’s a little too wordy, so I’ll go with the original.</p><p>When I started this post, I didn’t expect ChatGPT would have so much trouble with this task. It did make it easy for me to demonstrate “where ChatGPT doesn’t do well” though.</p><p>To expand on my <strong>TLDR</strong> from the top of the article;</p><ul><li><strong>Craft your prompt for ChatGPT with clear instructions. You can even include examples.</strong></li><li><strong>Create one self contained function (it’s easier to test).</strong></li><li><strong>ChatGPT can help write the unit tests, but <em>you</em> need to make sure you have sufficient and correct tests.</strong></li><li><strong>Use the unit tests to find where the function fails. Ask ChatGPT to fix the function, and if it can’t, find the bug and ask ChatGPT to solve the problem a different way.</strong></li><li><strong>ChatGPT can write Docstrings and rename variables to be more descriptive. You can even ask it to suggest a better function name.</strong></li></ul><p><strong>P.S.</strong> You might wonder if I used ChatGPT to help me write the non-code part of this blog post. I did ask it to proofread and improve the first paragraph, but I found the rewrite to be unnecessarily wordy, and not in my writing style. In the end, I didn’t use it.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=92817bcffe0e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Multi-Label Text Classification with StarSpace in R]]></title>
            <link>https://medium.com/analytics-vidhya/multi-label-text-classification-with-starspace-in-r-c9d72d7b7146?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/c9d72d7b7146</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[starspace]]></category>
            <category><![CDATA[text-analytics]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[nlp]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Thu, 20 Feb 2020 06:45:47 GMT</pubDate>
            <atom:updated>2021-12-02T00:01:13.784Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*mTxrxh9M2IQDLkkZ" /><figcaption>Photo by <a href="https://unsplash.com/@doingenia?utm_source=medium&amp;utm_medium=referral">Denis Degioanni</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>In this post, we will predict movie genres based on the text describing the plot of the movie.</p><p>The <a href="http://www.cs.cmu.edu/~ark/personas/">data</a> is from Wikipedia pages for each movie. The R package we use is the <a href="https://cran.r-project.org/web/packages/ruimtehol/index.html">ruimtehol</a> package which was created using methods developed by the Facebook AI Research team (<a href="https://research.fb.com/downloads/starspace/">StarSpace</a>, <a href="https://emnlp2014.org/papers/pdf/EMNLP2014194.pdf">TagSpace</a>). You can find my code for this project <a href="https://github.com/BenjaminPhillips22/movie_genres">here</a>.</p><p>When and why use TagSpace? In this case, we have text data (film plots) and an abundance of labels (genres) that have not exactly been applied consistently.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/892/1*zQ8SSlNgDv1sDDNxhxVWbg.png" /><figcaption>A look at TagSpace ‘under the hood’</figcaption></figure><p>TagSpace was designed to use the free text from Facebook posts to predict the hashtags associated with those posts. We can extend their Use Case to ours. We have text in the plot descriptions and the genres are a lot like hashtags.</p><p>StarSpace is similar to TagSpace, but is more generalised. Whereas TagSpace allows us to create document embeddings from word embeddings, StarSpace allows us to create embeddings for anything. For example, a website might have an embedding generated from the text on the website and a user might have an embedding generated from the websites they visit.</p><p><strong>Let’s get started!</strong></p><p>You can download the data manually or use the following code.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/040db7ec4e6dbf1e47adcdbcd69d8015/href">https://medium.com/media/040db7ec4e6dbf1e47adcdbcd69d8015/href</a></iframe><p>Load the necessary libraries. The ruimtehol package provides the framework for us to use the StarSpace algorithms in R. It was created by <a href="https://github.com/bnosac/ruimtehol">Jan Wijffels</a> who writes that ruimtehol is the translation of ‘star space’ into West Flemish.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b3a1708082eefb054c0f8385bb5a4965/href">https://medium.com/media/b3a1708082eefb054c0f8385bb5a4965/href</a></iframe><p>There are a number of preprocessing steps before we can get to modelling. We need to join the plot description data to the genre data and clean them both up. Here is the text cleaning function used. For more details on cleaning and joining the data, or other part of the project, see my github repo <a href="https://github.com/BenjaminPhillips22/movie_genres">here</a>.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e3c5e6b2b35b3511ce42a4240759142b/href">https://medium.com/media/e3c5e6b2b35b3511ce42a4240759142b/href</a></iframe><p>The film “Back to the Future” has labelled genres; science_fiction, adventure, comedy, family_film. The first line of the plot is “Seventeen-year-old Marty McFly lives with his bleak, unambitious family in Hill Valley, California.”. After processing, it will look like this; “seventeen marti mcfly live bleak unambiti famili hill vallei california”</p><p>A little bit of exploratory analysis never hurt, and often helps.</p><p><strong>Genres</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0011388bec9e05913f2790932ba5f694/href">https://medium.com/media/0011388bec9e05913f2790932ba5f694/href</a></iframe><p>We can see the most popular genre labels are drama, comedy and romantic_film. Amongst the least popular can be seen a misspelling of comedy and romantic_thriller. If you’re wondering, the one film in the genre romantic_thriller is a Bollywood film called “Bloody Isshq”. Because some of the genres appear so few times, in this experiment we will only be predicting the top 50 genres.</p><p>The labels aren’t perfect. Consider genres related to romance.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/da29acc6c113d7ff41b9c40af2fa95ff/href">https://medium.com/media/da29acc6c113d7ff41b9c40af2fa95ff/href</a></iframe><p>The film “The Princess Bride” has the labels; comedy_of_manners, comedydrama, drama, comedy, romance_film, family_film and teen. It is labelled romance_film and drama but not romantic_drama. The TagSpace algorithm is especially good at dealing with this sort of fuzzy classification problem.</p><p>Words in Plot Description (after removing stop words)</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fb89b5ecc4ca4544eb04d59fbeee5f31/href">https://medium.com/media/fb89b5ecc4ca4544eb04d59fbeee5f31/href</a></iframe><p>“kill” appears to be the most common word in movie plot descriptions. Infer what you will about Human Nature and/or Movie Culture.</p><p>There are many words that only appear a few times in the entire dataset. We will need to take this into consideration when training the model.</p><p><strong>Modelling</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d31ab644eb2a682bd4a6edfa056f8d19/href">https://medium.com/media/d31ab644eb2a682bd4a6edfa056f8d19/href</a></iframe><p>As we want to do classify text, we will use the embed_tagspace function. Let’s go through the parameters.</p><ul><li>x is the cleaned text that the model will use as features. It should be a vector where each element is a string.</li><li>y is the labels that the model will try and predict. It should be a list where every element in the list is a vector with the genres.</li><li>dim is the dimension size of the document embedding generated for the text. Each plot description will be represented as a vector of length 20.</li><li>Epoch is the maximum number of epochs to train the model for. Internally, the embed_tagspace function creates a training and development set. When performance on the development set doesn’t improve after 10 epochs, the training is stopped. Our model usually ran in around 15 epochs.</li><li>lr is the learning rate for the neural network.</li><li>loss is the loss function. Another option instead of softmax is ‘hinge’.</li><li>negSearchLimit is the number of negatives labels sampled.</li><li>ws is the window size that the model looks at the text over.</li><li>minCount is the minimum number of times a word needs to occur in the entire corpus for the model to create an embedding for it and use it as part of the prediction process. Words that occur less than this amount are invisible to the model.</li></ul><p><strong>Evaluating the model.</strong></p><p>The output of the model is a similarity score between the embedding for the text, and each of the genre labels. The similarity score is between -1 and 1, where a higher score means more similarity. There are many ways to measure the accuracy of the model. In this case we will take the model output, filter to only have the genres that that movie was originally labelled with, and average of the similarity scores. This way we aren’t penalising for the not so perfect labelling. Another option would be to look at <a href="https://en.wikipedia.org/wiki/Precision_and_recall">precision and recall</a>.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1bf9d450dfd993462911805dd93765b0/href">https://medium.com/media/1bf9d450dfd993462911805dd93765b0/href</a></iframe><p>No over fitting for us.</p><p>Let’s have a look at where our model does well and not so well. The clean_genres column are the true genres, the top_5_genres are the top 5 predicted genres for that plot.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cb9e03e86d8b75b8e86164217639a04c/href">https://medium.com/media/cb9e03e86d8b75b8e86164217639a04c/href</a></iframe><p><strong>Next Steps.</strong></p><p>To improve accuracy it might be worth trying different hyper-parameters for the model. We could consider increasing the embeddings size or decreasing the minCount. Trying hinge loss instead of softmax for the loss function, increasing the window size (ws) or trying different values for negSearchLimit.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c9d72d7b7146" width="1" height="1" alt=""><hr><p><a href="https://medium.com/analytics-vidhya/multi-label-text-classification-with-starspace-in-r-c9d72d7b7146">Multi-Label Text Classification with StarSpace in R</a> was originally published in <a href="https://medium.com/analytics-vidhya">Analytics Vidhya</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Simple Regression with Neural Networks in PyTorch]]></title>
            <link>https://medium.com/@benjamin22-314/simple-regression-with-neural-networks-in-pytorch-313f06910379?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/313f06910379</guid>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[regression]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Sat, 15 Dec 2018 04:17:51 GMT</pubDate>
            <atom:updated>2018-12-15T04:28:58.036Z</atom:updated>
            <content:encoded><![CDATA[<h3>Regression with Neural Networks in PyTorch</h3><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2Fvy0d5t83Pd5HpRAuPe%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2Fvy0d5t83Pd5HpRAuPe%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2Fvy0d5t83Pd5HpRAuPe%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="271" frameborder="0" scrolling="no"><a href="https://medium.com/media/4bbef2e44abf0e3160e2f1dce81c20d6/href">https://medium.com/media/4bbef2e44abf0e3160e2f1dce81c20d6/href</a></iframe><p>Neural networks are sometimes described as a ‘universal function approximator’. Here I show a few examples of simple and slightly more complex networks learning to approximate their target distributions.</p><p>The first distribution of data points we will look at is a simple quadratic function with some random noise.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*dDL9XWeWVXuA_eK2daNOaQ.png" /></figure><p>We’ll use a simple network (model 1) with one hidden layer with 10 nodes.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/99ece3bfa7bbe56e0cbc6faad8b56ef7/href">https://medium.com/media/99ece3bfa7bbe56e0cbc6faad8b56ef7/href</a></iframe><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FbSlVV81DZWc2Yf1MHh%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2FbSlVV81DZWc2Yf1MHh%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2FbSlVV81DZWc2Yf1MHh%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="271" frameborder="0" scrolling="no"><a href="https://medium.com/media/a82b63ee7144b3eac34713c7457eba34/href">https://medium.com/media/a82b63ee7144b3eac34713c7457eba34/href</a></iframe><p>Because the network has only one hidden layer, it’s limited in it’s ability to fit the data. Even still though, you can see the loss function decreasing with each step.</p><p>Next, let’s try the same network (model 1) on some more complex data. This time a sine way with random noise. After experimenting with different optimisers, I found the using the Adam algorithm for gradient descent with a smaller learning rate worked best.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FcJuKX2sx8MojaI5tto%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2FcJuKX2sx8MojaI5tto%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2FcJuKX2sx8MojaI5tto%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="271" frameborder="0" scrolling="no"><a href="https://medium.com/media/e7b4ad09782005dbe1adca8a66dd1b99/href">https://medium.com/media/e7b4ad09782005dbe1adca8a66dd1b99/href</a></iframe><p>After about 500 steps, it gets stuck and can not iteratively move towards a better solution.</p><p>Let’s try the same data distribution, but with a more complex model (model 2). This one still has only one hidden layer, but it now has 200 nodes and is followed by a LeakyReLu function. The neural network in this code is defined in a different way, using torch.nn.Sequential.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FpjqRiw2hk1xAXyBrs6%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2FpjqRiw2hk1xAXyBrs6%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2FpjqRiw2hk1xAXyBrs6%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="271" frameborder="0" scrolling="no"><a href="https://medium.com/media/5be6dcdb86f7e590f0acee35f5413df1/href">https://medium.com/media/5be6dcdb86f7e590f0acee35f5413df1/href</a></iframe><p>With the same learning rate and the same number of steps, this larger network can fit the target distribution. You can even notice that it starts to curve near the local min and max.</p><p>Let’s try a more complex model still. This time a neural network with two hidden layer, with 200 and 100 nodes respectively, each followed by a LeakyReLu (model 3).</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FmYdJhphX9zHkO0Os3a%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2FmYdJhphX9zHkO0Os3a%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2FmYdJhphX9zHkO0Os3a%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="271" frameborder="0" scrolling="no"><a href="https://medium.com/media/9b865c91f2ad96ddf2c8f495eb3fab7c/href">https://medium.com/media/9b865c91f2ad96ddf2c8f495eb3fab7c/href</a></iframe><p>With this extra complexity, the neural network model and fit the data distribution within 500 steps.</p><p>OK, so in the previous cases we’ve been using all the data the fit the model. Often we want to train a network using batches. Let’s give it a go with model 3.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b6eb59d10bc74c1f7b21ab151d2624ae/href">https://medium.com/media/b6eb59d10bc74c1f7b21ab151d2624ae/href</a></iframe><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2FcsRqcmlTasGhyHPm8c%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2FcsRqcmlTasGhyHPm8c%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2FcsRqcmlTasGhyHPm8c%2Fgiphy.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="271" frameborder="0" scrolling="no"><a href="https://medium.com/media/618175b2dc203a77f0bad77d4e5400b1/href">https://medium.com/media/618175b2dc203a77f0bad77d4e5400b1/href</a></iframe><p>So how does it perform on the data as a whole?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eZJVQ377mcue-PFONLlpBw.png" /><figcaption>Output from the above code.</figcaption></figure><p>Pretty well actually.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=313f06910379" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[“Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural…]]></title>
            <link>https://medium.com/data-science/deep-neuroevolution-genetic-algorithms-are-a-competitive-alternative-for-training-deep-neural-822bfe3291f5?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/822bfe3291f5</guid>
            <category><![CDATA[neuroevolution]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Fri, 16 Nov 2018 09:33:47 GMT</pubDate>
            <atom:updated>2021-05-06T13:54:37.709Z</atom:updated>
            <content:encoded><![CDATA[<h3>Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning — Paper Summary</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*gd8cjCn2IUFa7iaw" /><figcaption>Photo by <a href="https://unsplash.com/@veeterzy?utm_source=medium&amp;utm_medium=referral">veeterzy</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>In December 2017, Uber AI Labs released <a href="https://eng.uber.com/deep-neuroevolution/">five papers</a>, related to the topic of <a href="https://www.oreilly.com/ideas/neuroevolution-a-different-kind-of-deep-learning">neuroevolution</a>, a practice where deep neural networks are optimised by evolutionary algorithms.</p><p>This post is a summary of one those papers called “<a href="http://arxiv.org/abs/1712.06567">Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning</a>”. It is intended for those with some basic familiarity in topics related to machine learning. Concepts such as ‘genetic algorithms’ and ‘gradient descent’ are prerequisite knowledge.</p><p>Much of the research in the five Uber AI Labs papers, including the paper I am summarising, builds on research by OpenAI presented in the paper “<a href="https://arxiv.org/abs/1703.03864">Evolution Strategies as a Scalable Alternative to Reinforcement Learning</a>”. OpenAI have written a <a href="https://blog.openai.com/evolution-strategies/">blog post</a> summarising their paper. A shorter summary (written by me) can be found <a href="https://medium.com/@benjamin.phillips22/evolution-strategies-as-a-scalable-alternative-to-reinforcement-learning-paper-summary-691161b52ddd">here</a>.</p><p>The code used for the experiments in this paper can be found <a href="https://github.com/uber-research/deep-neuroevolution">here</a>. In April 2018, the code was optimised to run on a single personal computer. The work to achieve this is described in an Uber AI labs <a href="https://eng.uber.com/accelerated-neuroevolution/">blog post</a>, and the specific code can be found <a href="https://github.com/uber-research/deep-neuroevolution/tree/master/gpu_implementation">here</a>.</p><h4>What were the results?</h4><p>Deep Neural Networks (DNN) are typically optimised using gradient based methods such a back-propagation. This paper shows that using a simple Genetic Algorithm (GA) it is possible to optimise DNNs and that GAs are a competitive alternative to gradient based methods when applied to Reinforcement Learning (RL) tasks such as learning to play Atari games, simulated humanoid locomotion or deceptive maze problems.</p><p>The scalability of the GA was demonstrated by evolving a DNN with over four million parameters, the largest network ever evolved with an evolutionary algorithm. The ability to parallelise means that the computation for GAs can be distributed across many CPUs, creating the potential to train DNNs much more quickly compared to gradient based methods. Additionally, by ingeniously representing the DNN parameters as a series of random seeds, a network with over 4 million parameters can be encoded in just a few thousand bytes (a factor of 10,000-fold smaller).</p><p><a href="https://link.springer.com/chapter/10.1007/978-1-4614-1770-5_3">Novelty Search </a>(NS), a technique used with GAs to encourage exploration in tasks with deceptive or sparse rewards, was shown in one problem domain (called ‘Image Hard Maze’) to outperform other gradient and evolutionary based algorithms that optimise solely for reward.</p><p>Amazingly, Random Search (RS) was found to be competitive (although never as competitive as GAs) in learning to play some Atari games. This suggests that in some domains, sampling around the origin is enough to find an adequate solution.</p><p>These results indicate that GAs (and RS) are not all out better or worse than other methods of optimising DNN, but that they are a ‘competitive alternative’ that one can add to their RL tool belt.</p><p>Like OpenAI, they state that although DNNs don’t struggle with local optima in supervised learning, they can still get into trouble in RL tasks due to a deceptive or sparse reward signal. It is for this reason that non gradient based methods such as GAs can perform well compared to other popular algorithms in RL.</p><h4>About the GA</h4><p>For an introduction to GAs, I recommend Vijini Mallawaarachchi’s <a href="https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3">blog post</a>.</p><p>Popular algorithms in RL such as <a href="https://en.wikipedia.org/wiki/Q-learning">Q-learning</a> and <a href="http://www.scholarpedia.org/article/Policy_gradient_methods">policy gradients</a> use gradient descent. ES also follows the gradient via an operation similar to <a href="https://en.wikipedia.org/wiki/Finite_difference">finite differences</a>. Unlike these methods, GAs do not follow the gradient, instead the use exploration through mutation and exploitation through selection to evolve the individuals of a population.</p><p>This work uses a very simple GA, with the purpose being to establish a baseline for EAs. It’s so simple that it doesn’t even use cross-over, a technique so common in GAs that at first it felt strange to even call this algorithm a GA.</p><p>After initialising the population, the top T individuals (in this case neural network parameter vectors) are selected to be potential parents. These individuals are then selected from uniformly at random (with replacement) and are mutated by adding Gaussian noise with a standard deviation determined empirically for each experiment. The highest scoring individual of each generation is also added to the next generation (elitism of one).</p><p><strong>State-of-the-art Encoding</strong></p><blockquote>We propose a novel method to store large parameter vectors compactly by representing each parameter vector as an initialization seed plus the list of random seeds that produce the series of mutations applied to theta. This innovation was essential to enabling GAs to work at the scale of deep neural networks, and we thus call it a Deep GA. This technique also has the benefit of offering a state-of-the-art compression method.</blockquote><p>Without crossover, the list of seeds that define an individual is equal to the number of generations. It has the benefit of reduced memory and network transmission costs. With crossover, a new more complex method would be needed to encode the individuals. This method of encoding is pretty cool. Representing millions of neural network parameters with a comparatively tiny number of seeds.</p><h4>Novelty Search</h4><blockquote>[novelty search] was designed for deceptive domains in which reward-based optimization mechanisms converge to local optima. NS avoids these local optima by ignoring the reward function during evolution and instead rewarding agents for performing behaviors that have never been performed before (i.e. that are novel).</blockquote><p>NS requires a function that can quantify the difference between behavior of any two individuals. After each generation, individuals have a small probability of being added to an archive. The ‘novel’-ness of new individuals are determined by comparing them to others in the same generation as well as those stored in the archive.</p><h4>Experiments</h4><p>The experiments focus on the performance of the GA in the following tasks; Learning to play Atari games from pixels, continuous control of a simulated humanoid learning to walk (MuJoCo) and a problem with known deceptive local optima called the ‘Image Hard Maze’.</p><p><strong>Atari</strong></p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F92edltiUbUQ%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D92edltiUbUQ&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F92edltiUbUQ%2Fhqdefault.jpg&amp;key=d04bfffea46d4aeda930ec88cc64b87c&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/d98fd5090af7da3bddcc6ce60a4147b9/href">https://medium.com/media/d98fd5090af7da3bddcc6ce60a4147b9/href</a></iframe><p>13 Atari games were selected. Five were selected because ES performed well on them. Four others were selected because ES performed poorly. Lastly, four that where selected alphabetically from the collection of available games.</p><p>The GAs performance on Atari games is compared to the performance of other reinforcement learning algorithms such as <a href="https://arxiv.org/abs/1710.02298">DQN</a> (Q-learning), ES and <a href="https://www.nature.com/articles/nature14236">A3C</a> (policy gradients). The results for ES and A3C were both from OpenAI’s <a href="https://arxiv.org/abs/1703.03864">paper</a>. To facilitate comparisons, the data preprocessing and network architecture are the same as that presented in a 2015 <a href="https://www.nature.com/articles/nature14236">paper</a> on DQNs. Many improvements have been made to DQNs since 2015, but the authors argue that it makes sense to compare results to a vanilla DQN as this work uses only a vanilla GA. To also allow comparisons with OpenAI’s recent work on ES, the number of game frames agents experience over the course of a GA run is kept constant (at one billion frames) as it was in the ES experiments. This means that agents will see a varying number of frames (depending on how successful they are), and that the number of generations in a GA run is not fixed.</p><blockquote>[This research uses] the larger DQN architecture from <a href="https://www.nature.com/articles/nature14236">Mnih et al. (2015)</a> consisting of 3 convolutional layers with 32, 64, and 64 channels followed by a hidden layer with 512 units. The convolutional layers use 8 x 8, 4 x 4, and 3 x 3 filters with strides of 4, 2, and 1, respectively. All hidden layers were followed by a rectifier nonlinearity (ReLU). The network contains over 4M parameters.</blockquote><p>There is some difficulty in comparing the results of the GA to other algorithms. Unlike the GA, ES and DQN which were all trained from a random start, the A3C was trained using a database of human starts to sample from. Additionally, the results for the DQN were obtained using approximately 200 million frames (due to excessive computation time), compared to the 1 billion frames used for ES, RS and the GA.</p><p>Overall the GA was able to perform roughly as well as the other algorithms (see Table 1 below). DQN, ES and the GA each produced the best score on three games, while A3C produced the best score on four games.</p><p>For some games, GA sometimes outperforms DQN and ES within one or tens of generations. Those solutions found in the first generation are essentially random DNNs because there hasn’t even been one round of selection. So was the GA just doing random search? Here RS is a special case of GA, with the number of generations being equal to one. Looking at the results, GA always outperforms RS. But gosh, RS can beat DQN, A3C and ES on some domains.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FCGHgENV1hII%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DCGHgENV1hII&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FCGHgENV1hII%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/e6c2ef315c601fe951d298d9d00a88e6/href">https://medium.com/media/e6c2ef315c601fe951d298d9d00a88e6/href</a></iframe><blockquote>[T]he success of RS versus DQN, A3C, and ES suggest that many Atari games that seem hard based on the low performance of leading deep RL algorithms may not be as hard as we think, and instead that these algorithms for some reason are performing extremely poorly on tasks that are actually quite easy.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/752/1*SvM8ixyWECqyeBA02oQ8ew.png" /><figcaption>Table 1. The Atari results reveal a simple genetic algorithm is competitive with Q-learning (DQN), policy gradients (A3C), and evolution strategies (ES). Shown are game scores (higher is better). Comparing performance between algorithms is inherently challenging (see main text), but we attempt to facilitate comparisons by showing estimates for the amount of computation (operations, the sum of forward and backward neural network passes), data efficiency (the number of game frames from training episodes), and how long in wall-clock time the algorithm takes to run. The GA, DQN, and ES, perform best on 3 games each, while A3C wins on 4 games. Surprisingly, random search often finds policies superior to those of DQN, A3C, and ES (see text for discussion). Note the dramatic differences in the speeds of the algorithm, which are much faster for the GA and ES, and data efficiency, which favors DQN. The scores for DQN are from <a href="https://arxiv.org/abs/1710.02298">Hessel et al. (2017)</a> while those for A3C and ES are from <a href="https://arxiv.org/abs/1703.03864">Salimans et al. (2017)</a>.</figcaption></figure><p><strong>Humanoid Locomotion</strong></p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgiphy.com%2Fembed%2F23dPu0oyR7kIn4SYNc%2Ftwitter%2Fiframe&amp;url=https%3A%2F%2Fmedia.giphy.com%2Fmedia%2F23dPu0oyR7kIn4SYNc%2Fgiphy.gif&amp;image=https%3A%2F%2Fi.giphy.com%2Fmedia%2F23dPu0oyR7kIn4SYNc%2Fgiphy-downsized-large.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=giphy" width="435" height="435" frameborder="0" scrolling="no"><a href="https://medium.com/media/7b34faf7a2b1a1a3b41ccaad947e7a5b/href">https://medium.com/media/7b34faf7a2b1a1a3b41ccaad947e7a5b/href</a></iframe><p>The GA is next tested on a continuous control problem, where a simulated humanoid learns to walk. The software used was <a href="https://gym.openai.com/envs/Humanoid-v2/">MuJoCo</a> (Humanoid-v1 environment in OpendAI Gym).</p><blockquote>This problem involves mapping a vector of 376 scalars that describe the state of the humanoid (e.g. its position, velocity, angle) to 17 joint torques. The robot receives a scalar reward that is a combination of four components each timestep. It gets positive reward for standing and its velocity in the positive x direction, and negative reward the more energy it expends and for how hard it impacts the ground. These four terms are summed over every timestep in an episode to calculate the total reward.</blockquote><p>The GA requires a lot more computation compared to ES to achieve similar results which is surprising given how well GA performed on the Atari games.</p><p><strong>Image Hard Maze</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/394/1*J2B9hYNvU7SgBtTsHKwF2Q.png" /><figcaption>The Image Hard Maze domain</figcaption></figure><p>Image Hard Maze is a problem that contains local optima (traps) that deceive agents that greedily get closer to the goal.</p><p>Novelty Search doesn’t have this problem because it ignores the reward and encourages the agent to visit new places. As mentioned earlier, NS needs a behavioral difference function to determine ‘novel’-ness. For this problem, that function is the squared Euclidean distance between the final positions.</p><p>The neural network sees a birds eye view of the maze, which is 84 by 84 pixel image, and has over 4 million parameters. It controls the navigation of the robot in the maze through a speed and rotation output. The three previous frames are also part of the input to provide temporal information.</p><p>Performing novelty search allows the GA to solve this task while the GA and ES that optimise only for reward (smallest distance to the goal) get stuck in local optima. DQN and A2C (the source code for A3C was unavailable) were also unable to sufficiently explore enough to compete with the GA-NS.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yJvQ0ynahLLgi5y8Kb6MKQ.png" /><figcaption>How different algorithms explore the deceptive Image Hard Maze over time. Traditional reward-maximization algorithms do not exhibit sufficient exploration to avoid the local optimum (going up). In contrast, a GA optimizing for novelty only (GA-NS) explores the entire environment and ultimately finds the goal. All 3 evolutionary algorithms had the same number of evaluations. For DQN and A2C, we plot the end-of-episode position of the agent for each of the 20K episodes prior to the checkpoint listed above the plot.</figcaption></figure><h4>Conclusion</h4><p>The experiments demonstrate that GAs are a competitive alternative in RL to other well known algorithms such as DQN, A3C and ES, sometimes performing better and sometimes worse. This work only uses a simple GA and new results may be discovered by combining GAs with other techniques known to be effective in the neuroevolution community, or by combining GAs with other RL algorithms.</p><p>While these results seem promising, it is possible to take a slightly more pessimistic view. In march 2018, Ben Recht co-authored a paper called <a href="https://arxiv.org/abs/1803.07055">Simple random search provides a competitive approach to reinforcement learning</a> where his team achieved state-of-the art on the MuJoCo walking task with RS. His <a href="http://www.argmin.net/2018/03/20/mujocoloco/">conclusions</a> are similar to those presented in this paper regarding these results, that the success of RS in these domains indicates that these problems are not as difficult as previously thought.</p><p>Nevertheless, the work in the paper does demonstrate that a simple GA can outperform RS and that there are likely further gains to be made by continuing to research in this direction. It also shows that there is a trade off regarding sample efficiency and compute time among the current popular algorithms. This is something that can be taken into account given your use case. If the cost of a sample is high, a gradient based method might be better. If time is the limiting factor, a GA will get you a solution more quickly. Perhaps in the future we will be able to specify a “speed to sample efficiency” trade off and find a solution using both EAs and gradient based methods.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=822bfe3291f5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/deep-neuroevolution-genetic-algorithms-are-a-competitive-alternative-for-training-deep-neural-822bfe3291f5">“Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural…</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Evolving Simple Organisms]]></title>
            <link>https://medium.com/@benjamin22-314/evolving-simple-organisms-5b7599c4c2e9?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/5b7599c4c2e9</guid>
            <category><![CDATA[artificial-life]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[neural-networks]]></category>
            <category><![CDATA[reinforcement-learning]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Wed, 11 Jul 2018 01:29:19 GMT</pubDate>
            <atom:updated>2018-07-17T03:35:16.319Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eSqkgdaUbIZ5AXT1ZL_ytg.gif" /><figcaption>Fish competing for food, one thousand generations into the experiment.</figcaption></figure><p>Here I present the results of a small project I have been working on recently. I use a genetic algorithm to evolve organisms (I call them fish) that try to eat food. <a href="https://github.com/nathanrooy/evolving-simple-organisms">Nathan Rooy</a> wrote the original ‘evolving simple organisms’ code which I forked and then edited for my own purposes. My code can be found <a href="https://github.com/BenjaminPhillips22/evolving-simple-organisms">here</a>.</p><h4>The Organisms</h4><p>The fish have small brains represented by neural networks. Each fish brain has six inputs, x and y displacement to nearest food, x and y displacement to the nearest fish neighbor and current x and y velocity. They have two outputs, new x and y velocity. They have only one hidden layer with five nodes, making them very simple organisms.</p><h4>The Algorithm</h4><p>The fish evolve using a genetic algorithm. In the first generation most of the fish are not very capable because their neural network brains have been initialised with random weights. The best fish in that generation are selected for the next generation, and the rest of the new generation is created by breeding those successful fish. This pattern is repeated for as many generations as we like.</p><h4>The Fitness</h4><p>How to decide which fish are selected for the next generation and to become parents? Fitness was determined by how much food a fish was able to eat. Fish that were better at eating food were more likely to be selected. To prevent the fish clumping together, a small cost was incurred by fish that got too close to each other.</p><h4>The Experiment</h4><p>The fish of the first generation behave mostly at random, though some fish are slightly better at getting the food than the others.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8irX6i6po-y_-HuRzEMPEQ.gif" /></figure><p>After only one generation, several of the fish are able to head directly towards food.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B0DZfx2yl7vj7e3nS5zplQ.gif" /></figure><p>After five generations, most of the fish are quite good at moving towards food. After the food is gone, they quickly spread apart because of the selection pressure to not get too close to other fish.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eBPDHeFEE7HmqdnWKMuhnQ.gif" /></figure><p>After twenty generations, the fish have developed a swirling strategy that allows them to avoid getting too close to each other while also moving towards their closest food. This strategy also has the benefit that when several fish happen to be moving towards the same closest food, the swirling pushes some fish away from that food, allowing them the possibility of stumbling onto other food with less competitors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PekTd7Yw-49vqwllR4zyRA.gif" /></figure><p>Not much has changed after one hundred generations. A bit of fine tuning of the weights, slightly wider arcs when moving towards food.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jCOfMFrAMpItS8o4Yac8Bg.gif" /></figure><p>Even in the one thousandth generation, not much has changed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eSqkgdaUbIZ5AXT1ZL_ytg.gif" /></figure><p>So how do our fish perform over the generations? It’s interesting to see that after about fifty generations, the population average, best and worst performance stabilises. In the early generations, some efficient fish were able to get comparably high scores because of weak competition, but as the generations progressed, the weaker fish were replaced with children of the fitter fish.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*V9sUUPdigYgR2tWrZz0iZQ.jpeg" /></figure><blockquote>Now, <em>here</em>, you see, it takes all the running you can do, to keep in the same place — <strong>Lewis Carroll</strong>, <strong>Alice Through the Looking Glass</strong></blockquote><h4>Some Thoughts on the Project</h4><p>There were a few things I had to tweak to get the fish to behave in a way I wanted. First was the rate of convergence of the population. I adjusted this by choosing the number of individuals to select for breeding in the next generation. When I set this to 20% of the population, the population was very quick to converge, setting it to 50% seemed to work better. Increasing the population size also slows down convergence. Another variable I experimented with was the number of food. I noticed that a higher fish to food ratio led the fish to converge more quickly and to move towards food more aggressively.</p><p>My first experimental runs did not penalise against organisms getting too close together, and so when the population converged, all the fish had similar brains and would clump together if they were after the same food. This led me to try out reward shaping. To encourage the fish not to clump up, I created a small cost to their fitness if they got too close to each other. The ‘small cost’ I tried first was too big and sent the fish swimming away from each other and off the screen away from the food. Getting the fish to behave how I wanted them to was a matter of testing different cost values.</p><p>In generation 100, it looks like a fish that ignored the other fish and went straight for the food might do well. I reasoned that a fish that ignores other fish when all the other fish avoid it might excel. This strategy would not always do well though, because when it’s strategy became the dominant one in the population, the fish would clump together. This type of pressure is called <a href="https://en.wikipedia.org/wiki/Frequency-dependent_selection">frequency-dependent selection</a> and can sometimes create a cyclic pattern in behaviour. Despite searching, I wasn’t able to observe this in any of the experimental runs.</p><p>Lastly, there was a bug in my code. My code still ran and the fish still optimised, it was only after staring at their behaviour for several generations that I realised something must be wrong. Optimising systems with stochastic elements can make discovering bugs difficult. The system will still likely achieve some incremental improvements, and odd behaviour can be attributed to mutations.</p><h4>Bloopers</h4><p>Lot’s of things can go wrong when coding up ‘artificial life’. Here are some of the weirder things I came across.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*le5bMFhc8lektAr9B-c_wA.gif" /><figcaption>Without the selection pressure to not get too close to each other, the fish clump together. The neural network weights slowly converge as the generations progress. This means that for fish in close proximity, the next move is likely to be the same.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*78Tt34fGENINepGhlsxw2g.gif" /><figcaption>Due to a difficult to discover bug, most of these fish swim off the screen. The fish still learn though, despite the bug</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GG1Le0e1uZIornJuspMRQg.gif" /><figcaption>These fish get stuck between two foods</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3bG22fZDlKo-BYaGqVjfEA.gif" /><figcaption>Misshapen rewards made these fish circle around the food instead of eating it</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rbcR8Dn-dgou1m7fbCyZaA.gif" /><figcaption>I have no idea about this one</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-rNJ40NyMEM9-TO8Be_Ivg.gif" /><figcaption>This one isn’t a blooper. When food isn’t scarce, the fish don’t behave so aggressively</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jaBgi1qrNBT9kyu94oCR7A.gif" /><figcaption>Due to a difficult to discover bug, most of these fish lose motivation. Some fish can learn though, despite the bug</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*W5kJudjQtDyYuydbWLHtjw.gif" /><figcaption>This was when I mixed up the neural network outputs</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*liyugECbAl1XdYpnDc5_yQ.gif" /><figcaption>None of these poor fish seem able to get a single food</figcaption></figure><p>Thanks for reading. I had a lot of fun evolving these fish and observing their behaviour. I hope you enjoy them too.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5b7599c4c2e9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Evolution Strategies as a Scalable Alternative to Reinforcement Learning — Paper Summary]]></title>
            <link>https://medium.com/@benjamin22-314/evolution-strategies-as-a-scalable-alternative-to-reinforcement-learning-paper-summary-691161b52ddd?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/691161b52ddd</guid>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[openai]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Sat, 26 May 2018 06:15:22 GMT</pubDate>
            <atom:updated>2019-05-26T09:20:53.202Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*EkeKcoM8jpGnd-mK." /><figcaption>“Flowers in a field near a small mountain pond area.” by <a href="https://unsplash.com/@verstuyftj?utm_source=medium&amp;utm_medium=referral">Jonas Verstuyft</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>In 2017 OpenAI produced a paper on <a href="http://arxiv.org/abs/1703.03864">Evolution Strategies as a Scalable Alternative to Reinforcement Learning</a> . One of the researchers of the paper, Ilya Sutskever gave this <a href="https://www.technologyreview.com/s/603921/elon-musks-openai-unveils-a-simpler-way-for-machines-to-learn/">talk</a> on the work OpenAI was doing with Evolution Strategies (ES) and OpenAI has itself produced a <a href="https://blog.openai.com/evolution-strategies/">blog post</a> on the paper. This is a personal summary of the research.</p><p>The paper gives details on the performance of using the ES algorithm to train a deep neural network when applied to Reinforcement Learning problems and compares those results to the more conventional Reinforcement Learning method of using back-propagation. It suggests that for some problems specific to Reinforcement Learning, ES has several advantages. Ilya stresses in his talk that the advantages ES has in the Reinforcement Learning domain do not apply to supervised problems where gradient descent via back-prop already works well.</p><h4><em>Parameter Space</em> and A<em>ction Space</em>.</h4><p>Before getting into ES, let’s talk about <em>parameter space</em> and <em>action space</em>. Usually neural networks are trained using back-propagation to update the weights. When applied to Reinforcement Learning, the neural network explores different actions in the environment and these actions return values which is used to update the weights of the network. This can be considered searching in the action space. ES searches for the best weights of the network where the environment is a black-box that returns a score on the performance of any particular set of parameters. This is known as searching the parameter space.</p><h4>What is Evolution Strategies?</h4><p>ES is somewhat unfortunately named, as I view it has more of a variation of Random Search than in any way being related to the principles of evolution. Before describing ES, I think it’s helpful to understand Random Search. Consider the problem of finding weights for a neural network in a Reinforcement Learning task, where the network is given a score based on how well it performs in a particular environment. Random Search samples points (potential weights) in a hyper-sphere around the origin. The ‘best’ point is selected and then a hyper-sphere around that best point is sampled. The next best point is found and the cycle repeats until some stopping criteria. ES is similar to Random Search but instead of the new ‘best’ point being decided by the single best performing point, the new ‘best’ is calculated using the average of the difference between the previous ‘best’ and the sampled points, weighted by their ‘fitness’ (the value returned from the environment). Pseudo code is below. In this way, the new ‘best’ will move in the direction that maximizes performance in the environment. This can be considered as a type of gradient descent based on <a href="https://en.wikipedia.org/wiki/Finite_difference">finite differences</a>, even though no gradient is being calculated.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/663/1*81YoSaKm1drhY0iYRokEyQ.png" /></figure><p>The paper describes the mathematics of why the ES algorithm works but I personally found that it hard to follow because it left out a lot of details. David Barber has written a <a href="https://davidbarber.github.io/blog/2017/04/03/variational-optimisation/">blog entry</a> clearly going through all the steps and is worth the read if you would like to understand the maths behind the algorithm.</p><h4>What’s so good about ES?</h4><p>ES has several advantages compared to training by back propagation.</p><ul><li>It saves computation because you don’t have you calculate the gradient.</li><li>It’s less susceptible to confusion for tasks involving long time horizons or delayed rewards which is a problem for reinforcement learning with back-prop.</li><li>It’s easy to parallelize and can therefore be much faster.</li></ul><h4>What’s not so good about ES?</h4><ul><li>Needs more data for similar results. From the experimental results, on the order of 3 to 10 times as much data for some Atari games.</li></ul><h4>Parallelization</h4><p>It is possible to separate the individual networks in the ES population to different CPU cores so each network can perform an episode in the environment at the same time. Before starting the algorithm, the random seeds used to create the initial population and the perturbations (mutations) are defined. During training, each CPU worker has knowledge of these seeds, so workers only need to communicate their fitness score, a scalar, to each other to be able to update their parameters.</p><h4>Experiments</h4><p>The researchers applied ES to <a href="http://www.mujoco.org/">MuJoCo</a> (continuous robotic control, eg walking/hopping/swimming) tasks and several Atari games. ES was able to solve the MuJoCo tasks and performed competitively on the Atari games. Matching the network architecture and level of computation presented in the paper <a href="https://arxiv.org/abs/1602.01783">Asynchronous Methods for Deep Reinforcement Learning</a>, ES performed better in 23 games and worse in 28. Due to parallelization, it was possible to solve the 3D Humanoid walking task in just ten minutes using 1440 CPU cores.</p><h4>Conclusion</h4><p>This paper shows that ES can be successfully applied to training deep neural networks for Reinforcement Learning problems. It has several benefits in this domain, including scaling to parallel workers and not needing to calculate a gradient which can compensate for the need to use more data. It is exciting to see work demonstrating that algorithms that search the parameter space can be effective in Reinforcement Learning.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=691161b52ddd" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Efficient Evolution of Neural Network Topologies — Paper Summary]]></title>
            <link>https://medium.com/@benjamin22-314/efficient-evolution-of-neural-network-topologies-paper-summary-c8031aaa8692?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/c8031aaa8692</guid>
            <category><![CDATA[reinforcement-learning]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Wed, 11 Apr 2018 06:02:15 GMT</pubDate>
            <atom:updated>2018-04-12T01:18:57.555Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*bKflWfS3RmetUcnB." /><figcaption>Photo by <a href="https://unsplash.com/@landscapeplaces?utm_source=medium&amp;utm_medium=referral">Federico Bottos</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>This is a brief summary of Kenneth Stanley and Risto Miikkulainen’s 2002 paper ‘<a href="http://nn.cs.utexas.edu/downloads/papers/stanley.cec02.pdf">Efficient Evolution of Neural Network Topologies</a>’. It’s an oldie but a goody in the research area of Topology and Weight Evolving Artificial Neural Networks (TWEANNs). Kenneth and Risto introduce a new algorithm called NeoroEvolution of Augmenting Topologies (NEAT). This summary assumes some familiarity with evolutionary algorithms (EA) and neural networks (NN).</p><h4>Why TWEANNs are cool</h4><ul><li>They use evolutionary algorithms to optimise the weights and the topology (structure) of the neural net.</li><li>They can be used to pick a network architecture instead of designing one by hand.</li><li>They are an alternative to stochastic gradient descent (SGD) for optimising the weights of the network.</li></ul><h4>Why NEAT is cool</h4><ul><li>It has a clever way of encoding the structure of a network that allows for crossover between networks with different topologies.</li><li>It protects innovation in the population with speciation.</li><li>It incrementally grows networks from a small structure.</li></ul><h4>It’s all in the genes</h4><p>Each gene is a connection in the network and specifies the connection weight, the nodes it’s connected to (in-node and out-node) and if the gene is expressed or not. Also an innovation number that we’ll get to in a sec. The network is represented by a genome made up of these types of genes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/338/1*KzlnCjHgi0WdLPkkmcNK5Q.png" /><figcaption>from original paper</figcaption></figure><h4>What about mutation?</h4><p>There are two types of structural mutation (as opposed to connection weight mutation), adding a connection between two nodes that were not previously connected and adding a new node. When a new node is added, an existing connection is disabled and replaced with a new node that connects to the input and output of the now disabled node. This means two new genes are added to the genome. What are the weights of these two new connections? Who knows, the paper doesn’t mention it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/332/1*X2_U9JWjIMr_F4Cds4v6wQ.png" /><figcaption>from original paper</figcaption></figure><h4>Where do babies come from?</h4><p>Remember the innovation number from earlier? That’s the key to crossover of the genomes. Every structural mutation creates a new gene in the genome. When that happens, the new gene is given a unique innovation number. When you have two individuals ready to reproduce, you take their genomes, line up the genes according to the innovation numbers, choose a random split point and perform crossover. When there are genes that do not match up, ie not in both genomes, the unmatched genes in the fitter parent are passed on and the unmatched genes in the less fit parent are ignored. (although that’s not what’s shown in figure 3).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/337/1*jlnAlk6uXDqScwirtuY05w.png" /><figcaption>from original paper</figcaption></figure><h4>Give peace (and recent mutations) a chance</h4><p>Evolutionary algorithms are excellent stochastic hill climbing optimisors. But sometimes you need to get worse before you get better. New structural mutations almost always have a negative impact on fitness. So speciation is used to give these mutants a chance to optimise. A measure called the compatibility distance is used to group the genomes into different species. When it comes to selecting parents, the individuals are then compared to other individuals with similar genomes in the same species instead of the population as a whole, which allows the structure some time to be optimised instead of being immediately cut from the population.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/187/1*CTVqDFuTG8YH6zDBSFJPIA.png" /><figcaption>Compatibility Distance; from original paper</figcaption></figure><p>The compatibility distance is defined using a linear combination of the number of excess genes E (unmatched genes at the end of a genome), disjoint genes D (unmatched genes before the end of the genome) and the average of the weight differences of the matching genes W. The advantage of using speciation is that it protects innovation. The disadvantage is that it adds hyper parameters, c1, c2, c3.</p><p>Looking at this from 2018, it makes me wonder if this was the precursor to novelty search.</p><p>The size of the species population grows or shrinks proportionally to the average species fitness compared to the overall population fitness. Each generation a percentage of the top individuals in each species mate to replace all the individuals of that species. There is no indication in the paper of crossover between individuals of different species.</p><h4>From little things, big things grow</h4><p>In the NEAT algorithm, the individuals in the initial population are identical, all neural networks with no hidden nodes. From the the structure will incrementally complexify. This keeps the dimensions of the weight space smaller which allows for quicker optimisation. Also, the paper suggests that it’s easier to optimise the network for new structural mutations because the system as a whole is already somewhat optimised.</p><h4>Experiments</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*C90TBSQkAzPIBXw4NWnxJg.gif" /><figcaption>openAI pole balancing task, similar to the benchmark used in 2002. <a href="https://gym.openai.com/docs/">source</a></figcaption></figure><p>Back in the day, a common reinforcement learning benchmark was the pole balancing task. NEAT was applied to the hardest pole balancing task, balancing two poles without being given the velocity of the poles. It solved it with less computation than the other known methods that could solve that same problem.</p><p>To test the efficacy of incremental changes and speciation in the NEAT algorithm, some experiments were done on a simpler pole balancing task while restricting some of NEAT’s features. To examine the effect of incrementally growing the topology, NEAT was applied first to a network with fixed topology, then to an initial population of individuals with diverse structures (instead of the usual structure with no hidden nodes). To examine the effect of speciation, NEAT was run without speciation. These changes all had negative impacts on NEAT’s ability to solve the simple pole balancing task and the compute needed to solve the task if it could, though to varying degrees.</p><h4>Conclusion</h4><p>The NEAT algorithm incrementally grows more complex structures, allowing faster optimisation of the connection weights. Structural mutation adds complexity when needed and has the potential to get the network out of local optima. Speciation protects innovation. And don’t forget the innovation number that allows for efficient crossover, now that’s cool.</p><h4>Can NEAT get any more neat?</h4><p>Stay tuned</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c8031aaa8692" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Surprises in Digital Evolution]]></title>
            <link>https://medium.com/@benjamin22-314/surprises-in-digital-evolution-fecc120d03bc?source=rss-b9a3ad00eeea------2</link>
            <guid isPermaLink="false">https://medium.com/p/fecc120d03bc</guid>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[evolutionary-algorithms]]></category>
            <category><![CDATA[evolution]]></category>
            <dc:creator><![CDATA[Benjamin]]></dc:creator>
            <pubDate>Sun, 25 Mar 2018 09:05:01 GMT</pubDate>
            <atom:updated>2018-03-25T09:05:01.534Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*9xUm2WbCd-9Mfic0." /><figcaption>Photo by <a href="https://unsplash.com/@cgard?utm_source=medium&amp;utm_medium=referral">Crystal Gard</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>This article is a brief summary of the paper “<a href="https://arxiv.org/abs/1803.03453v1">The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities</a>” which was organised by Joel Lehman, Jeff Clune and Dusan Misevic and has contributions from researchers in digital evolution from over thirty institutions around the world.</p><p>The paper is a collection of 27 anecdotes illustrating that artificial organisms evolved in a digital environment are often capable of behaving in ways that are difficult for researchers to predict in advance. Here we will look at four of these anecdotes.</p><h4>What is Digital Evolution?</h4><p>The authors of the paper explain:</p><blockquote>Inspired by biological evolution, researchers in the field of digital evolution study evolutionary processes instantiated by computational methods.</blockquote><p>Examples of problems that digital evolution can be applied to include fitting weights to a neural network, developing the design of an airplane wing or finding a solution to the <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">travelling sales person problem</a>.</p><p>The authors quote Daniel Dennett, who states that there are three requirements for evolution to occur:</p><blockquote>replication, variation (mutation), and differential fitness (competition)</blockquote><p>These are conditions that can be met in both the biological and the digital world. In nature, organisms replicate by passing on their genes, variation occurs by mutation to genes or genetic recombination (for organisms with more than one parent), and fitness is determined by the degree to which an organism is successful in passing on its genes to the next generation. In a digital landscape, an artificial organism might be represented as a data structure. A fitness function, defined by the experimenter, determines which artificial organisms are allowed to replicate. Variation can be achieved by allowing small random changes to the data structures of the next generation.</p><h4>Selection Gone Wild</h4><p>Experimenters often start with an idea of what type of artificial organism they would like to evolve, and then design a fitness function to achieve this. This can lead to the situation where evolution ‘hacks’ the fitness function and produce results that diverge from what the experimenter intended.</p><p>As an example of this, the paper describes work by Karl Sims, who evolved 3D virtual creatures that could move in a virtual environment.</p><blockquote>In a simulated land environment with gravity and friction, a creature’s fitness was measured as its average ground velocity during its lifetime of ten simulated seconds. Instead of inventing clever limbs or snake-like motions that could push them along (as was hoped for), the creatures evolved to become tall and rigid. When simulated, they would fall over, harnessing their initial potential energy to achieve high velocity.</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgifs.com%2Fiembed%2F1rqx6V&amp;url=https%3A%2F%2Fgifs.com%2Fgif%2Fwhy-walk-when-you-can-somersault-1rqx6V&amp;image=https%3A%2F%2Fj.gifs.com%2F1rqx6V.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=gifs" width="480" height="270" frameborder="0" scrolling="no"><a href="https://medium.com/media/7d06e2a29f9648a6fed3336660203578/href">https://medium.com/media/7d06e2a29f9648a6fed3336660203578/href</a></iframe><h4>Automated Bug Discovery</h4><p>Many experiments to evolve artificial organisms that are impractical or impossible to develop in the physical world are instead evolved in a simulated environment. These simulations are often designed to mimic the physical world but do not do so perfectly. Evolution can take advantage of these minor flaws and produce infeasible solutions. Though this may not be the intended result, it allows researchers to find and fix bugs in the simulations.</p><p>The paper describes work by Ecart and colleagues where an evolutionary algorithm called MAP-Elites discovered a bug in the simulation.</p><blockquote>the robot’s gripper was crippled, preventing it from opening and closing. It was therefore expected that the robotic arm could move the small box in only limited ways, i.e. to push it around clumsily, because it could no longer grasp the box. Surprisingly, MAP-Elites found ways to hit the box with the gripper in just the right way, to force the gripper open so that it gripped the box firmly []! Once holding the box, the gripper could move to a broad range of positions, exceeding experimenters’ expectations.</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgifs.com%2Fiembed%2FYvxoyn&amp;url=https%3A%2F%2Fgifs.com%2Fgif%2Funexpected-grasping-Yvxoyn&amp;image=https%3A%2F%2Fj.gifs.com%2FYvxoyn.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=gifs" width="480" height="270" frameborder="0" scrolling="no"><a href="https://medium.com/media/b18c33a95cc567a6f4ff590caa3f4136/href">https://medium.com/media/b18c33a95cc567a6f4ff590caa3f4136/href</a></iframe><h4>Exceeding Expectations</h4><p>Occasionally digital evolution surprises by producing feasible results that are beyond the expectations of the experimenter.</p><p>Research by Cully et al, also using the MAP-Elites evolutionary algorithm, is presented as an example.</p><blockquote>MAP-Elites searched for the fastest moving gait possible across every combination of how often each of the robot’s six feet touched the ground. Naturally, the team thought it impossible for evolution to solve the case where all six feet touch the ground 0% of the time, but to their surprise, it did.</blockquote><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgifs.com%2Fiembed%2FjqM7Yl&amp;url=https%3A%2F%2Fgifs.com%2Fgif%2Fa-behavior-performance-map-containing-many-different-types-of-walking-gaits-jqM7Yl&amp;image=https%3A%2F%2Fj.gifs.com%2FjqM7Yl.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=gifs" width="480" height="270" frameborder="0" scrolling="no"><a href="https://medium.com/media/b581e711dc3fb7d265235d7101e872c6/href">https://medium.com/media/b581e711dc3fb7d265235d7101e872c6/href</a></iframe><h4>Convergence with Biology</h4><p>Many digital evolution researchers have noticed that, despite the numerous differences between the digital and biological landscapes that evolution plays out in, the artificial organisms they evolve often have characteristics similar to organisms found in nature.</p><p>Artificial organisms developed by Cheney et al demonstrate an ability to evolve phenotype such as muscle groups and stiff bone like structures.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fgifs.com%2Fiembed%2Fwm5Mm1&amp;url=https%3A%2F%2Fgifs.com%2Fgif%2Fevolving-soft-robots-with-multiple-materials-muscle-bone-etc-wm5Mm1&amp;image=https%3A%2F%2Fj.gifs.com%2Fwm5Mm1.gif&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=gifs" width="480" height="270" frameborder="0" scrolling="no"><a href="https://medium.com/media/f272fa1cdc49462bf98e98e312bd4481/href">https://medium.com/media/f272fa1cdc49462bf98e98e312bd4481/href</a></iframe><h4>Conclusion</h4><p>The anecdotes discussed in this article and the original paper present a strong case that the artificial organisms are capable of achieving complex and creative solutions. They also suggest that incorrect assumptions in the fitness function or the simulated environment can have unexpected results if not handled with caution.</p><p>A <a href="https://www.refseek.com/search?q=%22you+get+what+you+select+for%22">common saying</a> among researchers in digital and biological evolution is that:</p><blockquote>You get what you select for.</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fecc120d03bc" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>