Machine Learning Mathematics

Machine Learning Mathematics

Mathematics is the study of topics such as quantity, structure, space and change. Mathematics provides a means to represent the real world in the form of numbers, relationships and equations.

Machine learning employs a wide variety of mathematical concepts and functions in order to create processes that:

  • analyze vast amounts of data in workable timeframes
  • discover actions, relationships and forces occurring in nature 
  • model the real world
  • interact with the real world

In short, mathematics is the base methodology employed to create machine learning modelsthat are used to address challenging applications such as image recognition, face recognition, natural language processing and pattern recognition: 

Mathematics -> Models -> Applications

Read More

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

 

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 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.

Object Oriented Programming Design Patterns

OOP Design Patterns are development templates that give software designers and coders shorthand ways of thinking about and solving programming challenges.

A full explanation of OOP Design Patterns can (and does) fill entire textbooks. Understanding and remembering every aspect of every pattern can be a daunting task. Hopefully the brief descriptions below will help in remembering the function of some common Design Patterns.

Often programmers need to discuss pattern usage with software designers, managers and other programmers. Getting too lost in the details can distract from communicating the essence of a software solution. Design Patterns can help with these challenges.

Some commonly used Design Patterns are listed below. Click on the Design Pattern name for a full pattern description.

  • Adapter - Facilitates object interaction.
  • Bridge - Similar to the Adapter pattern but more robust.
  • Builder - Similar to the Factory pattern for returning objects as an output but used in cases where many variables of output object construction are needed.
  • Chain of Responsibility - Uses a sequence of processing code blocks, each of which handles a specific set of conditions before passing control to the next block.
  • Command - Used to store and use the information needed to call a method at a later time.
  • Composite - Describes that a group of objects is to be treated in the same way as a single instance of an object.
  • Decorator - Also known as a wrapper, allows behavior to be added to an individual object.
  • Facade - Provides a simplified interface to a larger body of code.
  • Factory - Creates objects as a return output.
  • Flyweight - Minimizes memory use by sharing as much data as possible with other objects.
  • Interpreter - Specifies how to evaluate sentences in a language.
  • Iterator - Used to traverse a container and access the container's elements.
  • Mediator - Defines an object the encapsulates how a set of objects interact. Instead of communicating directly, the encapsulated objects communicate through the Mediator.
  • Memento - Provides the ability to restore an object to its previous state, such as an undo via a rollback.
  • Null Object - Object with defined neutral ("null") behavior.
  • Object Pool - Set of initialized objects kept ready to use, rather than allocating and destroying them on demand. Thread Pools are a common Object Pool implementation.
  • Observer - Maintains a list of other objects and notifies them of any state change. Objects that perform Callbacks operate as an observer.
  • Prototype - Similar to the Factory pattern, creates objects based on prototypical instances.
  • Proxy - Functions as an interface to something else.
  • Singleton - Restricts the instantiation of a class to one object.
  • Strategy - Enables an algorithm's behavior to be selected at runtime.
  • Template - Defines the program skeleton of an algorithm and defers some steps to subclasses.
  • Visitor - Separates an algorithm from the objects on which it operates.

Marketing and Technology ... Not So Far Apart Any More

Certainly traditional media such as newspapers, TV, radio and magazines are still very important to marketing products and services. But the newer, high tech, internet driven media and tools are playing an ever increasing role. Consider:

And the list goes on. Some long for the 'good old days' as portrayed in the popular TV series Mad Men. Come up with a great angle on a product, buy a lot of space in paper media and watch the sales roll in. Technology was left up to the back room gnomes who would calculate results and play with budgets.

Today, technology is center stage in most marketing campaigns. There are, of course, challenges in the marriage of the two domains. Consider this list:

  • Finding the right balance between the new and the traditional.
  • Knowing how far to go with technology. Just like traditional media, it can get expensive.
  • Getting the traditional media folks to interact with the new media folks.
  • Not forgetting the importance of branding, positioning, images and other 'soft' elements when dealing with 'hard' technology.

So, how to deal with all this? Some thoughts:

  • Technology can be applied incrementally. Small scale at first to judge results, then a broader roll out.
  • Technology can provide a lot of detail about results and how it is working. It can be much more transparent than traditional media if reported correctly.
  • Technology can provide two way dialogues with the audience. This can be informative and allow adjustments as time passes.

A good example showing that today's audiences want both old and new media is the YouTube phenomenon. People like watching moving images. It's been around for 100 years. YouTube provides audiences a new element of control and interaction that enhances their experience.

Find ways to marry the two like that, and you're on your way to success. 

How Many Smartphone App Clicks is Too Many?

At what point will the user of a smartphone app just give up and move on to the next app? It's an important question for app developers. 
 
Although it's difficult to come up with an exact answer, we can understand at least something about the factors involved and how we might improve that chances that an app user will have a satisfying, non-frustrating experience.
 

First, there are factors that are out of the control of the developer:
  
Situational Pressure.
Smartphones are generally used in a higher pressure environment than is the case with a PC. People are one the move, busy and anxious to get results as fast as possible.
 
Information Needs.
How badly the user needs the information provided by an app will be highly variable. If they're late for a meeting and need a phone number or address quickly, user tolerence for clicking through multiple screens and waiting through delays in displays will be quite low.
 
App Knowledge.
All app developers would like users to take the time to completely understand every aspect of how to use their app. This usually is not the case. Users learn only the minimum they need and want apps to respond quickly.
 
Given this challenging environment, app developers need to focus on what they can control to make an app as usable as possible:
 
Design.
Apps need to be understood quickly and easily. Navigation, layout, colors, text, images, buttons ... all the elements of design play a role in creating a good user experience.
 
Information Load.
Is the user presented with just the right amount of information necessary to get the job done? Too much or too little can lead to an unsatisfactory experience and poor app ratings.
 
Click Sequences.
Can the user get to what they need directly? Having to click through long sequences of screens can frustrate users. People are impatient. 
 
In summary, app developers need to focus on what they can control and not assume favorable conditions for those factors that are out of their control.

Ranking Sticky Apps

Apple and Google are changing the way they rank apps in their markets. Although the exact formulas are kept secret, there is talk and news that they are moving away from basing rankings on downloads and now using a formula based on the "sticky-ness" of apps.

The sticky formula is based on the ratio daily active users to monthly active users. So just getting users to download an app no longer gets a high rating. Users need to actually use an app to move it up in the ratings. Seems to make sense. After all, they are called "users" not "downloaders." 

Internet Advertising Revenues Show Strong Growth

PricewaterhouseCoopers released their Internet Advertising Revenue Report for 2010 (http://www.iab.net/media/file/IAB_Full_year_2010_0413_Final.pdf).
Growth is strong at 15 percent year over year.
 
From the report:
 
"Internet advertising revenues in the U.S. totaled $7.45 billion in the fourth quarter of 2010, an increase of 15 percent from the 2010 third quarter total of $6.46 billion, and an increase of 19 percent from the 2009 fourth quarter total of $6.26 billion. 2010 full year Internet advertising revenues totaled $26.0 billion, up 15 percent from the $22.7 billion reported in 2009. Internet advertising revenues in the U.S. totaled$7.45 billion in the fourth quarter of 2010, an increase of 15 percent from the 2010 third quarter total of $6.46 billion, and an increase of 19 percent from the 2009 fourth quarter total of $6.26 billion. 2010 full year Internet advertising revenues totaled $26.0billion, up 15 percent from the $22.7 billion reported in 2009."
 
You can view a webinar on the report here: view the webinar 

Eye Tracking and Heat Maps

Eye tracking has become a hot topic in the last few years. Eye tracking devices are used to create heat maps showing where attention is focused on display pages. A sample heat map of a Google search results is shown below:

A dominant pattern for search engine results is the "F" pattern showing the eye being drawn to the upper left and then moving down and across from there. There are, however, factors (such as the inclusion of images, graphics, and additional columns) that can significantly alter this pattern. This is shown in the sample YouTube pages below:

You can do a Google Images search of "eye tracking" to see sample heat maps. Having a basic understanding of how people focus their attention on internet sites is important for improving traffic and conversions. Heat maps of specific sites can help to further improve results.