Blog | Combine

# Blog

## The basic idea

The basic idea we have for reading the time (or any other analog device!) is to first capture an image of the device using a web camera and use the image processing tools in Sympathy for Data to read the hour and minute hands from the clock. Our goal is to do this with only the open-source image processing tools that are included in Sympathy for Data, and no custom code.

Our aim is not to create a solution that works for any image of any clock, but rather to show how we can reliably read the values of the given clock given a very specific camera angle and lighting situation. To do this for any clock and lighting setup requires more advanced techniques, often involving machine learning, and which harder to guarantee that it works in all of the target situations.

For the purpose of this blog post, we will not be using machine learning or any other advanced algorithms but rather rely on basic (traditional) image processing techniques. This problem resembles very much that of designing image processing algorithms that are used every day in industrial production — where you have a highly controlled environment and want simple and fast algorithms.  By controlling the environment we can make this otherwise complex task very simple and easy to design an algorithm for. When doing image processing for industrial purposes it is commonly found that you can simplify the problem and increase robustness by heavily controlling the environment and the situation in which your images are acquired.

For the impatient, you can download the dataset with images that we prepare in the first part as well as the finished Sympathy for Data workflow.

## Acquiring the data

Step one is to acquire some images of the clock and to try to analyse them in Sympathy. If you don’t want to repeat these steps yourself you can simply download the full dataset from here.

We start with a naive approach and just place the web camera in front of the clock and record images once per minute over a full day. Some example of these images are below:

What we can see in the images above is two main problems: the lighting varies widely depending on the time of day, and the lighting in the image itself varies widely due to specular reflections and makes part of the hour-hand invisible second image above. Whatever algorithm we come up with will have a hard time to deal with an invisible hour-hand.

We can also note that with a stronger and directional light we would have shadows cast by the hour and minute arms of the clock is projected at different part of the face of the clock depending on the incoming light direction. If we where to directly try to analyse these images we would need to compensate for the shifting position of the shadows, and we could not use any simple thresholding steps since the overall light changes widely. Any algorithms we create for these kind of images will inherently be more complex and possibly more prone to failures when the light conditions change. We would need to test if over a wide range of conditions (day, night, sunset, rainy weather, sunny weather, summer, winter) to be sure that it works correctly under all conditions.

An attempted first fix for the specular reflections was to remove the cover-glass of the clock, the idea being that the face paint of the clock wouldn’t be reflective enough to give these issues. This however wasn’t enough to solve the problem with disappearing arms for all lighting conditions, and are we to apply this idea to an industrial setting it may oftentimes not be possible to make such a modification. A better solution is therefore to remove all direct light in favour of a setup with only diffuse lights.

To solve both these problems we choose to make a controlled environment with only diffuse light and where we know that the only thing that changes are the positions of the clock’s arms. We force a constant light level by enclosing the clock and camera in a box with a lightsource. This way we can also eliminate the the shadows of the clocks arms by placing the lightsource from the same direction as the camera.

## Building a camera friendly light source

In order to eliminate the shadows from the clock arms and to provide a even and diffuse lighting conditions we place a ring of white LED’s around the camera. Usually this is done using professional solutions such a light ring for photography, but we’ll manage with a simple 3d-printed design and some hobby electronics. You can find the downloads for these over a Thingiverse.

The design for this light is simple ring where we can add the lights plus a diffuser on top of it to avoid any sharp reflections.

After printing the parts above we place a number of white LED’s in the small holes in the middle part above. By twisting the pins together with each other on the underside (take care with the orientation of anode and cathode!) we can easily keep them in place while at the same time connecting it all up. See if you can spot the mistake I did below in the wiring. Fortunately it was salvageable.

Next step is to place the diffuser over the LED’s and to attach it onto your web camera. Power it with approximately 3V per LED used. Point it straight at the clock and put an enclosure over it. We can used a simple carton box as a simple enclosure that removes all external light.

Congratulations, you can now get images of the clock with perfect lighting conditions regardless of sunlight, people walking bye, or any other factors that would complicate the readings.

## Pre-processing the images

When doing image processing it is common to operate on grayscale images unless the colour information is an important part of the recognition task. For this purpose we first run a pre-processing step on the whole dataset where we convert the images to greyscale and downsample since we don’t need the full resolution of the camera for the rest of the calculations. This can easily be done using Sympathy for Data.

First create a new flow and point a Datasources directory to a copy of the dataset (we will overwrite the files in place). Add a lambda node by right clicking anywhere in the flow and select it. Connect a map node to apply the lambda for every datasource found.

Before you can run it, add the nodes below into the lambda node to do the actual image conversion. You need to select greyscale in the configuration menu of the colour space conversion node, and rescale X/Y by 0.5 in the transform image node. Note that the “save image” node here overwrites the images in place, so try not to run the node until everything is ok. Another option would be to compute a new filename to be used instead using eg. a datasource to tables node and a calculator node.

In the dataset that you can download we have already done these conversions (downscaling to 800×500 pixels) to save on bandwidth.

## Analysing the images

Our goal in this section is to create a Sympathy workflow that allows us to take any image of the clock and convert it into an hour and minute representation of the time.

### Creating a template

For the first step we want to extract only the arms of the clock that should be analysed. For this purpose we will use a practical trick to easily detect only the moving parts of the image. We do this by first calculating a template image that show how the images would look if all the moving parts were removed. This trick only works when the camera is fixed and there are no major changes in overall lighting.

Start by calculating the median (or in our case max since we know the arm’s are black) of a few different images from the dataset. This will give an image where the arms of the clock is removed.

Select max as operator in the Overlay Images node below. This works since we know that the arms are darker than the background, and whichever pixel has a light colour in any of the images will have a light colour in the final image.

The results look surprisingly good given that we only used a few images (where the arms where all in different positions):

We save this template in a separate file so that we don’t have to redo the calculation for each image that should be processed.

### Extracting the minute and hour arms

Continue by creating a new workflow and load one of the images to be analysed. We start by making a subtraction of the image to be analysed from the template image.

This will give an image where only the arms are visible, you will need to select “subtract” as the operation for the “overlay images” node.

The next step will be to perform a threshold to pick out only the arms of the clock as a binary image. To do so we use a Threshold node and set it to basic threshold. We can figure out a good threshold level by looking at the histogram above of the image after subtraction. We see that the maximum value of the image is 0.55 and that something significant seem to happen around the 0.4 mark (note that the graph is logarithmic!).  We set the threshold to 0.35 and get the results shown above.

Since there can be some small smudges and missed spots on the binary image we apply morphological  closing on the image using a structuring element of size 20 which should be more than enough to compensate for any missed pixels caused by noise, scratches on the object/lens or the otherwise black areas of the image.

Finally, we can note that we only actually need to see the tips of the hour and minute hand in order to read the time. If we sample to check for the the minute arm at every point in a circle with a radius closer to the edge of the picture we can know which pixels belong to the minute arm. Similarly, if we sample every point in in a smaller circle we get one or two sets of pixels corresponding to the hour arm when it is below the minute arm or  both the hour arm and minute arm when they are not overlapping.

We can do this sampling by first creating two new templates that we use to select a subset of the pixels. This is done by drawing a white ring on an otherwise empty image for each of the two selections. We can do this using the Draw on image node and a Manually create table node that gives the XY coordinates (416, 256) and radius 200 for a circle with colour 1.0 and 170 for a circle with colour 0.0 — corresponding to the ring selecting the minute arm below:

After multiplying these two templates with the thresholded image (using again the overlay images node)  we get two new images with blobs corresponding to the tips of the hour and minute hand:

All that is left now is to extract the coordinates of these blobs and to apply some math to convert them into hours and minutes.

### Computing the minute

We can compute the position of the minute hand by using a Image statistics node with the algorithm “blob, DoG” with a threshold of 0.1. This algorithm finds “blobs”, or light area on a dark background, in an image by subtracting two low-pass (gaussian) filtered version of the image filtered at different scales.

All other parameters can be default, but the default value for threshold of the difference-of-gaussian algorithm is too high for our inputs.

Now all we have to do is to convert the XY values 443, 426 of the tip of the minute hand into an actual value in the range 0 – 60. We can do this by calculating the vector from the center of the clock determined from the raw image as (416, 256) to the point of the detected blob. This gives us a vector (187, 10). By taking the arctan of this vector in a calculator node we can get the angle to this point and convert it into minutes. Note that we invert the y-component of this vector to compensate for the difference in coordinate systems (y-axis in images point down):

### Computing the hours

In order to compute the hour we need to eliminate one of two possible candidates for the hour. Consider the blobs shown below, from just this data it is hard to know which hour it is:

However, what we can do is to take the position of the minutes that we calculate above and clear out one of the two blobs above. Since we know the radius that we used for the circle multiplied with the data, we can easily draw a black area on top of the location where the minute arm is located and at the given distance from the centre:

For this purpose we use another calculator node to compute the X/Y coordinate above and to draw a black circle onto the image at that location. For clarity it has been drawn as a brown circle in the example above to see what area of the image is deleted.

We extract the hour value from the remaining blob, if there is one, similarly as to how the minute value was calculated. Note that if there is no blob in the image containing the tip of the hour arm then the expression belows gives a NaN value.  This happens when it is under the minute arm.

Finally, we can finish the flow by adding in a special case calculation that checks if the ‘hour’ column has the NaN value and if so instead derive the hour position from the minute position. In this step we also round the minutes to even number and round the hours down to nearest smaller integer. Note that we subtract a fraction of the minutes from the hours before rounding due to how the hour arm moves closer and closer to the next hour as the minutes raise.

We also subtract 1 (modulo 60) from the minute position since the captured images where all slightly rotated clockwise. We could have compensated this in the original pre-processing if we had noticed it earlier.

## Time to check the results

Before we are happy with the flow, let’s check how well it performs versus the ground truth. Since the timestamp was saved when each image was captured we can easily compare these values with the results of the flow. Due to the sampling process and since the seconds of this clock wasn’t synchronized with the seconds of the computer sampling them — we should expect to be off by one minute in some of the readings.
As we can see in the table below we successfully read the time, with a difference of at most one minute, for first 100 images.

By only allowing ourselves to use the first 50 images when we developed the flow, and then validating it by running on a larger dataset we gain confidence that the algorithm works for all the situations it will encounter. We have run it the full dataset of 700+ hours without any other errors.

Sympathy for Data is a visual software tool that helps to link scripts and data between different systems and enables analysis.

The tool targets all domains where data analysis is carried out off line and is challenging and repetitive. Our focus is on automating the tasks of importing, preparing, analyzing and reporting data. In some respects, it is also a visual programming environment.

Sympathy for Data is used by a number of leading companies in different industries, such as the automotive, process and automation industries. At Combine we believe that automation is the key to long-term success, yet a large proportion of current analysis is done manually. This is no longer sustainable as data continues to grow in every respect. Sympathy for Data supports subscription services to databases, network disks, etc. It can find, filter, sort and analyze data as well as create automatically formatted reports.

Applications
Among other things the tool allows you to:
– Transfer data from and to all sources (DB, web & remote, local).
– Move your favourite scripts to nodes and turn them into an analytical flow.
– Easily share data processes across an entire organization.
– Run data processes in batch mode to enable scheduled reporting.
– Easily share data from a data process with web reports or other chosen formats.

One of the aims of Sympathy for Data is to allow users to manage data from many different sources and in different formats. You can connect the tool to databases, select files from different network devices, or analyze thousands of Excel files automatically. We have developed the tool to manage large amounts of data along with other forms of useful data, such as metadata (units, dates, etc.), results and other custom data needed for analysis.

A tool for the entire organization
Sympathy for Data can easily be used throughout an organization, thanks to the flexible configuration options. The tool can be deployed as a standalone application, integrated in a server environment or combined with other enterprise solutions such as SQL (Server Integration Services), SharePoint, etc. The purpose is not to lock users into the platform, but instead to serve as an interface between different systems, data formats, etc.

### 1. Grabbing that cup of coffee

In the figure below, a two link robot arm is depicted. We say this depicts your arm. The upper
arm has the length r0 and the forearm the length r1. The position (x; y) of your wrist s described
by the two angles q0 and q1. Your wrist is currently located at the red dot. Say we want to the
grab a cup of coffee that is located at the blue dot. Pretend that you are a robot being controlled
by a computer giving commands to your upper- and forearm. What should the angles q1 and q2
be to achieve this? This type of problem is usually called the inverse kinematics problem. First,
we note that there should be two valid solutions, one with the “elbow” up and one with it down,
right? However, assuming this is us grabbing a cup of coffee, our arm is imposed to kinematical
constraints meaning that the elbow can only be down. I skip the equations for this, but they
can be found in for instance Robotics by Bruno Siciliano et.al.. The solution for this problem is
analytical, but however not completely trivial I would say.
Let’s just say we found the angles q0 and q1 and full of confidence we are to grab our cup of coffee.
Preferably we should move along a straight line, because we have a computer screen in front of
us. However, these angles say nothing about how we reach our cup of coffee. If we just first set q1
to our calculated target value, and then q0 the robot arm end point might move along the dashed
line or something similar. We would knock down our screen and maybe even that cup of coffee in
the process, which is all but a good start of the day.
So, we don’t just want to move to a certain point of interest, we usually want to reach that point
while being constrained to a specific trajectory. A common way in the digital world to do this
is to solve the inverse kinematics in very small steps, where all small steps adds up to a straight
line. This implies that the angular velocities q_1 and q_2 should be coordinated so we get a smooth
movement. A challenge here is that the dynamics of your arm is highly non-linear. Even if your
arm were actuated by ideal electrical motors, the equations of motion could well fill up a whole
page. In this case your arm are actuated by various muscles, which further adds complexity.
Then, we probably want the Cartesian velocity (x_ ; y_)T along the straight line to fulfill some
criterion. Probably we want to move a bit faster at first and slower when we reach the cup so we
can slow down in time and not spill coffee all over the place. This implies that we should want to
employ some trajectory planning. In the end we have a trajectory involving joint space variables
q1; q2; q_1; q_2 as well as Cartesian space variables x; y; x_ ; y_. So this starts to sound at least like a bit
of a hairy problem, eh? Then, add other challenges as that maybe we cannot even reach the blue
dot given that our arm is too short? Or that there is a bowl of cereals, a computer screen or some
other constraint in the way that we need to circumvent.
Then let’s say we add another link to your arm. Now we have three joint variables q1; q2; q3. Having
three input variables and two output variables (x; y) we can suddenly have infinite solutions to the
inverse kinematics problem. This is called a kinematic redundant manipulator. Off course, your
arm probably doesn’t have three links (would be quiet cool though?). But, your arm has far more
degrees of freedom than depicted here in 2D. You can tilt your forearm, upper arm and what not.
Each and every of your fingers are even more complex than the planar manipulator depicted. For
this 2D problem, your arm is kinematically redundant and we couldn’t find a closed form solution
for the inverse kinematics problem. We have to select some of the infinite solutions according to
criterion. A way to do this is to formulate some form of optimization problem. Machine learning
is also being employed sometimes.

Figure 1: A figure used to derive some basic ideas related to inverse kinematics

### 2 Kinematics and the evolution

Are you convinced now that grabbing a cup of coffee is maybe not as trivial as you might have
thought? Back to the philosophical question, what makes us human? For one, we are an animal
with relatively high intelligence compared to others creatures we know in this world. Without
dwelling into the subjective definition of what intelligence is, I think we can all agree on this. This
is what enabled us to develop tools helping us to gather, store and process foods among other
things. It encompasses all from weapons such as spears and archery, agriculture, taming fire and
so on. But what would these ideas concepts be without our ability to physically manipulate the
world? Agriculture and fire are merely theoretical pipe dreams when lacking some sort of ability to
achieve this things in practice. Surely, thinking might be existing. But you couldn’t think without
eating. Not in the way humankind exists today anyway.
This is where our advanced kinematics come into play. Advanced kinematics control is as crucial
to define humanity as we know it, as our intelligence I would say. You as a reader, might
not be dependent on your ability to make fire in order to survive in this world. Perhaps clacking
the keyboard of a computer is quiet enough. Which is applying kinematics control. But Stephen
Hawking could do without it you say then. Sure, he personally, yes. But those who built the first
computers? Those who scrabbled down the theorems necessary to build the first computer? Nope.
Then, say we all would communicate and operate like Hawking’s did. You would still at least
need to eat, right? Even if you could communicate with merely your mind, you would still need
to somehow run agriculture. Which again, means physically manipulating the world. It seems
inevitable that our existence is depending completely on our ability to physically manipulate the
world.
Let’s assume that the evolution made us interested in things that were beneficial for our survival
and reproduction in various ways. This is probably where sports come in. Apart form competition,
it is a way of refining our kinematic abilities. Spear-throwing, wrestling and boxing can probably
be directly related to the need of defense and hunting. A tribe being good at handball or a precursor
to it, would probably also be better at throwing stones at both prey and attacking enemies.
Those playing football would probably catch a hare better. Most culture employ dancing. While
dance can fulfill a variety of purposes, one is certainly displaying reproductional benefits. It could
be a way showing off genes being able to handle kinematics well. Do we have complex robots?
Yes. Does anybody of them dance well yet? Well, no. A robot that could dance well would thus
arguably be more complex and all robots so far known and would be able to perform many other
complex tasks then dancing. A person showing off some smooth moves at the dance floor basically
communicates “hey, my gene-pool is probably super-good for a variety of tasks in this world that
is beneficial for our existence. Good from all to hunting rabbits to climb trees”.
2
So, smooth and advanced kinematics is not a of interest for engineers and such only. The interest
for it is probably even coded into the DNA of each and every human being. It is fascinating
how we as a humanity, consciously or not, many times happen to mimic features and stages of the
evolution.

Controlling the temperature during beer brewing is essential for the quality of the end product, as well as ensuring an efficient production. By eliminating manual control in the production of beer a more consistent product can be produced. During this thesis project the temperature control strategies for a heat exchanger and the fermentation process has been modelled and developed.

During fermentation of beer, a brewmaster wants to control the temperature at which the fermentation occurs with great precision. Not only does the temperature need to be steady, different temperatures are needed during different stages of the fermentation process. With a precise controller capable of ensuring a unique temperature profile the brewmaster can repeatably create the best tasting beer possible. This is due to the temperature during fermentation affects the flavour profile of the finished product. With the additional benefits of being able to monitor the progress of the fermentation through the online monitoring system, being present at the brewery is no longer needed for routine checks of the beer.

By modelling the biological behaviour when yeast fermenting a variety of different sugars into ethanol and carbon dioxide, precise control of the temperature is achieved. Implementation of a mathematical model based on a modified version of the equations derived by Engrasser was used in Simulink.

During the beer brewing process, the last step before the fermentation starts is the cooling of the wort. This is done by pumping the boiling hot wort through a heat exchanger. By modelling the thermodynamical system a controller could be developed. It is of importance to ensure that the wort is at a precise temperature when the fermentation starts, in order to give the yeast the best possible environment. By implementing our controller the flow used in production can be increased as much as 65%, with the added benefit of a consistent and predictable temperature in the fermentation vessel, eliminating the guesswork from manual control.

Assume that we have a mass. Its purpose in life is to move from one point to another in a two-dimensional space. It can do this by applying a force in any direction as long as the magnitude of the vector is limited.

The mass is obliged to visit two points on the way while it is not allowed to violate the laws of motion.

The mass has a maximum of 50 seconds to fulfill its task as quickly as possible while the total energy consumed is minimized. The laws of motion of the mass are included as constraints when the optimum is defined as:

$$\min_{u_x(t),\,u_y(t)} w\,\underbrace{e(t_f)}_{\text{energy}} + (1-w) \underbrace{t_f}_{\text{final time}}$$

$$\begin{array}{rcll} \text{such that} & & \\ t_f & \leq & 50 & \text{final time} \\ u_x^2(t) + u_y^2(t) & \leq & 1 & \text{maximum force} \\ x\left(\frac{1}{3}t_f\right) & = & 0 & \text{first waypoint} \\ y\left(\frac{1}{3}t_f\right) & = & 1 & \\ x\left(\frac{2}{3}t_f\right) & = & 1 & \text{second waypoint} \\ y\left(\frac{2}{3}t_f\right) & = & 0 & \\ \dot{x}(t) & = & v_x(t) & \text{equations of motion} \\ \dot{v}_x(t) & = & \frac{1}{m} u_x(t) & \\ \dot{y}(t) & = & v_y(t) & \\ \dot{v}_y(t) & = & \frac{1}{m} u_y(t) & \\ \dot{e}(t) & = & u_x^2(t) + u_y^2(t) & \\ \end{array}$$

Since we have two goals working against each other, the parameter $$w$$ is used to weight the importance of the two terms. There is a trade-off.

This problem can be solved using Pontryagin’s Principle. In this case we are using the numerical solver ACADO and the problem is solved for $$w \in \left\{ 0.0,\,0.1,\,0.2,\,\dots,\,1.0\right\}$$.

The set of trajectories for different $$w$$ become

where the widest trajectory minimizes the time (high velocity) and the trajectory with the tightest turn minimizes the energy (low velocity).
The Pareto Front is

Here we see that a good trade-off might be somewhere in the region between 25 and 30 seconds since the energy does not change much for a change in duration and vice versa.

Optimal control is incredibly powerful, but it can also be quite difficult to solve complex problems. The formulation of the model needs to be correct and the constraints must be formulated such that a solution exists. For complex problems, the solver needs to be given a good initial guess of the solution, otherwise, it might fail to find a feasible solution at all.

Do you hear that? Is the sound of shorts and flip-flops rapidly being fetched from storage. Juvenile birds leave their nests, mosquitoes sharpen their mandibles, and you start making drinks with fruits that have names you can’t really spell.

In spite of the official date being June 21 of 2018, summer has already arrived on most of the northern hemisphere: spray me full of sunscreen, lather me on bug repellent and all hands on hanging the hammocks because the time to read outside is now!

If you want some inspiration, here are some Books and Curiosities that you can find interesting.

We trust that you can take just about any technique / paper / piece of code and learn from it. But communicating clearly? Making your message interesting while communicating? Knowing what kind of questions to ask before diving into a task? Reading the possible meanings behind an answer to a question? That is a skill just like any other and requires just about as much work if you want to hone it.

Most of this list is not about any specific mathematical or statistical technique. This is rather a list of resources to develop those “soft” yet important sides of ourselves that we often overlook while being immersed in math and code.

## Books

#### “Brief: Make a Bigger Impact by Saying Less” by Joseph McCormack

———————————- ———————————-

[brief] was my secret weapon during a Swedish Trade mission to Geneva on 2017. We used the methods in this book for refining a 30 second pitch about our companies and products. The real power became evident when the whole trade mission was asked to trim the pitch to 20 seconds as en exercise. We were able to deliver a clear message about our company and business using exactly 4 sentences.

Ever dreamed of being capable of controlling the succinctness of your presentations? Tired of back-to-back meetings? Read this book. Share it with your coworkers. Give it as a gift to your rebellious teenager instead of that gadget. Go ahead and be the change you want to see in the world!

#### “Designing with Data: Improving the user experience with A/B Testing” by Rochelle King, Elizabeth F. Churchill & Caitlin Tan)

————————————— —————————————

This book is strongly focused on how to study and understand your user, using data. From this main goal, many important points are raised: What are we hoping to capture about your users from the data you collect? How do you use qualitative data and quantitative data together? When is small sample research useful? What is the meaning of statistical significance in the context of making a design decision?

One of the main messages of this book is pretty refreshing: there is a false dichotomy between data and design. When design is informed by data, both fields work towards a shared goal: understanding users and crafting experiences.

Are you involved on creating anything that someone else will use? From reports to applications, to that business idea you had about renting Augmented Reality parrots, the same applies:

“Designers, data scientists, developers, and business leaders need to work together to determine what data to collect, as well as when, why, and how to manage, curate, summarize, and communicate with and through data.”

#### “The Elements of Eloquence: How to Turn the perfect English Phrase” by Mark Forsyth

————————————– ————————————–

This book has a strange combination of punk rock and refinement. Few things say “anti-authoritarian” as loudly as bashing Shakespeare in the first chapters of a book on eloquence. Granted, I think his point is that many literary resources can be used by anyone, if you learn the right formulae and have some creativity for filling in the blanks.

Do you want your writing/presentations to be memorable? Take some tips from this book. Study the forms that phrases can take. Think about how can you use them to convey the right messages. Have fun. And most importantly: Less people will nap on your keynotes!

## Curiosities

#### High Resolution Series on Design

The paths that lead you to mind-opening experiences are often accidental. One of the speakers of the Tales from the Road Meetup (and a dear friend) shared a High Resolution episode with Rochelle King from Spotify. The whole series extremely useful for grasping the language, worries and experiences of tech companies in the current age.

https://www.highresolution.design/

#### Six Degrees of Francis Bacon

Surprising how can very simple mathematical tools can yield such interesting and beautiful results when applied in an unexpected context. In particular:

“While our interest has been in reconstructing the social network of a specific time and place – sixteenth- and seventeenth-century Britain – there are few barriers to re-deploying our method in other historical or contemporary societies. We used short biographical entries, but we could with minor changes have used contemporary book prefaces, modern scholarly articles, blogs, or other kinds of texts. All that is needed is machine-readable text in which the co-occurrence of names is a reasonable indicator of connections between persons.”

http://sixdegreesoffrancisbacon.com

http://www.digitalhumanities.org/dhq/vol/10/3/000244/000244.html

Suggestions? Write a comment! Happy summer!

Once every year we are updating the business plan. So this Monday and Tuesday we are adjusting the plan, both the long-term and short-term to make sure we are prioritizing the right things. The best ideas does not come from sitting inside a conference room looking at the whiteboard. Therefore we are at Isaberg Mountain Resort making use or their mountain bike tracks in combination with outdoor meetings.

When looking at our previous business plan we see that we have succeeded in following the big picture. For example, we have started a Data Science group at our offices in Lund and Gothenburg; have had more focus on marketing such as developing a new homepage and graphical profile etc.

Our vision is still, and will always be, to improve technology around the world.
Enter The Next Level.

#### Everybody is talking about Data Science today, but you already have numerous years of practical experience in the field. How come you were so early in the game?

During my studies over 10 years ago, I heard about a startup that used biology and genetics to solve advanced problems and it sparked an interest that ultimately changed the course of my academic life. I had finally found a way to combine my interest in biology, mathematics and programming. After studying all relevant courses, I ended up doing my master thesis using machine learning to predict outcome after heart stop.

#### Even now days it’s difficult for data scientists to get real life experience after studying, how was it for you?

I was lucky to get a job at a start-up that had good connections with companies in Silicon Valley. They were very curious and eager to start working with machine learning and AI long before it was the buzzword of the day in the rest of the world.

#### So, what was it like getting out in the industry?

Working with large American retailers and online e-commerce companies gave us access to big amount of high quality data. This was of course a dream for a data scientist and gave me and the team possibilities to develop and experiment with algorithms for real-time machine learning. We quickly learned that the academic research in the field entirely lacked focus on real-time events. The main difference with real-time systems compared to working with stored data is that in real time systems you actually have the possibility to instantly affect the outcome of your algorithms. For example, you can give better product recommendations where you increase sales and learn more about the user.

#### What type of challenges did you encounter?

In order to set up a real-time system that could train machine learning models efficiently, you need a very efficient infrastructure that can process big data extremely fast. Since there were no existing software that fulfilled our needs we started to develop our own tool, the Expertmaker Accelerator. I was a little bit surprised how much fun it was to work with extreme optimization since I’m not originally a computer nerd. But it went really well and it was very satisfying when you can speed up your algorithm by magnitudes.

#### That sounds awesome! It must have generated some buzz in the industry?

Well, I’m not sure how famous the tool was outside our company. But the customers were very satisfied, and we were bought by eBay, which was one of our customers. The tools are now open sourced by eBay and free for anyone to use, which is great. That means that we can continue to use it to deliver efficient machine learning for big data projects.

#### So why did you change from eBay to Combine?

I felt it was time to take on a bigger responsibility and not only developing the technology aspects of machine learning, but also how and where data science is used. Combine gives me the freedom to do just that. I am also able to work with many different companies, where I have full freedom to choose who I collaborate with. I firmly believe that you become a better data scientist if you are exposed to diverse challenges. I talked to many different companies, both locally and abroad, but eventually I choose Combine because of the technical level and start-up like company culture that I really liked.

#### What’s your vision for Data Science at Combine?

To to create real value for our customers. This is an area with a lot of hype, and many enthusiastic developers. It’s very easy to start cutting corners on the engineering quality and the scientific soundness and you end up with useless solutions. To avoid that we work a lot with mentoring and peer reviews. I also think it is important that data scientists are good developers as well and we make sure to only hire people with really good programming skills. Our work consists of a mix of on-site consultancy and in-house projects, so we can get as much experience as possible and then share it with our team members. This means that we can solve all our customers needs and even become their complete data science department, taking responsibility of all aspects ranging from storing data securely to developing machine learning algorithms and hosting live production solutions. Among other things, this will enable companies without internal data science departments to quickly and cost-efficiently jump on the data science train.

Read more about Sofia and her teams work with the Expertmaker Accelerator on eBay’s tech blog:

https://www.ebayinc.com/stories/blogs/tech/announcing-the-accelerator-processing-1-000-000-000-lines-per-second-on-a-single-computer/

### Optimal Parking Strategy with Markov Chains and Dynamic Programming

Dynamic programming is an interesting topic with many useful applications in the real world. However, the magnitude of the state-space of dynamic programs can quickly become unfathomable. Warren B. Powell has published a book where various approximations can be applied to make otherwise intractable problems possible to solve. There is an interesting problem in this book which does not demonstrate the methods of approximation, but rather how an optimal control policy can be chosen given a Markov Chain.

Dynamic programming is an interesting topic with many useful applications in the real world. However, the magnitude of the state-space of dynamic programs can quickly become unfathomable. Warren B. Powell has published a book where various approximations can be applied to make otherwise intractable problems possible to solve. There is an interesting problem in this book which does not demonstrate the methods of approximation, but rather how an optimal control policy can be chosen given a Markov Chain.

We are driving a car and we want to park it in such a way that the total time to get to a restaurant is minimized. The parking lot contains 50 spaces which are not occupied given a probability of $$p = 0.6$$. For some reason, we cannot see whether the next space is occupied or not until we are approaching it. Driving between the spaces takes 2 seconds and walking from there to the restaurant takes $$8(50-n)$$ seconds, where n is the parking lot number.

If the last space is reached we can always get an opportunity to park, but that would take 30 seconds. The final set of states is given in the following figure:

The action space for the free states 46-50 is either “continue” or “park”. For the taken states 46-50 we can only choose to “continue”. We are using 0 = continue and 1 = park. For these final epochs we have the following 32 policies to choose from:

 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1

In each state we can calculate a value function which gives us the potential value of being in a given state. The future value is calculated as $$p V^{\text{free}}_{n} + (1-p) V^{\text{taken}}_{n}$$. This means that we have to calculate the value of each node for every possible action. Solving dynamic programming problems explicitly this way is doomed to fail due to the curse of dimensionality. Approximative dynamic programming can help to cope with large problems, but in this case it is not necessary.

To calculate the values we have to go backward in the graph. First, we start with parking space 50: $$V_{50}^{\text{free}}(0) = 30, \qquad V_{50}^{\text{free}}(1) = 0, \qquad V_{50}^{\text{occupied}}(0) = 30$$ For parking lot 49 we have: $$V_{49}^{\text{free}}(0) = 2 + p V_{50}^{\text{free}} + (1-p) V_{50}^{\text{occupied}}, \qquad V_{49}^{\text{free}}(1) = 8, \qquad V_{49}^{\text{occupied}}(0) = V_{49}^{\text{free}}(0) = 12$$ and so on.

By doing these calculations we find that the optimal policy is to ignore all parking lots except for the last two ones where you should park if the opportunity is given.

To find a function which describes complex data over an entire domain can be very difficult. By subdividing the domain into smaller regions it is possible to use simpler functions locally which, when joined together, is able to predict the entire domain well. Fitting the local functions using least-squares does not guarantee a continuous function globally without introducing equality constraints. In the book Matrix Computations by Golub and van Loan a simple method to solve least-squares problems with equality constraints (LSE) using linear algebra is described. This method involves two factorizations and a matrix multiplication.
The LSE-algorithm is implemented in LAPACK as GGLSE and can be found in e.g. Intel MKL.

Given $$A \in \mathbb{R}^{m \times n}$$, $$B \in \mathbb{R}^{p \times n}$$, $$b \in \mathbb{R}^m$$, $$d \in \mathbb{R}^p$$, $$\text{rank}(A) = n$$, and $$\text{rank}(B) = p$$ we can solve

$$\begin{array}{rcl} Ax & = & b \qquad \text{(regression)} \\ Bx & = & d \qquad \text{(constraint)} \end{array}$$

using

$$\begin{array}{rcl} B^T & = & QR \\ \text{Solve} \, R(1:p, \, 1:p)^T y & = & d \\ A & = & AQ \\ \text{Find} \, z \, \text{which minimizes} & & || A(:, \, p+1:n)z-(b-A(:, \, 1:p)y)||_2 \\ x & = & Q(:, \, 1:p)y + Q(:, \, p+1:n)z \end{array}$$

The first example is a piecewise linear function which is divided into six intervals. Each local function is fit using the data points present in its interval. The end points do not match up leading to a discontinuous function representation.

By using LSE and forcing the end-points of each segment to be continuous (with discontinuous derivatives) while the mean-square error is minimized, we obtain the following result:

Using higher-order polynomials opens up for even better descriptions of the data. Using third order polynomials in the same intervals as the linear without using LSE does not look very nice.

Since we have a higher order polynomial we can set equality constraints for both the end-points and the and the first-order derivatives leaving a discontinuity in the second-order derivative and higher.

Taking the step to two-dimensional data is straightforward. Here we are using a set of points generated by the inverse of the squared distance from (0,0).

Dividing the domain into 5×5 square subdomains, in which the points are described using two-dimensional functions without any constraints, looks like a storm-damaged tiled roof.

Applying the LSE-algorithm on each corner point effectively stitches all edges together.

Subdividing the domain further gives a better fit, but the global function risks becoming overfitted since fewer data points are used for each subdomain. Regularizing the final problem can help out if this happens. With 8×8 intervals, the function looks smoother.

This is just one application where a mean-squared error measure can be minimized while fulfilling equality constraints without having to resort to an iterative optimization algorithm. Linear algebra, despite being linear, can be incredibly powerful in practice.