Using Stochastic Processes to Help Humanize Artificial Intelligence

In developing examples for my book on HTML5 Canvas (HTML5 Canvas for Dummies) I experimented with using stochastic processes to improve the realism of an animated displays. Early versions of the displays appeared rigid and artificial. Adding stochastic (random) variations brought the displays closer to real life and made them much more fun to watch.

Stochastic processes are already important to AI. Stochastic Gradient Descent combined with Backpropagation is used to iteratively modify data values passed between neural network nodes in order to minimize the error between the output of the neural network and the correct/true result.

Recently, I've explored whether stochastic techniques can be used to help humanize AI. Humans are not robots. We don't mindlessly pursue objectives without variation from a given path. A more human-like AI would certainly make the man-machine interface more pleasant to deal with than a purely robotic one. There are certainly AI applications where we don't want these kind of random variations taking place ... in autonomous vehicles for example. 

You can experiment with one of my displays that employs stochastic processes ... click here to see it in action - once it's started, click control to see the variables you can modify using your keyboard.

Software Components Overview

Below is a list of links to and brief descriptions of common software components. It's useful to keep these in mind and reference them during software design as a shorthand for code that will be written to implement the design. Implementing a component could involve just a few or many lines of code.

A suggested way to use these components in solving/coding a computing problem is to include them using a Separation of Concerns design pattern folded into what I call Layered Logic Problem Solving that includes these steps:

  1. Describe in words the problem to be solved. This might include references to software components listed below. You might also include solution acceptance criteria, possibly in the form of formal acceptance tests.
  2. Draw a block diagram of the main problem solution pieces. For more complex problems, other types of diagrams can be used.
  3. Annotate the block diagram with references to components such as those below.
  4. Code the solution in your chosen programming language.

Communications

  • Client-Server Architecture: components include:
  • HTTP Requestindicates the desired action to be performed on an identified resource - actions include: 
    • GET: retrieve data
    • HEAD: retrieve without response body
    • POST: create new subordinate data
    • OPTIONS: retrieve supported actions
    • PUT: create/replace data
    • DELETE: delete the resource
    • CONNECT: convert connection to TCP/IP tunnel, usually to facilitate HTTPS SSL
  • Internet Protocol Suite:
    • Layers: Application/Transport/Internet/Link
    • Levels: Send/Receive, Controls/Routing, Values/Translations
  • Firewall: monitor/control of incoming/outgoing traffic
  • JSON: JavaScript Object Notation, Human Readable, Attribute-Value Pairs, Java JsonObject
  • Load Balancer: distributes workload across computing resources
  • Message: data sent across processes
  • Network: allows computers to exchange data
  • Protocol: Data Formats, Address Formats, Address Mapping, Routing, Error Detection, Acknowledgements, Sequence Control, Flow Control
  • REST: Representational State Transfer, Stateless, Client-Server, JSON data
  • Socket: endpoint of a connection across a computer network

Data

Algorithms & Processes

Objects

  • Class: object template
  • Container: collection of other objects
  • Design Patterns: reusable solutions to common software problems  
  • Object Oriented Design Patternsreusable solutions to common object oriented software problems
  • Generics: specify type or method to operate on objects
  • Cloud Computing: internet based computing that provides shared processing resources
  • Interface : all abstract methods
  • Mutability: mutable, immutable, strong vs. weak
  • Objects: variables, data structure or function referenced by an identifier
  • OOD: uses inheritance, abstraction, polymorphism, encapsulation, other design patterns

Views

  • Ajax: groups of technologies for client-side asynchronous web applications
  • Android Fragments: UI segmenting, own lifecycle, FragmentManager
  • HTML5 Canvas:  bitmap, javascript
  • CSS:  describes the presentation of information
  • HTML:  head, body, div, script
  • Widget: simple, easy to use applicator
  • XML: markup language that defines a set of rules for encoding documents

P Versus NP Complexity Theory

The P Versus NP issue deals with whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. This is a major unsolved problem in computer science.

In common, practical terms, it deals with how to identify problems that are either extremely difficult or impossible to solve.  In order of difficulty from easy to hard, problems are classified as P, NP, NP-Complete and NP-Hard.

So why do we care? When approaching complex problems, it's useful to have at least some idea of whether the problem is precisely solvable, or if an approximation is the best that can be accomplished. 

Big O Notation

Big O notation is a way to characterize the time or resources needed to solve a computing problem.  It's particularly useful in comparing various computing algorithms under consideration. Below is a table summarizing Big O functions. The four most commonly referenced and important to remember are:

  • O(1)              Constant access time such as the use of a hash table.
  • O(log n)        Logarithmic access time such as a binary search of a sorted table.
  • O(n)              Linear access time such as the search of an unsorted list.
  • O(n log(n))   Multiple of log(n) access time such as using Quicksort or Mergesort.

Sorting Algorithms

Before delving into the large variety of sorting algorithms, it's important to understand that there are simple ways to perform sorts in most programming languages. For example, in Java, the Collections class contains a sort method that can be implemented as simply as:

Collections.sort(list);

where list is an object such as an ArrayList. Some aspects of the Java sort() method to note are:

  • You can also use the Java Comparator class methods to implement your own list item comparison functions for specialized sorting order needs.
  • The Java Collections class (plural) is different than the Collection class (singular).
  • Which sorting algorithm (see below) is used in the Collections.sort() implementation depends on the implementation approach chosen by the Java language developers. You can find implementation notes for Java Collections.sort() here. It currently uses a modified merge sort that performs in the range of Big O O(n log(n)).

If you don't want to use a built-in sort function and you're going to implement your own sort function, there's a large list of sorting algorithms to choose from.  Factors to consider in choosing a sort algorithm include:

  • Speed of the algorithm for the best, average and worst sort times. Most algorithms have sort times characterized by Big O functions of O(n), O(n log(n)) or O(n^2).
  • The relative importance of the best, average and worst sort times for the sort application.
  • Memory required to perform the sort.
  • Type of data to be sorted (e.g., numbers, strings, documents).
  • The size of the data set to be sorted.
  • The need for sort stability (preserving the original order of duplicate items).
  • Distribution and uniformity of values to be sorted.
  • Complexity of the sort algorithm.

For a comparison of sorting algorithms based on these and other values see: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms.

Here's a quick reference for the major algorithms:

  • Exchange Sorts: based on swapping items
    • Bubble sort: for each pair of indices, swap the items if out of order, loop for items and list.
    • Cocktail sort: variation of bubble sort, passes alternately from top to bottom and bottom to top.
    • Comb sort: variation of bubble sort, selective swap of values
    • Gnome sort: also called the stupd sort, moves values back to just above a value less than it
    • Odd-even sort: developed originally for use with parallel processors, examines odd-even pairs and orders them, alternates pairs until list is ordered
    • Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Repeat. Often the method of choice. One of the fastest sort algorithms
  • Hybrid Sorts: mixture of sort techniques
    • Flashsort: Used on data sets with a known distribution, estimates used for where an element should be placed
    • Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
    • Timsort: adaptative algorithm derived from merge sort and insertion sort. 
  • Insertion sorts: builds the final sorted array one item at a time
    • Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
    • Library sort: like library shelves, space is created for new entries within groups such as first letters, space is removed at end of sort
    • Patience sorting: based on the solitaire card game, uses piles of "cards"
    • Shell sort: an attempt to improve insertion sort
    • Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list
    • Cycle sort: in-place with theoretically optimal number of writes
  • Merge sortstakes advantage of the ease of merging already sorted lists into a new sorted list
    • Merge sort: sort the first and second half of the list separately, then merge the sorted lists
    • Strand sort: repeatedly pulls sorted sublists out of the list to be sorted and merges them with the result array
  • Non-comparison sorts
    • Bead sort: can only be used on positive integers, performed using mechanics like beads on an abacus
    • Bucket sort: works by partitioning an array into a number of buckets, each bucket is then sorted individually using the best technique, the buckets are then merged
    • Burstsort: used for sorting strings, employs growable arrays
    • Counting sort: sorts a collection of objects according to keys that are small integers
    • Pigeonhole sort: suitable for sorting lists of elements where the number of elements and number of possible key values are approximately the same, uses auxiliary arrays for grouping values
    • Postman sort: variant of Bucket sort which takes advantage of hierarchical structure
    • Radix sort: sorts strings letter by letter
  • Selection sorts: in place comparison sorts
    • Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
    • Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
    • Smoothsort
  • Other
  • Unknown class

 

Android WebView Combines Native and HTML5 Code

A battle is raging over whether native mobile code apps, such as those for Android and iOS, are a better approach than using HTML5.  Each has its advantages.

There is, though, a way to blend the two in order to take advantages of the benefits each has to offer.  The graphic below shows the anatomy of an app that displays an HTML5 Canvas on an Android screen display.

This app is from the Learning Android App Programming video training course.

The HTML5 Canvas animation displayed is from HTML5 Canvas for Dummies.

You can see the HTML5 Canvas animation by clicking here. To see the JavaScript code that generates the animation, right click on the display page and select View Source Code.

Android/PHP/JQuery RESTful JSON MySQL Client-Server Overview

The title of this blog entry is quite a mouthful.  The purpose is to give a broad overview of the moving parts necessary to implement an application with client mobile and desktop devices that interact with a server database to alter and retrieve data.

I won't define all the classes, methods and acronyms on the graphic as they're easy to look up using an Internet search.  There are other choices that can be made for the details of the implementation, but this should provide a starting point for thinking through the necessary elements.

The communication vehicle for client-server interaction is typically the Internet Protocol Suite.

 

Creating a 3D Effect in 2D HTML5 Canvas Games

HTML5 Canvas doesn’t include a built-in 3D context. Without using an add-on product such as WebGL (www.khronos.org/webgl), 3D has to be simulated using the 2D context.

Some games require the sophistication of a true 3D engine like WebGL. However, many games built using the Canvas 2D context can be significantly enhanced by simulating aspects of 3D motion.

In the Ballpark sample game from HTML5 Canvas for Dummies, the thrown baseball is simulated moving away from the ball thrower toward the ball player along a simulated z axis third dimension. The z axis 3D effect is accomplished by decreasing the size of the baseball in proportion to it's movement upward along the 2D y axis.

You can play the game yourself by clicking here.  To see the full code, right click on the game web page and select View Page Source.

To simulate 3D movement using this technique, the following steps were used:

1.    Assign a z axis variable to each new object.

Along with the xPos and yPos variables, assign a zPos variable as in code section S2 assignments for baseballs:

     ball[b].zPos = zStart;

2.    As the object moves, update the z position.

In the sample game, in code section R8, the z position is calculated based  on the y axis position (yPos) and a z sizing factor (zSizeFact):

     var newZPos  = (ball[b].yPos/canvasBL.height) * zSizeFact;

     ball[b].zPos = newZPos;  

3.    Fix the z position under specified conditions.

In the sample game, the baseball is simulated to move along the z axis only away from the ball thrower. Also, to simplify the simulation, only movement up the y axis is used to increase z axis movement. So, when the ball starts to move down on the y axis, the z position is fixed. This code is in sections R9-R12:

     // FIX Z position of zFix is greater than zero.      

     if(ball[b].zFix > 0)  {ball[b].zPos = ball[b].zFix};

     // Z FIX check for not already set.

     if(ball[b].zFix == 0)

     {   // Z FIX conditions check. 

        var newYPos  = ball[b].yPos;

        if(((newYPos > curYPos) || (ball[b].bounce)) && (curYPos < zFixMaxY))

        {  // FIX Z POSITION at current level and no smaller than minSize.

           ball[b].zFix = Math.max((curYPos/canvasBL.height)*zSizeFact, minSize);   }   }

Using Randomized Variable Values to Enhance HTML5 Canvas Animations

The HTML5 Canvas feature is bringing additional animation power to web pages.  HTML5 Canvas allows web developers to embed sophisticated bit map animated graphics directly into web pages. 

In developing examples for my book on HTML5 Canvas (HTML5 Canvas for Dummies) I experimented with using randomized variable values to improve the realism of an animated fireworks display. I used random values within specified ranges for parameters such as fireworks colors, number of exploding particles, trajectory of particles, lifespan of particles and flight trajectories. I found that adding well constructed values (not too much or too little randomization) significantly increased the realism and appeal of the results.  Here's one example from the Fireworks app of setting a randomized value:

     part[newPart].life = lifeMin +(Math.random()*(lifeMax-lifeMin));

See what you think ... click here to see it in action.

HTML5 vs. Native App Development

As you're likely aware, there's a big debate going on about whether HTML5 web sites are a better platform for mobile apps than native code development using Android, iOS and Windows.

The main selling point for HTML5 is the write-once-run-anywhere advantage. Web browsers on mobile devices can access web sites from any mobile platform. HTML5 is providing features that allow web page JavaScript code to access phone features like devices sensors and geo positioning. In theory, a well constructed HTML5 web page will look and perform like a mobile device native code app.

However, currently not all device features are available to HTML5 JavaScript code and native code apps have a performance advantage over HTML5 web pages viewed using a browser. Native code apps are presently the dominant choice among developers.

In HTML5's corner, though, the technology is improving and web browsers are ramping up their implementation of HTML5 features. Life would certainly be simpler for mobile developers if they could develop for only one platform, HTML5, instead of multiple native platforms.

Longer term, HTML5 will certainly continue to get better. But so will native platforms. In fact, native platforms may improve more rapidly than HTML5. HTML5 is a global standard developed by the W3C. It takes years of effort to change the standard and have these changes adopted by the various browsers. The individual native platforms (Android, iOS, Windows) can change as quickly as their developers (Google, Apple and Microsoft) want them to. So will HTML5 ever catch up?

Maybe not. Google, Apple and Microsoft have lots of developers and big budgets. They want their products to be competitive ... and that means constant improvements.

So, what's likely to happen? In my opinion, we'll have a blend of the two. In fact, this is taking place today. Native code platforms have Application Programming Interfaces (APIs) that support displaying web pages from within native code apps. Developers can use native code for what it does best and HTML5 web pages for what they do best. The exact mix will shift over time as all the platforms change and improve. 

For developers, this means that separate native code platforms will likely continue to exist. Write-once-run-anywhere will remain an elusive goal probably not realized for a long time, if ever. This doesn't mean that development costs can't be managed or reduced. HTML5 web pages can be developed and used by native code apps where appropriate. Functions specific to those pages can be write-once-run-anywhere. This may not be an optimal solution, but it's the game on the ground.

Smartphone Website with Laptop 2.png

WebPlatform.org: A Resource for Web Development

WebPlatform.org is a new organization and collection of websites that will provide open source resources for web development. It will cover topics such as HTML5, Canvas, SVG, Video, Animations, IndexedDB, CSS, WebGL, Transforms, Audio, Media Queries and FileAPI.

Which is the Best Browser

An analysis of Internet browsers by Top Ten Reviews places Google Chrome at the head of the list. The analysis shows, however, that it's a real horse race between the top five: Chrome, Firefox, Internet Explorer, Opera and Safari. Here are some of my observations based on this analysis and personal tests and experience:

Change after new releases: All of the browser developers are working hard to improve their products. With each new browser version release, the competitive landscape can change. For example, Internet Explorer had recently lagged in speed due to the lack of graphics hardware acceleration. Based on my tests, they're now the fastest running HTML5 Canvas animations.

Graphics hardware acceleration: GPU (Graphics Processing Unit) hardware acceleration is an important factor in browser speed. A browser displaying video or animation with GPU acceleration will outperform a browser without it by a factor of 3-4. That's right, 300-400%. A computer using just the CPU to manipulate graphics displays simply can't keep up with one using the combination of CPU and GPU. Hardware acceleration is a fairly complex topic. Basically, the browser offloads calculations from the CPU to the GPU. If you're interesting in some of the details, take a look at this discussion of hardware acceleration from the Chromium Projects.

Mobile lags desktop: Especially in speed, the mobile browsers lag desktop versions. Mobile devices simply don't have the computing power to match desktop devices. 

HTML5 Status

Transient

The World Wide Web Consortium (W3C) has announced that a final recommendation for HTML 5.0 will be released in the 4th quarter of 2014. In spite of the "recommendation" terminology that W3C uses, this is official release of HTML5. This is a big deal and great news. Browser developers will have a firm definition of HTML5 they can use to bring their products up to a complete level of support for this latest version of HTML.

W3C has also defined the follow-on version, HTML 5.1, to be released in the 4th quarter of 2016. This release will include features that have been pushed out in order to get release 5.0 completed in 2014. Without this stragegy, W3C was looking at an indefinite specification development timeframe. 

Browser developers are not waiting for 2014 to begin implementation of HTML5. You can use www.html5test.com to check the status of your browser to see which features are supported and www.caniuse.com for a summary of the status of support by all the major browsers.

What is HTML5 Canvas?

HTML5 Logo.png

The Canvas feature of HTML5 is one of the most exciting new developments in web based capabilities in many years. Here are some key aspects:

HTML5 - Canvas is a part of the latest revision and improvement of the previous version (HTML4, released in the late 1990's) markup language for displaying web pages on the Internet.

Canvas Tag - The <canvas> tag joins the other HTML tags (there are around 100 now) as a way to include single or multiple Canvas areas on a web  page. 

Bit Map DisplayThe Canvas area you define with a <canvas> tag is a bit map display. You can manipulate individual pixels to draw objects, images, animations and video.

JavaScript ControlThe JavaScript language is used to control what is seen on the Canvas. The JavaScript application code is placed between the <head></head> and <script></script> tags of the web page.

Browser Based - The computing needed to create a Canvas display is done within the browser. In other words, it's client based, not server based. The means that creating a Canvas application is simpler than one requiring server based programming. It also means that the computing power needed to generate the Canvas display is not concentrated in single servers. Each user's browser handles its own work.

Animation - Canvas applications can generate animations. This is accomplished using callbacks from the browser. The Canvas application designates one of its functions to be called from the browser at specified time intervals. During each of these callbacks, the application draws a new Canvas display, moving objects slightly. When viewed as a continuous flow of Canvas displays, an animation is generated.

Audio/Video - Audio and video can be incorporated into your Canvas applications. Moving objects can create sounds and video images can be melded into other application objects. This is done without the use of any audio or video plugins.

Gaming - Game developers have all to tools necessary to create compelling HTML5 Canvas games.

Fun - Putting aside the technical aspects of Canvas ... it can be described as just plain fun. An HTML5 Canvas is a place where as a developer you can express your creative energies and as a user you can have expanded and enjoyable experiences.

For a more details look at HTML5 Canvas, watch for my upcoming book: HTML5 Canvas for Dummies.

Integrating Audio with HTML5 Canvas

One of the useful features of HTML5 Canvas is the ability to integrate audio, either with or without an audio player. Click here or on the image to see if it works on your browser ... click on my dog Daisy and/or the pelican to test simultaneous sounds.

When the new browser window opens, you can view the page source to see the code that generates the Canvas display.

This is one of the sample applications from HTML5 Canvas for Dummies.

HTML5 Canvas Performance Test

Browser support for HTML5 Canvas is constantly improving. More features are being supported and performance is improving. Click here or on the image below to see how your browser performs. The app rotates a ten layer gradient and displays the Frame Rate.

HTML5 Canvas on a Smartphone

HTML5 Canvas is a highly anticipated feature that allows web developers to create sophisticated graphics on their website pages. Most desktop and laptop browsers now support the Canvas feature. Mobile browsers are catching up. To see if your browser supports Canvas, you can access www.html5test.com for an analysis and rating of your browser.  Also, give this Canvas app a try: