Showing posts with label algorithms. Show all posts
Showing posts with label algorithms. Show all posts

Tuesday, October 15, 2019

AI can help, if trained to do so

AI can help humanity; but only if it isn't trained with human biases and ideologies. This is the same with raising and training people, but with a machine it could be easier to get better results.

AI is coming for you, or is it?

There seems to be a large amount of both excitement and fear around the emergence of artificial intelligence. Will it take over? What is it? Can it save the world? Those are all very big questions, and for a new technology to generate these sorts of questions and to actually make us question its impact it could have on our lives. This really illustrates just how big people think it is, or could be.

I'll save many of the explanation of AI to much of the published articles and just sum it up: AI is a new brain, we have made a new brain without giving birth to a new person or other organic being, but instead building a machine. This brain has a tremendous amount of capability, but it doesn't have the knowledge required to be useful yet. It need to learn, and be trained.

What seems to cultivate fears in people is the amount of time ti take to provide the brain with knowledge. People take years of care and feeding to become thinking adults, AI machines can seemingly take minutes or hours to learn analogous tasks. Why would we be scared of that capability?

For good or evil? 

How is it that just because the someone is smart that the others around them assume their intentions to be good, or evil? Just because a person can overwhelm another physically or mentally, does it follow that they will? That seems to be a reach, and we might know better by understanding the impact good people have had. It would follow then, if the person knew the difference between good and evil and the consequences of each school of thought; then they would make decisions with the intention of the good. This understanding of not taking a piece of the pie, but instead making a bigger pie and sharing it shows enlightenment of that persons intellect. The training of the AI machine may not be any different.

Are you scared when you meet a smart person? Are you scared when you meet a dumb one? Maybe they deserve the same reaction; but in the meeting of people during the course of a day you will surely generate a lot of fear for yourself.

Decisions, decisions

Why then do people make bad decisions? There are biases that lead them down bad paths. They fall victim to their own deficiencies to justify actions that are vain, greedy, gluttons, envy, etc. They just don't seem to be able to help themselves. The AI brain may present an opportunity to provide decision making that is free of these organic human constraints.

Humans are able to reason and solve problems effectively; but run into difficulties when the brain is clouded by ideologies; whether they are political or religious ones. For AI to help solve us solve some of our own problems, it can be trained to do so; as long as that training isn't an ideological nature.

Bias

Bias needs to be learned. For the various biases that complicate people making good decisions. Confirmation bias, survivor bias or loss aversion; these are learned behaviors and reside in the sub-conscious to be triggered at any time. This can happen without the host really know what is going on.
This is also not consistent. People have bad days, and the anxiety of having a bad (or good) day will affect your decision making. As long as the electricity is on; machines don't by nature have bad days.

To Train AI properly, the validation of the training needs to incorporate not just what the machine knows, but the validate what it doesn't know, and then provide the training so that the machine is adverse to learning the bad habits.

Is this not the same as raising a child or mentoring an apprentice? It might not be that different in what we are doing; but how we do it can be improved to get better outcomes in the decisions the machine (or person) makes.

Tuesday, January 08, 2019

Undisciplined refactoring can create more spaghetti code


When finding a blob of code that is hard to comprehend, it is tempting to just dig in and break apart the blob into an number of seemingly related functions. Functional decomposition is a powerful concept in math and computer science. It breaks down a large and sometimes incomprehensible solution into one that is easier to understand; and as a result provides a more stable solution.

In the heat of the moment this can make a lot of sense by reading the code and breaking it apart for what it currently does and perhaps not what its intended to do. What this can lead to a more convoluted code-base in the name of refactoring.
Its easy to cut these corners when you are under pressure to fix a ticket, and/or tired from a long week. In the rush to fix be careful to see the larger design picture so you don't end up pushing that work further into the future.

So, instead of analysing what the software does at the moment, take a minute to understand what it is supposed to do. This is sometimes referred to as 'first principles' and is key to really understanding the problem; and as a result create a nice solution. How then would we do that in programming? By taking a proven problem solving approach that is used to solve any applied mathematics problem.

How to solve it

Remember our fundamental "How to solve it" steps. Understand, plan, execute, review. For seemingly easy fixes it can seen as overkill to keep to skip the first two steps and understand (design) on the fly while we execute (programming) on the solution. Stick to the more disciplined approach of moving through the steps as a simple checklist so you don't have to keep everything in your head.
This isn't a checklist to go through once, its really a mechanism to break down larger problem and build the solutions accordingly.

A moment to understand the Design

Are the intentions of the feature defined? If not, write down what value this feature is supposed to deliver. The features that implement this are defined by their responsibilities, not necessarily what its doing at the moment.
Take a moment to understand not what the code is doing, but what the responsibilities of the containing object or function has. Understand these responsibilities into an interface or better formed class, and then re-factor to fulfill those responsibilities.
Understanding the actual responsibilities can take some time, but not much; and you do have the time to get this into a coherent structure so you don't have to revisit it later. Draw a diagram and link the dependencies, inputs and the outputs to get a solid understanding of what this is supposed to do.

How it fits in. Whats the plan?

How does this class fit into the bigger picture? A good strategy is to use the 4 c model to see where your class or function fits into the component you are modifying, and if that 'fits in' to the intended functionality. Good architecture fits in, and doesn't stand out.

A Simple Example

Ok, enough talk-talk; lets go through an example. Lets say we are building a feature that lets users login to our fancy web app with social accounts. To 'make it work' and experimenting with the API we might end up with something like:


# using authomatic library and skipping code segments for sake of example
def get_user(network):
    email = None
    if (network == 'linkedin'):
        url = 'https://api.linkedin.com/v1/people/~?format=json'
        response_data = authomatic.login(self, network)
        first_name = response_data.get('firstName')
        last_name = response_data.get('lastName')
        email = response_data.get('emailAddress')
    elif (network == 'twitter'):
        url = 'https://api.twitter.com/1.1/statuses/user.json'
        response_data = authomatic.login(self, network)
        email = response_data.get('email')
    elif (network == 'facebook'):
        url = 'https://api.facebook.com/v2.12/'+result.user.id+'/me?fields=id,name,email,picture'
        response_data = authomatic.login(self, network)
        email = response_data.get('email')

    # we have a user class that requires an email in the constructor
    return User(email)


# 'refactor' attempt to smaller functions
def get_facebook_user():
    email = None
    url = 'https://api.facebook.com/v2.12/'+result.user.id+'/me?fields=id,name,email,picture'
    response_data = authomatic.login(self, network)
    email = response_data.get('email')
    return User(email)

def get_linkedin_user():
    url = 'https://api.linkedin.com/v1/people/~?format=json'
    response_data = authomatic.login(self, network)
    first_name = response_data.get('firstName')
    last_name = response_data.get('lastName')
    email = response_data.get('emailAddress')
    return User(email)

def get_twitter_user():
    url = 'https://api.linkedin.com/v1/people/~?format=json'
    response_data = authomatic.login(self, network)
    first_name = response_data.get('firstName')
    last_name = response_data.get('lastName')
    email = response_data.get('emailAddress')
    return User(email)


def get_user(network)
    if (network == 'linkedin'):
        return get_linkedin_user()
    elif (network == 'twitter'):
        return get_twitter_user()
    elif (network == 'facebook'):
        return get_facebook_user()


This is maybe a bit better, but to modify this to get more data from the api or to add error handling, the functions just expand as you add more logic. This is also only able to work when the app is running, how do I test this?
Let's take a moment and understand what we are trying to do:


  1. The application needs a User object to identify who is logged in
  2. The application can authenticate with an external identity provider
The responsibilities of this object then become: Authenticate, build User, handle errors, so lets refactor to a class that assumes these responsibilities, and no matter the network we use, we end needing these responsibilities fulfilled.

Even better, use an abstract class or interface to define the behavior. Objects have responsibilities and those responsibilities are fulfilled by behavior

The interface defines the behavior, so test and check for exceptions from logical methods that are defined in an interface. This is the main contract that the component has. (should have...of course. So much code doesn't have any structure)


class SocialAuthenticator(object):
    @abc.abstractmethod
    def authenticate(self, user_data, response_data):
        pass 
    @abc.abstractmethod
    def build_user(self, data):
        pass 
    @abc.abstractmethod    
    def get_api_data(self):
        pass

# So for any network you are using, you just extend with its own logic
class TwitterAuthenticator(SocialAuthenticator):

    def authenticate(self):
        return authomatic.login(self, 'twitter')
    
    def build_user(self, result):
        response = self.authenticate()
        email = response.get('emailAddress')
        return User(email)
        
    def get_api_data(self, result):
        url = 'https://api.twitter.com/1.1/statuses/user_timeline.json'
        response = result.provider.access(url, {'count': 5})
        return response

# This structure is more testable, so you can get the response data, and save it as a json file, and use that to test the creation of your users
import unittest
class test_authentication(unittest.TestCase):

    def get_twitter_data():
        #load and return file that would be reponse from twitter

    def test_create_user(self):
        auth = TwitterAuthenticator()
        self.assertNone(auth)
        test_result = get_twitter_data()
        user = auth.build_user(test_result)
        self.assertEquals(user.email, 'mytestaccount@whateves.com')

    #subsequent tests for creating users from different identity providers

Now we have a structure we can test without running the application, and can extend to get more data from each network. Also, we can just make a new class for any new networks we want authentication and user data from.

Wrap it up

By taking a pause and defining the responsibility of the object we were able to better understand the problem we had, which enabled a coherent plan for the execution of the solution. This results in a more coherent design which is much more easily understood, and also testable since we have an interface (or abstract class) to test against.


https://en.wikipedia.org/wiki/Decomposition_(computer_science)

Tuesday, November 15, 2016

Algorithms intro: Profiling python code


When developing software and implementing algorithms its always important to be as efficient as possible, to have the most elegant solution that is concise, understandable to others, but most importantly uses the resources it has in the most efficient way.

This post extends the previous http://jseller.blogspot.ca/2016/11/algorithms-intro-implementing-math-proof.html and profiles the algorithms we created to implement Euclids GCD method

Profiling

With python and most every language has some profiling tools to check various computer resources; most frequently this is the memory used and CPU cycles consumed. For our algorithm post we are just concerned with the time any of our algorithms take to execute.


import cProfile, pstats, io

#you can run any code as a string to be executed:
cProfile.run('fill_rectangle_with_squares(Rectangle(24000,19453))')

#but the profile object can also be enabled and disabled to run many lines.
pr = cProfile.Profile()
pr.enable()
fill_rectangle_with_squares(Rectangle(2400000,194530))
pr.disable()
pr.print_stats()

With

If there are many lines, this can get a little difficult keeping the first two and last two in the same spot, or accidentally deleted the cleanup part. Python has a 'with' statement to make this nice and clean. http://effbot.org/zone/python-with-statement.htm

import cProfile, pstats, io
class profile_block:
    def __enter__(self):
        self.profile = cProfile.Profile()
        self.profile.enable()
        #set things up
        #return thing
    def __exit__(self, type, value, traceback):
        #tear things down
        self.profile.disable()
        self.profile.print_stats()

Try running a few versions and look at the output. It will probably take some larger numbers until you can see a change. The times depends on the machine, but by using the 'with' block we know the disable and printing will always happen, and the code is nicer.

with profile_block():
    fill_rectangle_with_squares(Rectangle(24000000,19453003))

with profile_block():
    fill_rectangle_with_squares_iterative(24000000,19453003)

Running the different approaches with the large example show a 3x difference with the optimized version.


with profile_block():
    fill_rectangle_with_squares_iterative(2400000223334219423423424234240,1945303434230234234242322)

with profile_block():
    greatest_common_divisor(2400000223334219423423424234240,1945303434230234234242322)

The output. This is a big improvement between our two versions.


fill 2400000223334219423423424234240, 1945303434230234234242322 with squares 
smallest square found 2, 2 
         6 function calls in 0.989 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 euclid.py:104(__exit__)
        1    0.000    0.000    0.000    0.000 euclid.py:22(__init__)
        2    0.000    0.000    0.000    0.000 euclid.py:25(__str__)
        1    0.989    0.989    0.989    0.989 euclid.py:55(fill_rectangle_with_squares_iterative)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

greatest common divisor 2
         3 function calls in 0.386 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 euclid.py:104(__exit__)
        1    0.386    0.386    0.386    0.386 euclid.py:77(greatest_common_divisor)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


Wrap it up

From the first part of this post we solved the problem with computation and in this case it was a classic, Euclid Greatest Common Denominator method. His proof in Elements uses only geometry, but we also used geometry as a handy tool to visualize and understand the proof.
What we wanted to find out though, was how to validate this method with computation, and understand which approach works best.
As recursive implementations can more closely model the real world scenario, we have to keep in mind that this is being solved with computation, so our iterative approach is able to take advantage of the computing power at hand.

Finding out how well that actually performed is the job of profiling, and a well measured system, or just a small part of it, can go a long way to understanding how to write efficient code.



Algorithms intro: implementing a math proof


What's a nice way of showing a visual example to better understand how a math proof can be implemented as an algorithm in code? Here we are showing an example of implementing an algorithm, comparing iterative and recursive algorithms for solving a method; and validating the results with profiling.

In problem solving, a great methodology to use is: Understand, Plan, Execute and Review.
We will use a bit of geometry to understand the problem, and then plan how to solve it; then we will implement code to execute that plan and review how things worked out.

Understand

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b. (or x and y).

We can use some geometry to visualize this, check out this video of it in action. From that, it looks like a matter of:
  1. Fill with squares along the shortest side of the rectangle
  2. For the remaining rectangle, fill with squares again, until smallest square is found.

Plan

Lets write down the steps in more detail:
  • fill rectangle with squares
    • find shortest sid
    • divide long side by square side, get remainder
    • if remainder is 0, smallest square is found
  • for remainder, fill rectangle with squares

Execute

To model the visualization, lets make a Rectangle object, and use that with a function. Lets start with what we know, the Rectangle:

class Rectangle(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __str__(self):
        return "%s, %s" % (self.x, self.y)

Now lets plan how to fill the rectangle just like the visualization happens, the next rectangle is filled, and so on until the end. This style of implementation is recursive.
  • fill_rectangle_with_squares(2,4)
    • fill_rectangle_with_squares(2,2)
      • 2 is smallest square
We keep calling the fill_rectangle_with_squares function, until the x and y sides are equal. This is the stopping condition.

def fill_rectangle_with_squares(rectangle):
    print("Fill " + str(rectangle))
    # check the sides, if they aren't equal make a new rectangle with the remaining
    if rectangle.x == rectangle.y:
        print('smallest square found %s ' % str(rectangle))
        return rectangle.x
    elif rectangle.x > rectangle.y:
        return fill_rectangle_with_squares(Rectangle(rectangle.x - rectangle.y, rectangle.y))
    elif rectangle.y > rectangle.x:
        return fill_rectangle_with_squares(Rectangle(rectangle.x, rectangle.y - rectangle.x))

Now we call the function with an assert to test the result

To test to see if this function returns what we want, we use assert to check. We want to assert that a 2 by 4 rectangle is anything other than 2. Lets test some others as well

assert fill_rectangle_with_squares(Rectangle(2,2)) == 2
assert fill_rectangle_with_squares(Rectangle(140,68)) == 4

assert fill_rectangle_with_squares(Rectangle(24,12)) == 12

Review

Lets keep reviewing our solution with other sizes, like: Rectangle(143,62) and Rectangle(270,192). These work fine, but what happens when larger values are involved?

Rectangle(2400000223334219423423424234240,1945303434230234234242322)

When this would fail would vary from machine to machine, but on my home laptop I get a:

RuntimeError: maximum recursion depth exceeded


This means the call stack limit is reached, and this limit is bound by the design of the python language itself. Some languages like LISP don't have this limitation, it's just ends up using what resources it has. The limit is imposed because the amount of callable memory is a finite space on the machine. If you are using a large amount of recursion depth, and not getting the results you need then there is way to only bound by time, and the running of the CPU.

How can we make this better? Lets implement the algorithm using iteration.

def fill_rectangle_with_squares_iterative(x,y):
    rectangle = Rectangle(x,y)
    print('fill %s with squares ' % str(rectangle))
    found = False
    while not found:
        found = rectangle.x == rectangle.y
        if rectangle.x > rectangle.y:
            rectangle.x = rectangle.x - rectangle.y
        elif rectangle.y > rectangle.x:
            rectangle.y = rectangle.y - rectangle.x
    print('smallest square found %s ' % str(rectangle))

So far, so good, and the tests work with fill_rectangle_with_squares_iterative(24000000,19453003)

Can the iterative version take the massive difficult rectangle that blew the call stack with the recursive version?

fill_rectangle_with_squares_iterative(2400000223334219423423424234240,1945303434230234234242322)

It does, but takes a couple seconds.

Optimize

I know it took a couple seconds because the console lets me know how long any code execution takes. What's really happening here? To find out more I need to profile the code which will will in the second part of this post.

Before we do though, lets take a crack at optimizing the code even farther.

When you look at the iterative function, see that we are just modifying the Rectangle objects x and y values. We can just keep track of the x and y and not bother making the Rectangle object at all. We could maybe make one object and pass it instead of making a new object for each call, but lets go the step further. It's only 2 variables that makes it concise.

We used the Rectangle as a way to visualize the problem, but nice terse notation is possible and ends up being very clear, so lets boil down the description to the original:

Given two (natural) numbers not prime to one another, to find their greatest common measure.
(The Elements: Book VII: Proposition 2)


def greatest_common_divisor(x,y):
    while not x == y:
        if x > y:
            x = x - y
        elif y > x:
            y = y - x
    return x
    
print('greatest common divisor found %s' % (str(greatest_common_divisor(24,10))))

That's much more straightforward, and can probably be more concise, but I'd like to stop here to keep it readable and easier to understand.

Wrap it up

Lets review what we did in the post. we understood the problems and used some geometry to show a solution. Since it was Euclids proof, it seems like the right thing to do. We then planned a solution using recursion as it matched our real world model.
This worked to a point, but we reviewed our options and implemented an iterative method that could handle much larger rectangles. Once we had that solved we optimized for the computational abilities of the language and the machine we are using.

Our last implementation works for all the tests above, and certainly seems to run faster. How much faster?
We will profile all these functions and find out in the next post:  http://jseller.blogspot.ca/2016/11/algorithms-intro-profiling-python-code.html