as mentioned in the interview, even though deep learning can be used to classify the objects in some images, a method has not yet been found to enable computers to establish the full relation between objects. computers can also not fully comprehend the use of objects. for example, humans can easily find a place to sit even though there might not be traditional chairs in most situations. computers, however, find this considerably more difficult. (there has been some research into this, such as the article “what makes a chair a chair?” by h. grabner, j. gall and l. van gool)

what we often don’t consider is how the human brain is trained to interpret what is seen. even something as simple as recognising objects in a 2d image seems to be a learnt skill. in other words, even if we knew what objects looked like, and could recognise them all around us, the ability to recognise them on a photo seems to be a learnt skill. this is the conclusion that the author of “smart moves”, dr c. hannaford, a neurophysiologist and educator, has come to. in her book, she explains how she had visited a tribe that had never before been exposed to 2d images. when showing them pictures of a mountain range, they were completely unable to ‘see’ the mountain range (even though they were very familiar with mountain ranges). how their brains process visual information was not adapted to recognising objects in a 2d picture.  just as gestalt theory also reveals, therefore, what we see is not necessarily what is present.

an example of this is the blue-black vs white-gold dress that made its rounds on social media ‘recently’, and can be seen in figure 1.

figure 1

not everyone sees this dress the same. some people immediately see it as a black-blue dress, whilst others see it as a white-gold dress. in essence, taken from this article that explains it in detail, what happens is that the sharp outside light may cause your brain to think that you are looking at the shadowed version of the dress, and so compensates, and you see a white-gold dress. however, when people see it as a black-blue dress, the brain realises that the dress itself is also well-lit, and that the bright light isn’t to be taken into account when looking at the dress itself.

from this can be seen that our brains consider the surrounds when processing colour. whether that surrounds is something specific as the actual colour that surrounds the one in question, or whether it is from more of an idea such as a light-source or shadow.

consider the objects in figure 2.

figure 2

it appears in figure 2 as if the middle rectangle in the bigger rectangles are different colours. however, they are actually the same colour, as can be seen in figure 3. this effect is known as simultaneous contrast, and refers to how colours from different objects affect each other .

figure 3

the simultaneous contrast effect is most intense when the colours that interact with each other are complementary colours. complementary colours are the colours that are directly opposite one another on the colour wheel (as shown in figure 4).

figure 4

this effect, together with colour theory and the colour wheel is used in many different applications. obvious places where it is used is in areas such as art, logo design and in the design of websites. a less obvious place it is used in is in choosing the colour of life rafts. as can be seen in the colour wheel in figure 4, orange is the complementary colour to blue. as the oceans appear blue in general, life rafts’ colour has been chosen to be orange, since it is the colour that will stand out the most on blue.

as mentioned before, the idea of a shadow can also have an effect on how we perceive colours. as an example of this, consider the images in figure 5.

figure 5

in the image to the left, it appears as if the blocks labelled ‘a’ and ‘b’ are of different colours. however, in the image to the right, it can be seen that the two blocks are actually the same colour. part of the reason for this ‘trick’ is due to our brains seeing the shadow thrown by the green cylinder and in so doing, adapting our perception of the colour of block ‘b’. for the full reasoning behind this example, see this article.

the human brain is a complex system with extremely complex interactions. above are some simple examples of how our brains adapt to the information that is perceived. it is also adaptions like these that makes teaching a computer to gather the same information from of a scene as a human, more difficult.

For my Honours research project this year, I analysed ways of increasing user participation in blog-based social networks. My case study was Bonfiire, a multi-community network for discussion and debate, that I co-founded with a friend in 2012. Since the public launch of Bonfiire Stellenbosch (our first community, targeted at Stellenbosch University students and alumni) in January 2013, we’ve seen the platform evolve into a vibrant virtual space for the discussion of campus issues. In my research project, I focused specifically on modelling Bonfiire using a system dynamics approach. However, along the way, I’ve stumbled across a number of interesting phenomena that I am very curious to examine further.

One of the things I’ve been wanting to do, is to use text mining to gain insight into the focus and nature of discussion on Bonfiire, as well as the way in which users express themselves. In recent years, there has been a growing interest in large-scale text mining as a means to gaining rich insights from unstructured (i.e. natural language) data sources. Bonfiire presents an interesting case in this regard, because blog posts by users are long (usually three to six paragraphs) and rich (packed with the writer’s sentiment towards and opinion on specific topics).

In this blog post, I’m going to use rudimentary text mining to answer the question: What were the main discussion topics in the months that saw the highest frequency of ‘othering’ words (“they”, “their”, “them”)? The time frame will be January 2013 to October 2014.

The concept of ‘othering’, and measuring it in Bonfiire blog posts

In Wiktionary’s definition, ‘othering’ refers to “the process of perceiving or portraying someone or something as fundamentally different or alien”. ‘Othering’ focuses on emphasising how one, or one’s group, differs from others, through using exclusionary language (“our culture”, “we condone such practices”, “they reject our idea”, “the leader is one of them”) and, in a broader sense, implicitly identifying the ‘other’ in a negative light. This article describes the language of ‘othering’ in greater detail.

Arguably the most rudimentary level at which ‘the other’ is indicated in the English language, is through the use of the words “they”, “their” and “them”, referring to out-groups in the third person. These words can easily be mined in large heaps of text. That is precisely what I intend to do, to measure to what an extent a post may be said to use ‘othering’ language. (Of course, my approach has a number of important limitations. Fear not; I discuss these later on.)

In this post I will focus on forecasting from data which is referred to as Time series data. Time series is data that changes over time and is captured in (time, value) or (x, y) pairs with x being time. Examples of time series data include stock prices, yearly rainfall, inflation, profits, etc. The area I am interested  in is the load on a server in the cloud.

Classical Machine Learning

Before explaining how to predict on time series, let us first discuss machine learning. Classical machine learning aims to classify data into a categories termed classes. A well known case is one where we have data points collected from flowers that belong to the Iris family (either Setosa, Virginica or Versicolor). For each flower sample the following was measured: the length and width of the sepals and petals and these four measurements form what machine learning refers to as features. Using these features we train a classifier (a mathematical model) with some of the data collected, in each training case telling the model what species the particular sample belongs to (also called a label). After the classifier-model has been taught, it is tested by presenting a new sample with the label unknown and makes a prediction on which species the new sample belongs. This is called statistical classification with supervised learning and you can find more information here.

Time series

Classical machine learning uses features, like the petal and sepal lengths of flowers or the symptoms presented by a patient or elements in a wine in order to make some decision on a new sample. In contrast time series do not contain a collection of features, but rather a value at each time step. Time series prediction assumes that the future depends on the past and using this assumption it views each time step back; x[t-1], x[t-2], … as features. Time series typically also has one or more of the following characteristics; is contains randomness, follows a trend and has seasonal and/or cyclical behaviour. Predicting or forecasting a value (or set of values) into the future is the ‘decision’ the machine learning model must make. The question now is how do one approach a time series predication problem?

Steps in forecasting

The following is the generic steps in forecasting time series:

1. Define the problem to be solved. It is vital to consider of the what the end result of the forecast will be and how the forecast result will be used.
2. Gather data. The saying is “There is no data like more data”, more data enables better training, testing and validation.
3. Explore your data. Use statistical tools to plot different information plots and determine the characteristics of your data; does it contain patterns, is it too random or does it follow a trend.
4. Choose models and fit them. This can be simple models such as using the mean of past data-points or complex approaches such as Neural networks. I will give a brief overview of models currently applied to time series, below.
5. Evaluate your model accuracy. This entails measuring error metrics and optimising model parameters.

I will now discuss steps 3-5 in more depth. Step 1 and 2 are straightforward and depends one the specific problem you are facing.

3. Explore your data: Exploratory Data Analysis aims to  give insight into the data, discovering the structure, behaviour, patterns, outliers and other information to help with choosing a forecasting model. A key assumption of time series prediction is that the data is Stationary. A Stationary process’s joint probability distribution does not change over time (read more here). Tools to determine stationarity include calculating the Auto-correlation of the data or using the Augmented Dickey–Fuller test. Another important characteristic of your data to explore is to determine if the data follows a trend or contains a seasonal behaviour. Some model are not capable of accurately predicting on data which contains a trend or periodic pattern and thus one will typically remove these behaviour through transforming the data (ie. using FFT or first order differencing).

4. Choose and fit models: The simplest ‘model’ is calculating a mean over the past few samples and using this as a prediction. One step up is to plot a Histogram of your data and use the average of the samples in the most significant bin (the bin in which the majority of samples fall). Moving Average (MA) models calculates a average of the samples in a sliding window over time, with Exponential Smoothing weighting each lagged sample exponentially less. Auto-Regressive (AR) models aims to fit a function f(t) to a prediction y(t) = f(t) + e, where e captures the random error in the data. Combining MA and AR models give ARMA(p,q) models with order (p,q) defining the order of AR(p) and MA(q) respectively.

More advanced models include Markov chains and Neural networks. The idea is that one can discriminate a time series’ values into M bins, which then denotes M states and using a Markov model, predict the probability of transitioning from one state to another for each time step. Neural network aim to learn patterns from past values and predict a new value or a probability distribution for a set of values into the future. Other advanced methods include combining different models or vectorising a collection of time series data in order to improve model accuracy.

5. Model Evaluation: After fitting a model and forecasting some values, it is vital to be able to measure the accuracy of both the model and the predictions. The typical metric to use is to calculate the Root Mean Squared of the Error (RMSE) also referred to as the Root Mean Squared Deviation (RMSD); calculated by : With  being the predicted value and  the actual value at time t. More information on error metrics can be found here.

Conclusion

The future is still uncertain, but using Forecasting models in machine learning, I conjured some ‘magic’ to enable us to predict the future. This blog post briefly covered classical machine learning, namely classification with supervised learning and the focus was on the steps to take when forecasting on time series data. I discussed the popular models currently being applied to time series and also mentioned advanced approaches using Markov models or Neural networks.

Useful resources

• Online statistics e-book: Forecasting: principles and practice
• Engineering Statistical handbook: NIST/SEMATECH e-Handbook of Statistical Methods
• Python Machine learning library: Scikit-learn

I’m a person that loves coming up with new ideas. My friends and family know this all too well. From drive-through grocery shops to fully automated peer-to-peer community courier services. Doesn’t matter how absurd, I just like new ideas.

The problem is implementing these ideas. They usually cost a lot of money and take a lot of time to build. That means you probably have to stop what you are doing and try to realise your idea. You will probably require some funding from investors. Unfortanately, the odds of your idea taking off is very small. If it fails, a lot of time and money will have been wasted.

Thats why I started web development. If you have some idea for a cool website or service, development of a basic protoype can be done relatively quickly and inexpensively. You can build a word game, a braai app or even a new social media app. Whatever you can think of.

You can test the viability of your idea and if it fails, you won’t owe anyone a lot of money and you can try again on a new idea. You are also not limited to focussing on one idea at a time. You can try many ideas in parallel, especially since you can reuse a lot that you learn in one idea in another.

Starting with web development

Starting with web development can be a daunting task. The biggest issue I faced is “where do I begin?”. There are so many tools available. HTML, CSS, JavaScript, PHP, Python, Ruby and MySQL are just some of the phrases you will come upon. But which of these do you need?

The first thing I started to learn was basic HTML. It is easy enough to use, but you soon find that your site looks like it was made in 1991 by a 10 year old. Thats when I started learning CSS. Suddenly, the website looked a lot prettier. After everything looked pretty, I realised my website doesn’t do anything. It’s called a static website. Its usually used to give information and is not used for interacting with users.

I realised I needed a backend scripting language in my arsenal. I decided to learn PHP, probably because Facebook uses it. Along with PHP, I learned to use MySQL databases. As soon as I got the hang of HTML, CSS, PHP and MySQL, I was at a point where I could start building primitive sites.
The biggest problem I ran into is that all of these tools are used together, so you need a basic knowledge of all of them to actually start using them.

Humble beginnings

My first real site was www.helpacar.com, a service where you alert people anonymously that their car’s lights are left on. The site doesn’t look great, but it works.

For a long time, I continued developing sites like these. They were all functional, but didn’t feel like the other sites on the Internet. Something was still missing.

The missing link

Not having to reload your entire page when you click on a button. That is what was missing. AJAX is what I had to learn next, which meant I had to learn JavaScript first. After getting AJAX requests working in pure JavaScript, I learned of a library called jQuery that made everything a lot easier. jQuery lets you accomplish a lot more in less code. Thats where I learned a valuable lesson: Don’t do everything from scratch. It is a lesson that I am still learning to this day. I am still doing many of my development in pure php, even though there are good frameworks available. Getting to learn a framework takes more time in the beginning, but it definately pays of in the long run.

Another nice framework that I learned to use is Twitter’s Bootstrap, an amazing and free frontend CSS framework that is used by countless websites.

Tools you will need

Firstly, you will need a place to host your website. To get started, you can host your site on your own computer. You will need to install webserver software. I would recommend installing XAMPP. XAMPP stands for cross-platform Apache MySQL PHP Perl. It can be installed on Windows, Mac and Linux. After you have made your site, you can move it to a hosting provider and host it online.

There are many, many tutorials available on the Internet to teach you web development. It’s the Internet teaching the Internet how do program for the Internet. Guides and tutorials are great. However, I feel the best way to learn is to get a small project and try to make it work. By struggling and figuring it out, you learn a lot more than from a tutorial.

One of the most useful sites that I use on a daily basis is w3schools.com. It has references and guides for almost everything you will need.

The last tool you will need is your imagination. Be creative.

Try new things and make the Internet a better place.

Apache Maven

What is Apache Maven?

Apache Maven is a very powerful and useful tool for Java programmers. Its main feature is automatic dependency resolution, but it is also very customizable to include Java build options, JUnit testing and Javadoc generation.

Installing Apache Maven

Download the appropriate Apache Maven archive: apache-maven-3.2.3-bin.tar.gz for OSX/Unix or apache-maven-3.2.3-bin.zip for Windows from Here. Untar/Unzip and follow the instructions README.txt, included in the archive. More instructions available here

Using Maven from commandline

The default build script for an Apache Maven can be generated by using the following command on commandline:

mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false

This will create a new Maven project in the current directory called myapp. Calling mvn clean install from the commandline will build the App.java source, which represents the “Hello World” of Maven projects. Run “Hello World” with java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App

For more advanced projects, it is important to understand the principles of how Maven works before attempting to change the generated pom.xml to include more dependencies and build options. Maven processes Java source in different life-cycle phases called goalds. According to Maven in 5 minutes:

Although hardly a comprehensive list, these are the most common default lifecycle phases executed.

• validate: validate the project is correct and all necessary information is available
• compile: compile the source code of the project
• test: test the compiled source code using a suitable unit testing framework. These tests should not require the code be packaged or deployed
• package: take the compiled code and package it in its distributable format, such as a JAR.
• integration-test: process and deploy the package if necessary into an environment where integration tests can be run
• verify: run any checks to verify the package is valid and meets quality criteria
• install: install the package into the local repository, for use as a dependency in other projects locally
• deploy: done in an integration or release environment, copies the final package to the remote repository for sharing with other developers and projects.

There are two other Maven lifecycles of note beyond the default list above. They are

• clean: cleans up artifacts created by prior builds

• site: generates site documentation for this project

These life-cycle goals are specified in the pom.xml. Most of these life-cycle goals are included by default, but every goal can be customized to use specific settings. More information at Maven Getting Started

The dependecy resolution part of Maven is specified by the <dependency> tags in the XML. For example, including JUnit testing in the build (included by default, but specific versions can be specified), use the following code:

<dependencies>
  <dependency>
    <groupId>junit</groupId>
    <artifactId>junit</artifactId>
    <version>3.8.1</version>
    <scope>test</scope>
  </dependency>
</dependencies>

Check the Maven Repository for more plugins.

Using Maven in Eclipse

Apache Maven can also be used with Eclipse. To install follow these steps:

• Download the latest Eclipse
• In Eclipse: Help->Install New Software: Enter http://download.eclipse.org/technology/m2e/releases
• Create a Maven Project

The pom.xml file can be edited in Eclipse, and the different life-cycle goals can be set as Build configurations. For a quick start, use clean install, which will clean, compile, test and package the project.

Maven Wrap-Up

There are many other settings and configurations available with Maven, but would be too long and complicated to explain here. Check the official Apache Maven site for more details.

Web Hosting Services

Various websites offer free or trail period Web Hosting Services, and this section is dedicated draw a comparison between the options. However, this post will focus on the lightweight and easy to setup websites, and not a production ready, heavy duty hosting solutions.

FreeHostingNoAds.net

The first hosting solution is completely free, but with some restrictions. According to the website, here is the list:

• 20GB of Storage
• 200GB of Traffic to and from your site per month
• Free subdomain @t15.org
• 3 versions of PHP available, MySQL, FTP, POP3 Email, SSH Console
• Free subdomain @t15.org
• Free website builder

However, what is not included in this list is the restriction on file creation. This poses a problem for PHP scripts that create a local cache, such as Google+ Sign-in. Also, it has a 30-day inactivity shut-down. If there was no activity, the site is suspended. However, for most other applications, this lightweight solution is adequate. Usage is as simple as uploading the PHP files to the public_html folder using FileZilla or other ftp client.

Amazon Web Services

Although not free, Amazon Web Services(AWS) provides a limited Infrastructure-as-a-Service(IaaS), that is virtual machines in the cloud, for a 1-year trail period. This free Service provides the following resources:

• 750 hours of computational usage / up-time per year
• 750 hours of relational database use, 20GB of database storage
• 30GB of general storage
• Linux and Windows Server images available
• Read/write access according to Linux or Windows defaults
• 15GB of total out-bound data transfer for the 12 month period
• Free trail period to 12 month period, can continue at $0.013 per hour for a micro instance after 12 month period.

This offering is limited, but could be used for a basic prototyping of a website. If more computing power is required, it can be easily added on at relatively good pricing. For a basic web server setup, follow this tutorial

Google App Engine

Google App Engine is a Platform-as-a-Service(PaaS) which not only hosts websites, but can also host executables written in Java, Python and Go.

There are various limits on the free service:

• 5GB of general storage
• 28 instance hours per day (Auto-scaling)
• 100 E-mails per day
• 1GB of outgoing bandwidth per day
• CloudSQL not included, basic package costs $0.36 per day for 0.5GB of database storage

Check this link for more information on deployment of an app.

Webhosting Wrap-up

In comparison: FreeHostingNoAds.net provides easy-to-use and free hosting, but with file write restrictions. Both Amazon and Google App Engine have stronger storage restrictions, but more flexibility. Google App Engine also provides auto-scaling of instances to accommodate larger peak loads.

Thank you for reading this blogpost, hope it helps!

My research primarily focuses on optimizing simulations based on cellular automata, and in order to do so, I’ve been utilizing NVIDIA GPUs. I started off using a laptop with a mobile-series GPU. What I did not know at the time of purchase was that Intel and NVIDIA had devised a strategy to save battery life. This strategy is known as Optimus, and essentially what it entails is that the more battery-intensive GPU is only utilized for heavy graphical processing and other forms of rendering. General usage reverts back to using the built-in CPU graphics processor which is less battery intensive. Although this strategy works perfectly fine (as far as I know) on Windows OSs, it does not really work all that well on Ubuntu. First off, if you decide to boot directly into Ubuntu when switching on the laptop, Ubuntu cannot establish proper low-end communication with the battery checker, and a strange glitch tends to occur 90% of the time… The GPU fan will spin at full speed, Ubuntu does not know how much battery life the laptop has left, and whether the laptop is plugged-in or not. The battery indicator LED will also constantly flash.

I did quite some research on this issue, and found two solutions. The one solution (tested by other people across the planet with the same problem as I had) installed an Optimus driver simulator (specifically developed for Ubuntu 12.04+), known as Bumblebee. However, when I discovered Bumblebee, it was still in its infancy and there were still a lot of issues reported, especially with later model GPUs, like the one I have.
The other solution (which I stuck to) is a lot more simple, and it involves first booting into Windows, with the laptop not plugged-in, using a bit of battery, and then restarting and logging into Ubuntu. Luckily, I replaced the stock hard-drive with a solid-state hard-drive to speed-up boot-up times.

When I started learning CUDA later last year, I eventually had to get the GPU working, which meant that I would have to try and install drivers for the GPU. But this meant that I might have to try and install Bumblebee, because at that time I thought that I’d be using the GPU as the primary rendering device. How fortunate I was that this process of getting the GPU to ‘work’ did not require me to hack the system. After I installed CUDA, Ubuntu was able to communicate with the GPU and send it request to perform work, without me having to use it as the primary rendering device.

Thus, I was able to learn and apply CUDA for my research. The GPU in my laptop is pretty much just a chunk of supercomputing power when I’m logged in on Ubuntu. But, it gets the job done.

More recently I decided to get a desktop system, with a desktop GPU (which are more powerful than their mobile counterparts), so that I can generate more data for my thesis. After acquiring the desktop system, the whole process of installing Ubuntu and installing GPU drivers had to be performed again. This time around I wasn’t really bothered (at first) since I wasn’t dealing with a system that uses Optimus. However, getting the GPU to work as I first intended it to do, turned out to be quite difficult…

The plan was to install the drivers and then use the GPU as the primary rendering device (and not the on-board GPU). Unfortunately, the driver that accompanies the latest release of CUDA doesn’t properly support the GPU that I decided to get, as well as the latest release of Ubuntu. It does allow me to communicate with the GPU, but NVIDIA X-Server does not start properly and thus the GPU cannot be used as the primary rendering device. So I had to revert to using the on-board GPU to display the goods. After a couple of days of persistence I did manage to set up a proper working environment.

So what I’ve learned over the last year or so is that, if you are interested in this line of research, i.e. using GPUs for general computation, make sure that the hardware you have at your disposal can be used as you have intended. If you are planning on purchasing new hardware, make sure that the operating system you intend to use, does have support for all of the hardware (yes you: graphics and networking) or that there are proper ways to getting your hardware to work. In terms of using something like CUDA, make sure that you are installing it on a supported operating system. And as far as you can, FOLLOW OFFICIAL INSTRUCTIONS when installing drivers and software on operating systems such as Ubuntu (and other Linux based operating systems). Finally, be persistent; that is what helped me to set up my working environment.

This problem is do to the fact that sound effects are mostly produced by playing sound waves from storage. A possible alternative to this approach is to use sound synthesis for some action sounds. This will enable more variety in sound effects, and will also save storage space — which may be especially useful in a mobile setting. This was indeed the method employed on the early game consoles, when the sound chip consisted of nothing more than 3 tone generators and a noise generator. Some people may be concerned about the artificial nature of synthesized audio for sound effects, but it is important to remember that many sounds in both games and movies are already artificial. The classical “dish!” sound often employed during fist fights is one example. As any one who has ever witnessed a bar fight can attest, fists don’t sound that way in real life. This sound was traditionally produced by hitting the end of an empty toilet roll close to a microphone.

There exist a number of sound synthesis methods, each with it’s strengths and weaknesses. Additive sound synthesis works by the principal that all periodical wave forms can be produced by adding sine waves of different frequency’s and amplitudes together. This proved to be time consuming to do with hardware synthesizers, and hence this synthesis method went out of favor. This is however becoming more popular again as it is easy to do in code. A program demonstrating this synthesis method is Spear (www.klingbeil.com/spear/). Frequency modulation synthesis (FM synthesis) is another synthesis method that is similar to FM radio in principal. The most basic setup involves a carrier sine wave with a frequency determined by the amplitude of another sine wave called the modulator. More complex setups involve different wave shapes, or modulators chained together. FM synthesis can be used to create approximations of existing sounds and was used extensively in MIDI synthesis chips of early cellphones. Subtractive synthesis is yet another synthesis method by which an initial wave form is shaped by subtracting wave forms from it. It can for instance be used to generate the “dish!” sound by starting with white noise, subtracting all sound but a narrow frequency band, and applying an envelope to it (varying it’s amplitude over time to produce an attack at the beginning of the sound, and a fast decay towards the end).

Programming languages exist which are specifically designed for sound synthesis and the researching of synthesis methods. The oldest language still in use is the CSound language (www.csounds.com), which attempts to be the “C” of synthesis languages. The following is an example of CSound code — the definition of a basic FM synthesizer.

instr 1 ; start of an instrument definition
amod oscils 300, 880, 0 ; modulator sine oscillator — arguments are amplitude, frequency, and phase
acar oscils 10000, amod+440, 0 ; Carrier oscillator with frequency equal to 440 (A above middle C) added to modulator
out acar ; send sound to output (sound card or file)
endin ; end instrument definition

CSound contains over 1000 unit generators (routines that produce sound samples). Super Collider (supercollider.sf.net) is another synthesis language, but designed for real-time sound synthesis and live coding. Live coding involves writing code live as to produce sound while a sound performance is happening.

Sound synthesis can not replace all sound effects, many sounds are very hard to produce with current synthesis methods. It can, however, be used for many sound effects which are currently prerecorded and played from storage. It is especially suitable for sounds which are artificial by nature (the “dish!” mentioned above, or the sound of electric equipment). It can also be used to process recorded sound, as to add more variation in sound effects. I hope to see more sound synthesis being employed in the future, specifically in games.

this oft-used quote, by koffka, can be used to summarise gestalt theory in a single sentence. this theory deals with the fact that very often the ‘whole’ that we experience/see/hear is not the same as merely dissecting something into pieces and adding them together. there are various ways in which we process input in such a way that we actually perceive more than is present, or perceive it differently. for example, consider the well-known image of a rubin vase in figure 1. this image is actually of a white vase on a black background, but sometimes it is perceived as two black profiles of faces on a white background.

figure 1: rubin vase

there are various principles that influence what we actually see in an image. some of these principles will be discussed below, but this is in no way an exhaustive list of the principles of gestalt theory. some of these principles are of greater influence than others and so can override the effects of another principle.

law of simplicity

this law, also known as the law of prägnanz or the law of good form, states that when we see a complex shape, we may perceive it as consisting of simpler components. an example of this can be seen in figure 2 and figure 3. the complex object given in figure 2 might easily be perceived as a triangle, circle and rectangle (as indicated in figure 3) instead of a the new whole complex object.

figure 2: complex structure

figure 3: simpler components

this fundamental aspect of gestalt theory can also be used to explain why we often see familiar shapes when looking at clouds. we want to perceive the most simplistic forms, and forms which we have previously encountered are familiar to us, and ‘less complex’.

figure-ground 

the rubin vase, that can be seen in figure 1, is a good example how the figure-ground principle can cause us to stumble in our perception of what we are seeing. when looking at an image, the image is decomposed into a figure and background. for example, in figure 2 the complex object in black is seen as the figure and the surrounding white space is perceived as the background. on a white page with black print on it, the white is perceived as the background whereas the black print on it is perceived to be the figure. with images such as the rubin vase, however, whether the white space or the black space is seen as the figure, the perceived figure is an object that most of us will be familiar with us (a vase or a face). the edges separating the figure and background is often interpreted as belonging to the object. this aspect of gestalt theory can be used to explain why camouflage works so well. instead of being in contrast with the background, camouflage enables animals (or the wearer of camouflage clothing) to blend into the background by using the same colours, and possibly similar textures, as the background and in so doing  making it difficult to distinguish a figure, especially if no figure is expected.

proximity

proximity is defined as “nearness in space, time, or relationship”, by the oxford dictionary. understandably then, the proximity principle in gestalt theory states that objects which are near each other are considered to be together / part of one greater object. the objects which are near each other do not necessarily have to look alike for the proximity principle to take effect. for example, consider figure 4. even though the rectangles are all similar, and the circles are all similar, the perceived groupings are that there is one group at the top left, and another at the bottom right, both consisting of circles and rectangles.

figure 4: proximity principle

similarity

the similarity principle sates that objects that look similar will be perceived together. similarity can be in the areas of shape, size, orientation and colour. one example of this principle can be seen in figure 5. even though all the objects are rectangles of the same size, the black rectangles and blue rectangles may be perceived as two different groups.

figure 5: similarity principle

in figure 4 we saw that the perceived groupings of the objects were according to the distance the objects were apart, even though all the rectangles and all the circles were similar. it can be deduced, therefore, that the proximity principle is higher on the hierarchy of gestalt principles than the similarity principle.

continuity

oftentimes we perceive some lines to be continuous lines whereas they could also be defined as separate lines. for instance, consider the figure 6. the most likely perception of this figure would be that there are two dashed lines – one horizontal and one vertical – that intersect in the middle. the figure is not perceived as having 18 lines, or as 4 separate dashed lines that come together in the middle – both these interpretations can also be correct. the reason for this is the continuity principle, whereby, when shapes are aligned, they together form a larger whole. as another example of the continuity principle, consider figure 7. in figure 7, the lines in (a) will more likely be perceived as grouped as in (b) than in (c). the reason for this is again the alignment of the lines. when coming to the intersection, a choice has to be made regarding whether to continue with the same course or change direction. going in the same direction is more natural and thus we perceive the red and blue lines as in (b) more readily as that in (c).

figure 6: continuity principle

figure 7: continuity

closure

the closure principle allows us to perceive ‘information’ where there is none, and in so doing helps us recognise patterns/shapes which are suggested, but not explicitly drawn. consider, as an example, the logo of the world wildlife fund in figure 8. we immediately perceive a panda, though there are definitely lines missing to complete the entire panda. the closure principle is therefore similar to the simplicity principle in the effect that it has – it allows us to discern simpler objects than only what is seen. it differs from the simplicity principle in that here, instead of breaking up a large complex whole into smaller, simpler objects, the (sometimes disjoint) objects are seen as a whole.

figure 8: closure

these are but 6 of the principles of gestalt that influence how we perceive objects that we see. there are many more, such as symmetry, common fate, past experience, uniform connectedness, common regions, parallelism etc. for more information on these, see the list of references.

list of references

1. m. soegaard, gestalt principles of form perception, interactive design foundation. http://bit.ly/1hJgGrY
2. s. bradley, design principles: visual perception and the principles of gestalt, smashing magazine, march 2014, http://bit.ly/1kK31A8
3. spokane falls community college, the gestalt principles. http://bit.ly/1oMAklo
4. k. broom, theory of visual perception. http://bit.ly/1o4NQ7Q
5. s. grais, gestalt principles. http://bit.ly/1o4NQ7Q
6. d. todorovic, gestalt principles. scholarpedia, 2008 http://bit.ly/1kS5Pfy

Group theory 101

A group is a very general mathematical structure defined as follows. Let G be a set, and let • be a binary operation on G—basically a function which takes two elements of G and gives an element of G back, like addition or multiplication on the integers. We say that (G, •) is a group if the following conditions are satisfied:

1. Associativity: For every x, y and z in G, (x • y) • z = x • (y • z).
2. Identity element: There is a unique e in G (called the identity element of G) such that for every x in G, x • e = x.
3. Inverse elements: For every x in G, there is a unique y in G (called the inverse of x) such that x • y = e.

If I’ve lost you with all of the symbols and jargon, a concrete example might be illuminating. Consider the set of integers Z and the binary operation +. We know that if we add three integers together, it doesn’t matter which addition we do first. For example, if we’re computing 1 + 2 + 5, we could first compute 1 + 2 = 3 and then 3 + 5 = 8, or we could first compute 2 + 5 = 7 and then 1 + 7 = 8. This is associativity. The identity element is 0 (add it to any number and you get that number back), and so the inverse of any integer is simply its negative: 4 + (-4) = 0. We may conclude that (Z, +) is a group, since it satisfies all the group conditions. In fact, groups originated as an abstraction of numerical arithmetic.

Another example of a group, and one very important for cryptography, is the multiplicative group of integers modulo p, denoted (Z_p, ·). This is essentially the set of numbers {1, 2, …, p – 1} furnished with the usual · operation, but where the result “wraps around” if it is bigger than p – 1. For example, in Z_5 we would have 2 · 4 = 8 = 3 and 4 · 4 = 16 = 1. Associativity is inherited from the usual integer multiplication. The identity element is clearly 1. It is not clear why every element of Z_p has an inverse, but this is a standard result from elementary number theory. Using Z_5 as an example again, we see that 1 · 1 = 1, 2 · 3 = 6 = 1 and 4 · 4 = 1, so each element has an inverse.

Before continuing to the next section, we define exponentiation for groups. Let G be a group and let x be an element of G. We define x^n = x • x • … • x (n times) for any positive integer n. We extend this to all integers by letting x^0 = e and letting x^(-n) be the inverse of x^n. You may check that the familiar exponentiation laws then hold (i.e. x^m • x^n = x^(m + n) and (x^m)^n = x^(mn)).

The discrete logarithm problem

Now that we have the basics of group theory down, we may define the discrete logarithm problem for groups, which reads as follows. Let G be a group with some element x and let n be an integer. Given the group elements x and x^n, determine the value of the exponent n. This is analogous to finding the logarithm to the base x of x^n. In the group Z, this is trivial: if you have x and x^n = x + x + … + x (n times) = nx, then you can find n by simple division. However, in Z_p, the problem becomes harder. No polynomial-time algorithms are known for solving discrete logarithms in Z_p (but some sub-exponential algorithms are known). In other groups, the state-of-the-art algorithms can solve discrete logarithms only in exponential time.

The Diffie-Hellman problem

The Diffie-Hellman problem is a slightly easier version of the discrete logarithm problem defined as follows. Let G be a group with some element x, and let m and n be integers. Now given the group elements x, x^m and x^n, we wish to find x^(mn). Clearly, if the discrete logarithm problem may be solved efficiently for G, then we may compute m and n efficiently, and thus compute x^(mn). However, there might be some clever method of combining x^m and x^n to form x^(mn) without first computing their exponents. This is why we say that Diffie-Hellman is an easier problem. For Z_p, no such method is known, as is true for many other groups, so that these two problems are actually equivalent in practice.

The Diffie-Hellman key exchange

We are now ready to define a group-based cryptosystem, called the Diffie-Hellman key exchange, which will be the conclusion of this post. Assume we have three parties: Alice, Bob and Eve. Alice and Bob wish to agree on some secret value, in such a way that if Eve were to eavesdrop on all of their communications, she would not be able to figure out what this value is. They will do so as follows. First, they agree on a very large group G in which the Diffie-Hellman problem is hard, and they pick some element x in G. Now, Alice computes a large random integer a, and Bob similarly computes b. They keep these values to themselves, but they tell each other the values of x^a and x^b. Now, Alice has the values a and x^b at her disposal, so she may compute (x^b)^a = x^(ab). Similarly, Bob my compute x^(ab) using b and x^a. Eve only knows the values of x, x^a and x^b. Should she wish to compute x^(ab), she will have to solve the Diffie-Hellman problem, which we assumed to be hard in G. Thus, Alice and Bob have succeeded in agreeing on a secret value.

In online marketplaces and ads

I first heard about this when I had the opportunity to briefly chat with Cliff Stein (perhaps best-known for CLRS) in March about his current research. One of the things they are looking at (as I understood it) considers a situation where an advertiser is provided with some sort of guarantee that it will be treated fairly over some period of time with regards to, say, the number of times its ads are displayed, compared to the ads of competitors. (Alternatively, advertisers may have the option of buying certain tiers of service, which imply that it will receive a certain amount of preference.) The complications in this case arise from the fact that different advertisers may have specified different keywords for their products and that it is not known how many further users will enter the system before the end of the time period. (A 2010 paper developing online algorithms along these lines may be found here.) A similar situation holds in online marketplaces, where a manufacturer/seller may be interested in the number of times its products are listed as one of the first three products returned by a search for certain keywords, with the additional consideration that users who quickly find relevant information are more likely to use a marketplace repeatedly, so satisfying promises to sellers must be balanced against showing users relevant search results.

In a recent talk at the lab, Stephan Ballot, head of product at OLX, mentioned that they decided to display most recently listed ads first, while giving some preference to ads with pictures, as these lead to more sales. This solution attempts to elegantly sidestep many of the intricacies of the problem, yet the question remains whether it is ‘fair’ to sellers that someone who posts their advertisement at 02:00 may never be listed among the top results due to the high number of ads posted every morning, while someone posting an identical ad at some other time of the day may be at the top of search results for quite some time.

In determining cricket outcomes

As all cricket followers known, the Duckworth-Lewis method of adjusting scores in rain-interrupted matches has been used since 1999. This method adjusts targets based on the amount of resources (measured in overs and wickets remaining) that the chasing team has left. The general consensus in the cricketing community seems to be that it does this fairly well, however, some questions arise whent these adjusted targets are used to determine the outcomes of matches (if you are ahead of the adjusted target when the game ends, you are declared the winner).

A paper by Bandulasiri entitled Predicting the winner in One Day International cricket considered 105 uninterrupted ODIs and compared the Duckworth-Lewis predicted outcomes after 30 and 40 overs have been faced by the chasing side to the actual outcome. It found that after 30 overs D/L correctly predicted the outcome of the match only 36.27% of the time, while it predicted the correct winner after 40 overs 52.2% of the time.

Its slightly embarrassing that a game with 2.5 billion fans around the world will do better to decide rain-interrupted games by simply flipping a coin.

In food (and many other things)

I’ve long been a fan of the following technique of dividing a cake fairly: Make a cut from the centre of the cake to an edge. Assemble the interested parties. Slowly rotate a knife from the cut around the centre until a person shouts stop – cut the cake at that position and hand it to the person who stopped you. Repeat until there is no cake left. The wonderful thing about this technique is that everyone thinks everybody else received less than their fair share and that they themselves received a fair share of the cake. (In writing this piece I’ve found that this is called the Dubins-Spanier algorithm and that it guarantees every one of n people to receive a piece he/she values to be worth at 1/n of the whole.)

If anyone is particularly interested in the literature on cake cutting (which is larger than you’d think, since much of it generalises to the fair division of dividable resources, for example dividing the cost of pollution between nations) a recent survey Cake cutting – not just child’s play may be a good place to start.

I think fairness is one of those things which are broad enough to ensure that someone will always feel they are being treated unfairly. This should not prevent us from seeking provably fair policies in the application and design of technology, nor in everyday life.

Did you recently notice any results regarding fairness?