In recent years researchers have found numerous different ways to fool image classification software. An image of say a face can be tweaked slightly so that image recognition software detects something completely different, perhaps a rifle, even though for a human observer the face is still clearly visible and the rifle cannot be seen. In one respect, when AI is being fooled, it is becoming more human. There are optical illusions that trick a human but not AI and we have now found the reverse.
Let's now look at the mathematics of what is going on. We'll represent the image as a vector x. This can of course contain a value for red, green and blue at each pixel. The neural net estimates the likelihood of a rifle being in the images, We'll call this R(x). For the original input image the likelihood is low. The hacker can then work out the gradient, i.e. the partial derivative of R with respected to each element. This can be done numerically using a standard finite difference approach:
\[\frac{\partial R}{\partial x_i} \approx \frac{R(\underline{x} + \delta x_i) - R(\underline{x} - \delta x_i)}{2 \delta x_i} \]
(The purists might slightly argue with my notation there, but they know what I mean.)
The hacker can then use an iterative gradient ascent methodology to tweak the image, so that the net reports it to be more likely that a rifle is present. After each step, the gradient would be recalculated. One of the interesting features of this hack is that the hacker doesn't need to know the details of the architecture of the neural net. He just needs access to the output R(x). It is sometimes found that a small tweak to the original image results in the net reporting that a completely different object is contained, even though to a human the tweaked image appears almost identical to the original.
But what can we do to improve the robustness of image classification (AI) software?
One option would be to use multiple different neural networks with different architectures and different training data. If one of the nets detects a rifle but all the others detect a face, then we would suspect that one of the nets may be being fooled. One of the nets could be trained on only grey-scale images, i.e. with the red, green and blue replaced by shades of grey. Before the combined neural nets could be deployed, an algorithm would need to be written to combine the results from the various nets. We may have one net that is the best, in which case it would only be over ruled if all the other nets give a different result. However, one problem would be that if the hacker were to return and if he were to attempt the same hack against our combined net, he may also be somewhat successful. Remember we showed above that the hacker doesn't need to know any details of the neural net architecture. If we replace one net with a set of nets it may not necessarily improve matters that much. We would deem our defense against the hack to be a success if the only way the hacker could convince our system that a rifle is in the image would be to change the image so much that we would all agree that it does appear as though a rifle is in the image.
However combining the result from multiple nets does not necessarily guarantee this.
Here is the outline of a suggested algorithm that attempts to defeat the hacker:
We start with our primary, lovingly trained neural net which is fairly reliable. We also construct a set of perhaps 10 alternative nets, with different architectures and trained with different data. When we want to recognize an image, we first use a hash of the image as a random seed and then use a random generator to pick say 5 of the 10 alternative nets. The image is then passed through our primary net along with our 5 chosen alternative nets. The final result is some non-linear combination of our primary net along with the others. When the hacker then comes along and uses his gradient ascent method he would find that there is so much noise from our random switching of the alternative nets that his method doesn't work well. And so we would have a fairly robust defense against the hack.
There are some drawbacks to this approach: Instead of constructing 1 neural net, we would construct and extra 10 and at run-time 5 of the alternative nets would be evaluated. Also we would find that if the exact same image is presented twice the same result would be returned, however if even one pixel were tweaked we could get quite a different result. Some users may deem this instability to be undesirable.
Tuesday, December 11, 2018
Monday, December 3, 2018
Encryption and debit card numbers
Online retailers would like to make it as straightforward as possible for existing customers to make multiple purchases. Clearly they would like to store the credit and debit card numbers of their clientele, so when they come back, they don't need to re-enter their card details. However, when the sensitive data is stored, it might be leaked, the consequences of which would be severe. It would of course make sense to encrypt the data before saving. But to use the card number, it will need to be decrypted and so, there is a risk that the unencrypted data will be obtained by a criminal due to staff incompetence or corruption. So what should a retailer do?
One option would be to use public key encryption, but rather than use the retailer's own public key, they could use the card issuer's public key. The card number could be encrypted in the browser of the client and then sent to the retailer's server to be stored. In this case if there were some dishonest employees working for the retailer, they still wouldn't be able to decrypt the card number. When the retailer wants to request a payment from the card issuer, it can send the encrypted number and the card issuer will be able to decrypt it.
However, if it were to become standard practice for firms to use the encrypted number, then that encrypted number would be like a proxy for the original card number. In that case if it were leaked, it would once again be problematic. One way round that would be to tag the card number with the retailer ID first, before encrypting it. That encrypted data would be useless to any other retailer, corrupt or otherwise. In that case the head of information security at the retailer would sleep well at night.
All that assumes that the public key encryption of the card issuer hasn't been compromised. But just in case it has been, one option would be for the retailer to put an extra layer of encryption. On the retailer's website, it may make sense to first encrypt using the card issuer's public key and then encrypt again with the retailer's public key. The doubly encrypted data would be transmitted and then stored. Before the payment request is sent to the card issuer, the outer layer of encryption would need to be removed (decrypted).
However, if it were to become standard practice for firms to use the encrypted number, then that encrypted number would be like a proxy for the original card number. In that case if it were leaked, it would once again be problematic. One way round that would be to tag the card number with the retailer ID first, before encrypting it. That encrypted data would be useless to any other retailer, corrupt or otherwise. In that case the head of information security at the retailer would sleep well at night.
All that assumes that the public key encryption of the card issuer hasn't been compromised. But just in case it has been, one option would be for the retailer to put an extra layer of encryption. On the retailer's website, it may make sense to first encrypt using the card issuer's public key and then encrypt again with the retailer's public key. The doubly encrypted data would be transmitted and then stored. Before the payment request is sent to the card issuer, the outer layer of encryption would need to be removed (decrypted).
Tuesday, November 13, 2018
Accelerating economy
When the object is static, the position X is constant, the velocity is zero and so is the acceleration.
Now consider an economy. Economic activity can be considered to be a flow of money. Mathematically we could consider it to be the rate of change of ownership of money with respect to time.
Above we stated that acceleration is the rate of change of velocity which is the second derivative of position. Now in an economy, we can again take the second derivative of ownership of money. It is the rate of change of the flow of money. This is known as economic growth, which can of course be negative or zero. So, economic growth is the acceleration in the flow of money.
If you are trying to make long-term economic plans with the aim of maximising human welbeing, then what sort of economic growth do we want? Or to put it another way, for an optimal economy what sort of acceleration in the flow of money do we need? I would posit that at the optimal there won't be acceleration or in other words there won't be economic growth.
And that is a slightly wordy mathematical argument ( but not proof ) that, for an optimal society, there won't be economic growth.
Here's an easy question: is an accelerating object slowing down?
The answer is of course: no.
Is an economy that is growing slowing down?
Again the answer is: no.
In China, if growth goes from 6% to 4%, then is the economy slowing down?
Of course not.
When economic growth is positive, economic activity is increasing.
Monday, January 1, 2018
Musical harmony
When something that is vibrating comes in contact with the air, it can create sound which consists of compressions and decompressions of air that travel at about 343 meters per second.
We could visualise it as follows:
That image shows a simulation of a snapshot of compressions that are moving horizontally. One of the primary formulae in acoustics is: \[\lambda = \frac{c}{\nu}\] In other words the wavelength is equal to the speed of sound over the frequency.
So, if you double the frequency then you halve the wavelength.
In musical terminology, doubling the frequency is called going up one octave.
We could construct a geometric series of frequencies with: \[\nu_i = \nu_0 \alpha^i \] If we were to consider wavelengths, rather than frequencies, then we would have: \[\lambda_i = \frac{ \lambda_0 }{ \alpha^i} \] Suppose we set \(\nu_{12}\) to be one octave above \(\nu_0\),
then \[2 \large{\nu}_0 = \large{\nu}_{12} = \large{\nu}_0 \alpha^{12} \] and so, after doing a little algebra, we find: \[\alpha = 2^{ \frac{1}{12}} \] If we have 12 semitones in an octave, this might seem like a sensible choice of ratio between adjacent notes.
Now suppose we play two notes at the same time, perhaps \(\nu_0\) and \(\nu_6\). We find \[\nu_6 = \nu_0 \alpha^6 = \nu_0 \sqrt{2}\] or writing that in terms of wavelengths: \[\lambda_6 = \frac{\lambda_0} { \alpha^6} = \frac{\lambda_0} {\sqrt{2}}\] Suppose we could find two integers \(n_0\) and \(n_6\) such that \[\frac{n_0}{n_6} = \frac{\lambda_6}{\lambda_0} = \sqrt{2}\] then the pattern of interference between the two notes would repeat after
\(n_0\) cycles of the note with wavelength \(\lambda_0\) and
\(n_6\) cycles of the note with wavelength \(\lambda_6\).
Alas the problem is that \(\sqrt{2}\) is irrational so integers \(n_0\) and \(n_6\) don't exists. Hence the pattern of interference between the waves won't repeat regularly. A musician might say that they don't harmonize well.
Here is a visualiation of those two notes combining:
If you look carefully at that image, you'll see the irregularity. Those two notes combine, causing constructive and destructive interference in an irregular pattern.
Unfortunately \(2^{\frac{1}{12}} \) is also irrational. So when we use that as the ratio between adjacent semitones we are going to have a difficult time finding notes that will perfectly harmonize. ( Assuming we define harmony to be a regular repeating pattern of interference ). So it might make sense to tweak our semitones to aid harmony!
Suppose we had two notes A and B, with frequencies \(\nu_A \) and \(\nu_B \) and wavelengths \(\lambda_A \) and \(\lambda_B \) and suppose also that we can find two small integers \(n_A\) and \(n_B\) such that: \[ n_A \lambda_A = n_B \lambda_B \] and so \[ \frac{\nu_A}{n_A} = \frac{\nu_B}{n_B}\] then we will be able to find a nice harmony.
For example if we have: \[\frac{n_B}{n_A}=\frac{2}{3} = \frac{\lambda_A}{\lambda_B} = \frac{\nu_B}{\nu_A} \] then we get a nice regular pattern, which can be visualised as follows:
Note the precise repetition in that image above.
The images in this post were generated using the following R code:
We could visualise it as follows:
That image shows a simulation of a snapshot of compressions that are moving horizontally. One of the primary formulae in acoustics is: \[\lambda = \frac{c}{\nu}\] In other words the wavelength is equal to the speed of sound over the frequency.
So, if you double the frequency then you halve the wavelength.
In musical terminology, doubling the frequency is called going up one octave.
We could construct a geometric series of frequencies with: \[\nu_i = \nu_0 \alpha^i \] If we were to consider wavelengths, rather than frequencies, then we would have: \[\lambda_i = \frac{ \lambda_0 }{ \alpha^i} \] Suppose we set \(\nu_{12}\) to be one octave above \(\nu_0\),
then \[2 \large{\nu}_0 = \large{\nu}_{12} = \large{\nu}_0 \alpha^{12} \] and so, after doing a little algebra, we find: \[\alpha = 2^{ \frac{1}{12}} \] If we have 12 semitones in an octave, this might seem like a sensible choice of ratio between adjacent notes.
Now suppose we play two notes at the same time, perhaps \(\nu_0\) and \(\nu_6\). We find \[\nu_6 = \nu_0 \alpha^6 = \nu_0 \sqrt{2}\] or writing that in terms of wavelengths: \[\lambda_6 = \frac{\lambda_0} { \alpha^6} = \frac{\lambda_0} {\sqrt{2}}\] Suppose we could find two integers \(n_0\) and \(n_6\) such that \[\frac{n_0}{n_6} = \frac{\lambda_6}{\lambda_0} = \sqrt{2}\] then the pattern of interference between the two notes would repeat after
\(n_0\) cycles of the note with wavelength \(\lambda_0\) and
\(n_6\) cycles of the note with wavelength \(\lambda_6\).
Alas the problem is that \(\sqrt{2}\) is irrational so integers \(n_0\) and \(n_6\) don't exists. Hence the pattern of interference between the waves won't repeat regularly. A musician might say that they don't harmonize well.
Here is a visualiation of those two notes combining:
If you look carefully at that image, you'll see the irregularity. Those two notes combine, causing constructive and destructive interference in an irregular pattern.
Unfortunately \(2^{\frac{1}{12}} \) is also irrational. So when we use that as the ratio between adjacent semitones we are going to have a difficult time finding notes that will perfectly harmonize. ( Assuming we define harmony to be a regular repeating pattern of interference ). So it might make sense to tweak our semitones to aid harmony!
Suppose we had two notes A and B, with frequencies \(\nu_A \) and \(\nu_B \) and wavelengths \(\lambda_A \) and \(\lambda_B \) and suppose also that we can find two small integers \(n_A\) and \(n_B\) such that: \[ n_A \lambda_A = n_B \lambda_B \] and so \[ \frac{\nu_A}{n_A} = \frac{\nu_B}{n_B}\] then we will be able to find a nice harmony.
For example if we have: \[\frac{n_B}{n_A}=\frac{2}{3} = \frac{\lambda_A}{\lambda_B} = \frac{\nu_B}{\nu_A} \] then we get a nice regular pattern, which can be visualised as follows:
Note the precise repetition in that image above.
The images in this post were generated using the following R code:
# Author: Philip Kinlen, Jan 2018
library(grid) # required for grid.raster(.)
################################################################
getSinMatAB <- function( numCols, numRows,
redA1, greenA1, blueA1,
redA2, greenA2, blueA2,
redB1, greenB1, blueB1,
redB2, greenB2, blueB2,
phaseA, phaseB,
periodsA, periodsB){
xArr <- (0:(numCols-1)) / numCols
xMat <- matrix(rep(xArr, numRows), numRows, numCols, F)
alphaA <- periodsA * 2 * pi
redA <- matrix(mapply(pixelFn, xMat, phaseA, alphaA, redA1, redA2 ), numRows, numCols, T)
greenA <- matrix(mapply(pixelFn, xMat, phaseA, alphaA, greenA1, greenA2 ), numRows, numCols, T)
blueA <- matrix(mapply(pixelFn, xMat, phaseA, alphaA, blueA1, blueA2 ), numRows, numCols, T)
alphaB <- periodsB * 2 * pi
redB <- matrix(mapply(pixelFn, xMat, phaseB, alphaB, redB1, redB2 ), numRows, numCols, T)
greenB <- matrix(mapply(pixelFn, xMat, phaseB, alphaB, greenB1, greenB2 ), numRows, numCols, T)
blueB <- matrix(mapply(pixelFn, xMat, phaseB, alphaB, blueB1, blueB2 ), numRows, numCols, T)
red <- 0.5 * ( redA + redB )
green <- 0.5 * ( greenA + greenB )
blue <- 0.5 * ( blueA + blueB )
img <- rgb(red, green, blue)
dim(img) <- dim(red)
return ( img )
}
################################################################
pixelFn <- function (z, phase, alpha, val1, val2){
return ( val1 + (val2 - val1) * ( sin ( phase + z * alpha) + 1) * 0.5 )
}
################################################################
plotSin <- function () {
numCols <- 1000
numRows <- 200
## colors are in the range 0 to 1 inclusive.
redA1 <- 1
greenA1 <- 1
blueA1 <- 1
redA2 <- 0
greenA2 <- 0
blueA2 <- 0
redB1 <- 1
greenB1 <- 1
blueB1 <- 1
redB2 <- 0
greenB2 <- 0
blueB2 <- 0
phaseA <- pi
phaseB <- pi
wavelengthRatio <- sqrt(2)
periodsA <- 15
periodsB <- periodsA * wavelengthRatio
img <- getSinMatAB ( numCols, numRows,
redA1, greenA1, blueA1,
redA2, greenA2, blueA2,
redB1, greenB1, blueB1,
redB2, greenB2, blueB2,
phaseA, phaseB,
periodsA, periodsB)
doSmoothing <- F
grid.raster(img, interpolate=doSmoothing)
}
################################################################
Monday, November 27, 2017
Photographing the horizon
Suppose you are on an island, looking out to see, how far away is the horizon?
We can approximate the earth as a sphere and apply pythagorous' theorem, then we find: \[ d^2 + r^2 = (h + r )^2 \] So the distance to the horizon is: \[d = \sqrt{h(h + 2r)}\] and the distance along the surface at sea level is: \[d_s = r \hspace{2 mm} sin^{-1} \left( \frac{d}{h+r} \right) \] Try out different heights to see the distance of the horizon. Also set the photo angle ( defined below ) to see the curvature of the horizon in a photo.
If we apply pythagorous a couple of times to the diagram above and then do a bit of algebra, we find: \[g = \frac{d^2 - h^2}{2(r+h)}\] and \[ f = \sqrt{g ( 2r - g)}\]
Now suppose we take a photo of the horizon, what shape will the horizon appear to be when we have rendered the image? We will use the same ideas we used in the previous post Straight Lines in photos
The horizon will be a section of a cirle of radius f in a plane a distance h+g below the observer. When we point a camera horizontally and take a photo of the horizon, we assume that an image of that photo can be rendered on a screen a distance \(\nu\) from the observer, for whom all objects in the photo perfectly align with the real objects. Consider the cone which consists of the horizon circle at the base and with a vertex at the observer. The image of the horizon will be the intersection of the plane containing the screen and the cone. This is known as a conic section.
On the cone we have the equation: \[x^2_1 + x^2_3 = \rho^2\] The height of the cone is h+g and so, comparing similar triangles: \[ \frac{\rho}{x_2} = \frac{f}{h+g}\] Combining those two equations we find: \[ x^2_1 + x^2_3 = \frac{x^2_2 f^2 }{(h+g)^2} \] Now we are interested in intersection of that cone with the screen in the plane \(x_3 = \nu\)
We find \[x_2 = - \frac{h+g}{f} \sqrt{x^2_1 + \nu^2}\] That is an equation for a hyperbola. So the horizon will be a hyperbola.
We now have an expression for \(x_2\) in terms of \(x_1\), we could say that \(x_2\) is a function of \(x_1\) which we could write \(x_2(x_1)\)
We'll define \(\theta\) to be the angle in the horizontal plane from the centre of the screen to either vertical edge ( for the observer ).
We find: \[x_2( \nu tan(\theta)) = - \frac{h+g}{f} \nu \sqrt{1+tan^2(\theta)} \] and thus \[x_2( \nu tan(\theta)) = - \frac{(h+g) \nu}{f cos(\theta)} \] We define: \[\epsilon = x_2( 0 ) - x_2( \nu tan( \theta )) \] and then we measure the curvature of the horizon in the photo to be: \[\kappa = \frac{\epsilon}{\nu tan(\theta)}\] and we find: \[\kappa = \frac{(h+g)}{f} \frac{ (1-cos(\theta))}{sin(\theta)}\]
We can approximate the earth as a sphere and apply pythagorous' theorem, then we find: \[ d^2 + r^2 = (h + r )^2 \] So the distance to the horizon is: \[d = \sqrt{h(h + 2r)}\] and the distance along the surface at sea level is: \[d_s = r \hspace{2 mm} sin^{-1} \left( \frac{d}{h+r} \right) \] Try out different heights to see the distance of the horizon. Also set the photo angle ( defined below ) to see the curvature of the horizon in a photo.
| Height above sea level | meters | |
| Distance to horizon | km | |
| Distance along surface | km | Theta (photo angle) | degrees |
| Horizon curvature | % |
If we apply pythagorous a couple of times to the diagram above and then do a bit of algebra, we find: \[g = \frac{d^2 - h^2}{2(r+h)}\] and \[ f = \sqrt{g ( 2r - g)}\]
Now suppose we take a photo of the horizon, what shape will the horizon appear to be when we have rendered the image? We will use the same ideas we used in the previous post Straight Lines in photos
The horizon will be a section of a cirle of radius f in a plane a distance h+g below the observer. When we point a camera horizontally and take a photo of the horizon, we assume that an image of that photo can be rendered on a screen a distance \(\nu\) from the observer, for whom all objects in the photo perfectly align with the real objects. Consider the cone which consists of the horizon circle at the base and with a vertex at the observer. The image of the horizon will be the intersection of the plane containing the screen and the cone. This is known as a conic section.
On the cone we have the equation: \[x^2_1 + x^2_3 = \rho^2\] The height of the cone is h+g and so, comparing similar triangles: \[ \frac{\rho}{x_2} = \frac{f}{h+g}\] Combining those two equations we find: \[ x^2_1 + x^2_3 = \frac{x^2_2 f^2 }{(h+g)^2} \] Now we are interested in intersection of that cone with the screen in the plane \(x_3 = \nu\)
We find \[x_2 = - \frac{h+g}{f} \sqrt{x^2_1 + \nu^2}\] That is an equation for a hyperbola. So the horizon will be a hyperbola.
We now have an expression for \(x_2\) in terms of \(x_1\), we could say that \(x_2\) is a function of \(x_1\) which we could write \(x_2(x_1)\)
We'll define \(\theta\) to be the angle in the horizontal plane from the centre of the screen to either vertical edge ( for the observer ).
We find: \[x_2( \nu tan(\theta)) = - \frac{h+g}{f} \nu \sqrt{1+tan^2(\theta)} \] and thus \[x_2( \nu tan(\theta)) = - \frac{(h+g) \nu}{f cos(\theta)} \] We define: \[\epsilon = x_2( 0 ) - x_2( \nu tan( \theta )) \] and then we measure the curvature of the horizon in the photo to be: \[\kappa = \frac{\epsilon}{\nu tan(\theta)}\] and we find: \[\kappa = \frac{(h+g)}{f} \frac{ (1-cos(\theta))}{sin(\theta)}\]
Friday, November 24, 2017
Stright lines in photos
In this post, I'll give a mathematical justification for the following statements about photos of line segments:
1: The photo of a straight line segment will be a straight line segment.
2: If the line segment is in a plane perpendicular to the direction that the camera is pointing, then the slope of the line in the photo will be the same as it is in reality.
As a result, if a camera is pointing in a horizontal direction, then vertical lines ( and vertical edges of objects ) will be vertical in the photo. Also a horizontal line which is in the plane perpendicular to the direction the camera is pointing will be horizontal in the photo.
I will show that those statements are true for regular photos, i.e. for photos which, when rendered as an image, maintain the original orientation, for an observer located in a particular location.
Consider a static image that is taken with a camera. We'll label the direction the camera is pointing as the \( x_3 \) axis. Suppose we render the image on a screen perpendicular to the \( x_3 \) asix, a distance \( \nu \) from the observer. The image of a point will the be rendered on the screen precisely in the spot that is covering the original point.
With 3 dimensional coordinates, we'll specify the position of the observer to be at the origin. The screen is in the pane \(x_3 = \nu \)
The \(x_1 \) axis is parallel to the ground and the \( x_2 \) axis is perpendicular to both \( x_1 \) and \( x_3 \).
When the camera is pointing in the horizontal plane, \( x_2 \) is vertical.
If the object is at \( \underline{x}^a = ( x_1^a , x_2^a, x_3^a ) \)
then the image should be somewhere along the line from the origin 0 to \( \underline{x}^a \)
In other words, for some real number \( \alpha \), the location of the images is given by: \[ Image(\underline{x}^a) =\underline{x}^a \alpha = ( x_1^a , x_2^a , x_3^a ) \alpha \] The image is on the screen so \[ \nu = x_3^a \alpha \] and so \[ \alpha = \frac{\nu}{x_3^a} \] hence \[ Image(\underline{x}^a) = ( \frac{x_1^a}{x_3^a} , \frac{x_2^a}{x_3^a} , 1 ) \nu \] Now suppose we had a line segment running from \( \underline{x}^a \) to \( \underline{x}^b \)
Let \( \underline{x}^{\lambda} \) be a point on that line segment such that: \[ \underline{x}^{\lambda} = \underline{x}^a ( 1 - \lambda) + \underline{x}^b \lambda \] where \( 0 \le \lambda \le 1\)
So \[ Image(\underline{x}^{\lambda}) = \left( \frac{x^a_1 (1 - \lambda ) + x^b_1 \lambda }{x^a_3 (1 - \lambda ) + x^b_3 \lambda} , \frac{x^a_2 (1 - \lambda ) + x^b_2 \lambda }{x^a_3 (1 - \lambda ) + x^b_3 \lambda} , 1 \right) \nu \] If we let \[ \beta =\frac{ x^b_3 \lambda}{x^a_3 (1 - \lambda ) + x^b_3 \lambda} \] then after doing some algebra we find: \[ Image(\underline{x}^{\lambda}) = \left( \frac{x^a_1}{x^a_3} ( 1 - \beta) + \frac{x^b_1}{x^b_3} \beta , \frac{x^a_2}{x^a_3} ( 1 - \beta) + \frac{x^b_2}{x^b_3} \beta , 1 \right) \nu \] And as we vary \( \lambda \), \( \beta \) changes and the image traces out a line segment on the screen from \( ( \frac{x^a_1}{x^a_3} , \frac{x^a_2}{x^a_3}, 1 ) \nu \) to \( ( \frac{x^b_1}{x^b_3} , \frac{x^b_2}{x^b_3}, 1 ) \nu \)
So we have shown that in our model, the image of a straight line segment is a straight line segment.
It took some effort using algebra to get to that statement. It turns out we could have arrived at that statement using some geometry. The image of the line segment from \( \underline{x}^a\) to \( \underline{x}^b\) will be along the intersection of the plain \( x_3 = \nu \) and the plane containing \( \underline{x}^a\), \( \underline{x}^b\) and the origin. The intersection of two planes is a line and so the image of the straight line segment will be a straight line segment.
Again let us consider the image of a line segment from \( \underline{x}^a\) to \( \underline{x}^b\) but this time let's assume that both \( \underline{x}^a\) and \( \underline{x}^b\) are equidistant from the plane containing the screen at \( x_3 = \nu \).
So \[ x^a_3 = x^b_3 \] In this case, the image will be rendered along the line segment from \( \left( \frac{x_1^a}{x^a_3}, \frac{x_2^a}{x^a_3} , 1 \right) \nu \)
to \( \left( \frac{x_1^b}{x^a_3}, \frac{x_2^b}{x^a_3} , 1 \right) \nu \)
Ignoring for a moment the \( x_3 \) axis, we find the slope of the line segment from \( \underline{x}^a\) to \( \underline{x}^b\), in the \( x_1 \) , \(x_2 \) plane is: \[ slope_{12}( \underline{x}^a, \underline{x}^b) = \frac{x^b_2 - x^a_2}{x^b_1 - x^a_1} \] which is the same as the slope of the line segment from \( Image( \underline{x}^a ) \) to \( Image( \underline{x}^b ) \).
So in this case the slope is preserved.
From a practical point of view, if a camera is pointing in the horizontal plane and it is used to take a photo of a building with some vertical lines, then those vertical lines will be preserved in the photo.
The image of a horizontal line segment which is parallel to the \( x_3 = \nu \) pane ( parallel to the screen ), will be rendered as a horizontal line in the photo.
So if you take a photo with the camera pointing perpendicularly at a wall, then horizontal lines on that wall will be horizontal lines in the photo.
If you are perpendicular to a flat straight road, then a line at the edge of a road will appear as horizontal, going across a photo.
On the other hand, if the photographer is very close to a building and points the camera upwards, then the real vertical axis will not be parallel to the \( x_2 \) axis and so a real-life vertical line, may not appear to be vertical in the photo. In fact the building may appear to lean back in the photo.
All bets are off when a fish-eye lens is used and then the image is rendered on a flat screen. The objects in the image will not be aligned with the real objects and you may observe straight lines to appear to become curved in the photo.
1: The photo of a straight line segment will be a straight line segment.
2: If the line segment is in a plane perpendicular to the direction that the camera is pointing, then the slope of the line in the photo will be the same as it is in reality.
As a result, if a camera is pointing in a horizontal direction, then vertical lines ( and vertical edges of objects ) will be vertical in the photo. Also a horizontal line which is in the plane perpendicular to the direction the camera is pointing will be horizontal in the photo.
I will show that those statements are true for regular photos, i.e. for photos which, when rendered as an image, maintain the original orientation, for an observer located in a particular location.
Consider a static image that is taken with a camera. We'll label the direction the camera is pointing as the \( x_3 \) axis. Suppose we render the image on a screen perpendicular to the \( x_3 \) asix, a distance \( \nu \) from the observer. The image of a point will the be rendered on the screen precisely in the spot that is covering the original point.
With 3 dimensional coordinates, we'll specify the position of the observer to be at the origin. The screen is in the pane \(x_3 = \nu \)
The \(x_1 \) axis is parallel to the ground and the \( x_2 \) axis is perpendicular to both \( x_1 \) and \( x_3 \).
When the camera is pointing in the horizontal plane, \( x_2 \) is vertical.
If the object is at \( \underline{x}^a = ( x_1^a , x_2^a, x_3^a ) \)
then the image should be somewhere along the line from the origin 0 to \( \underline{x}^a \)
In other words, for some real number \( \alpha \), the location of the images is given by: \[ Image(\underline{x}^a) =\underline{x}^a \alpha = ( x_1^a , x_2^a , x_3^a ) \alpha \] The image is on the screen so \[ \nu = x_3^a \alpha \] and so \[ \alpha = \frac{\nu}{x_3^a} \] hence \[ Image(\underline{x}^a) = ( \frac{x_1^a}{x_3^a} , \frac{x_2^a}{x_3^a} , 1 ) \nu \] Now suppose we had a line segment running from \( \underline{x}^a \) to \( \underline{x}^b \)
Let \( \underline{x}^{\lambda} \) be a point on that line segment such that: \[ \underline{x}^{\lambda} = \underline{x}^a ( 1 - \lambda) + \underline{x}^b \lambda \] where \( 0 \le \lambda \le 1\)
So \[ Image(\underline{x}^{\lambda}) = \left( \frac{x^a_1 (1 - \lambda ) + x^b_1 \lambda }{x^a_3 (1 - \lambda ) + x^b_3 \lambda} , \frac{x^a_2 (1 - \lambda ) + x^b_2 \lambda }{x^a_3 (1 - \lambda ) + x^b_3 \lambda} , 1 \right) \nu \] If we let \[ \beta =\frac{ x^b_3 \lambda}{x^a_3 (1 - \lambda ) + x^b_3 \lambda} \] then after doing some algebra we find: \[ Image(\underline{x}^{\lambda}) = \left( \frac{x^a_1}{x^a_3} ( 1 - \beta) + \frac{x^b_1}{x^b_3} \beta , \frac{x^a_2}{x^a_3} ( 1 - \beta) + \frac{x^b_2}{x^b_3} \beta , 1 \right) \nu \] And as we vary \( \lambda \), \( \beta \) changes and the image traces out a line segment on the screen from \( ( \frac{x^a_1}{x^a_3} , \frac{x^a_2}{x^a_3}, 1 ) \nu \) to \( ( \frac{x^b_1}{x^b_3} , \frac{x^b_2}{x^b_3}, 1 ) \nu \)
So we have shown that in our model, the image of a straight line segment is a straight line segment.
It took some effort using algebra to get to that statement. It turns out we could have arrived at that statement using some geometry. The image of the line segment from \( \underline{x}^a\) to \( \underline{x}^b\) will be along the intersection of the plain \( x_3 = \nu \) and the plane containing \( \underline{x}^a\), \( \underline{x}^b\) and the origin. The intersection of two planes is a line and so the image of the straight line segment will be a straight line segment.
Again let us consider the image of a line segment from \( \underline{x}^a\) to \( \underline{x}^b\) but this time let's assume that both \( \underline{x}^a\) and \( \underline{x}^b\) are equidistant from the plane containing the screen at \( x_3 = \nu \).
So \[ x^a_3 = x^b_3 \] In this case, the image will be rendered along the line segment from \( \left( \frac{x_1^a}{x^a_3}, \frac{x_2^a}{x^a_3} , 1 \right) \nu \)
to \( \left( \frac{x_1^b}{x^a_3}, \frac{x_2^b}{x^a_3} , 1 \right) \nu \)
Ignoring for a moment the \( x_3 \) axis, we find the slope of the line segment from \( \underline{x}^a\) to \( \underline{x}^b\), in the \( x_1 \) , \(x_2 \) plane is: \[ slope_{12}( \underline{x}^a, \underline{x}^b) = \frac{x^b_2 - x^a_2}{x^b_1 - x^a_1} \] which is the same as the slope of the line segment from \( Image( \underline{x}^a ) \) to \( Image( \underline{x}^b ) \).
So in this case the slope is preserved.
From a practical point of view, if a camera is pointing in the horizontal plane and it is used to take a photo of a building with some vertical lines, then those vertical lines will be preserved in the photo.
The image of a horizontal line segment which is parallel to the \( x_3 = \nu \) pane ( parallel to the screen ), will be rendered as a horizontal line in the photo.
So if you take a photo with the camera pointing perpendicularly at a wall, then horizontal lines on that wall will be horizontal lines in the photo.
If you are perpendicular to a flat straight road, then a line at the edge of a road will appear as horizontal, going across a photo.
On the other hand, if the photographer is very close to a building and points the camera upwards, then the real vertical axis will not be parallel to the \( x_2 \) axis and so a real-life vertical line, may not appear to be vertical in the photo. In fact the building may appear to lean back in the photo.
All bets are off when a fish-eye lens is used and then the image is rendered on a flat screen. The objects in the image will not be aligned with the real objects and you may observe straight lines to appear to become curved in the photo.
Saturday, April 1, 2017
Efficient machine learning
Suppose we have a set of data from which we wish to train a machine learning algorithm and the data keeps growing and growing. We'd like an efficient algorithm that will put more weight on the recent results and we would like it to be straight forward to keep up dated, even if we have hundreds of millions of rows of data. What can we do?
Well, in this post I will suggest an algorithm that is very efficient at dealing with large data sets. It can learn from old data, but it doesn't need the old data to be stored.
Let's start with the basics. Suppose we have a set of T input vectors \(\underline{x}^t \in \mathbb{R}^n\) with \[1 \le t \le T\] and for each \(\underline{x}^t\) there is a resultant \(y^t \in \mathbb{R} \).
We want to find the optimal vector \(\underline{\theta}\) so that \( \underline{\theta } . \underline{x}^t \) is a good predictor of \( y^t \).
We choose the \(\underline{\theta}\) which minimises the cost function: \[ J( \underline{\theta} ) = \frac{1}{2T} \sum^{T}_{t=1} ( \underline{\theta} . \underline{x}^t -y^t)^2 \] We could expand the inner product \( \underline{\theta} . \underline{x}^t \), which would give us: \[ J( \underline{\theta} ) = \frac{1}{2T} \sum^{T}_{t=1} \big[ \sum_{j=1}^n ( \theta_j x^t_j ) -y^t \big]^2 \] When we have an optimal \( \underline{\theta} \), the partial derivatives of J will be zero: \[ 0 = \frac{\partial J}{ \partial \theta_i} = \frac{1}{T} \sum^{T}_{t=1} x_i^t \big[ \sum_{j=1}^n ( \theta_j x^t_j ) -y^t \big] \] We can change the order of the summation and do some rearranging to obtain: \[ 0 = \sum_{j=1}^n \big[ \frac{1}{T} \sum_{t=1}^T ( x^t_i x^t_j ) \theta_j \big] - \frac{1}{T} \sum_{t=1}^T ( y^t x_i^t) \hspace{24 mm} (eqn 1) \] Now, if we define the matrix \(\underline{A}\): \[ A_{ij} = \frac{1}{T} \sum_{t=1}^T ( x^t_i x^t_j ) \hspace{24 mm} (eqn 2) \] and we define vector \(\underline{B}\) \[ B_i = \frac{1}{T} \sum_{t=1}^T ( y^t x_i^t) \hspace{24 mm} (eqn 3) \] Plugging those into equation 1, we find: \[ 0 = \sum_{j=1}^n \big[ A_{ij} \theta_j \big] - B_i \] If we can invert the matrix \(\underline{A}\) then we can obtain \( \theta \) \[ \underline{\theta} = \underline{A}^{-1} \underline{B} \] If we look back at equation 2, we see that each vector \( \underline{x}^t\) effectively has the same weighting.
We could rewrite equations 2 and 3 as: \[ A_{ij} = \sum_{t=1}^T ( x^t_i x^t_j \omega_t) \hspace{24 mm} (eqn 4) \] and \[ B_i = \sum_{t=1}^T ( y^t x^t_i \omega_t) \hspace{24 mm} (eqn 5) \] where \[ \omega_t = \frac{1}{T} \hspace{24 mm} \forall t: 1 \le t \le T \] However, suppose we wanted more recent values of \( \underline{x}^t\) to have higher weighting. We could fix the ratio of consecutive weights: \[ \frac{\omega_{t+1}}{\omega_t} = 1 + \lambda \] with \( \lambda > 0\)
So we would have: \[ \omega_t = \frac{\omega_T} { (1+\lambda)^{T-t}} \] Suppose want to find the speed at which the weight drops down to half the weight of the most recently added entry, then we would seek \(\tau\) such that \[ \frac{\omega_T}{\omega_{T - \tau}} = 2 \] which implies: \[ (1 + \lambda)^{\tau} = 2 \] so: \[ \lambda = 2^{1/ \tau } -1 \hspace{24 mm} (eqn 6) \] So, if we want the most recent data to have double the weighting of a point 1,000 rows back, then we would set \(\tau = 1000 \) and use equation 6 to determine \( \lambda \).
The parameter \( \lambda \) determines how much bigger the weights of the recent data will have, when compared with older data. When choosing it, it may be helpful to first choose \( \tau\) ( which is something like a half-life ) and then use equation 6 to evaluate \( \lambda \)
If we wish to preserve the condition that the sum of the weights is 1, then we can do the geometric sum and after a little algebra we find that: \[ \omega_T = \frac{\lambda}{(1+\lambda)^T-1} \hspace{24 mm} (eqn 7) \]
For a given set of \(\underline{x}^t \) and \(y^t\) with \(1 \le t \le T \)
we can evaluate \(\underline{A} \) and \( \underline{B}\).
Since they were generated with T rows of data, we could label them \(\underline{A}^T \) and \( \underline{B}^T\).
Now suppose we have already evaluated \(\underline{A}^{(T-1)} \) and \( \underline{B}^{(T-1)}\)
with T-1 rows of data and we want to introduce one more,
then we find: \[ A^T_{ij} = \omega_T x^T_i x^T_j + ( 1 - \omega_T ) A^{(T-1)}_{ij} \hspace{24 mm} (eqn 8) \] and \[ B^T_i = \omega_T y^T x^T_i + ( 1 - \omega_T ) B^{(T-1)}_i \hspace{24 mm} (eqn 9) \] where \( \omega_T \) has been defined in equation 7.
So when we have evaluated \( \underline{A} \) and \( \underline{B} \) for a given set of data and then later want to include the contribution from a new \( \underline{x}^T \) and \( y^T \), we can amend the existing \( \underline{A} \) and \( \underline{B} \) using equations 8 and 9, without the need to retrieve all the past \( \underline{x}^t \) and \( y^t \).
As a result, when data ( \( \underline{x}^T \) and \( y^T \) ) comes in, we can use it to update \( \underline{A} \) and \( \underline{B} \) and then we can discard the \( \underline{x}^T \) and \( y^T \). They have made their contribution to \( \underline{A} \) and \( \underline{B} \) and we can continually update \( \underline{A} \) and \( \underline{B} \) without the need to look back at old values of \( \underline{x}^t \) and \( y^t \). When T is very large, say in the hundreds of millions, using this algorithm to continually update the machine learning results is rather efficient. Since we don't need to keep retrieving the old data. We just keep the \( \underline{A} \) and \( \underline{B} \) up to date.
Let's start with the basics. Suppose we have a set of T input vectors \(\underline{x}^t \in \mathbb{R}^n\) with \[1 \le t \le T\] and for each \(\underline{x}^t\) there is a resultant \(y^t \in \mathbb{R} \).
We want to find the optimal vector \(\underline{\theta}\) so that \( \underline{\theta } . \underline{x}^t \) is a good predictor of \( y^t \).
We choose the \(\underline{\theta}\) which minimises the cost function: \[ J( \underline{\theta} ) = \frac{1}{2T} \sum^{T}_{t=1} ( \underline{\theta} . \underline{x}^t -y^t)^2 \] We could expand the inner product \( \underline{\theta} . \underline{x}^t \), which would give us: \[ J( \underline{\theta} ) = \frac{1}{2T} \sum^{T}_{t=1} \big[ \sum_{j=1}^n ( \theta_j x^t_j ) -y^t \big]^2 \] When we have an optimal \( \underline{\theta} \), the partial derivatives of J will be zero: \[ 0 = \frac{\partial J}{ \partial \theta_i} = \frac{1}{T} \sum^{T}_{t=1} x_i^t \big[ \sum_{j=1}^n ( \theta_j x^t_j ) -y^t \big] \] We can change the order of the summation and do some rearranging to obtain: \[ 0 = \sum_{j=1}^n \big[ \frac{1}{T} \sum_{t=1}^T ( x^t_i x^t_j ) \theta_j \big] - \frac{1}{T} \sum_{t=1}^T ( y^t x_i^t) \hspace{24 mm} (eqn 1) \] Now, if we define the matrix \(\underline{A}\): \[ A_{ij} = \frac{1}{T} \sum_{t=1}^T ( x^t_i x^t_j ) \hspace{24 mm} (eqn 2) \] and we define vector \(\underline{B}\) \[ B_i = \frac{1}{T} \sum_{t=1}^T ( y^t x_i^t) \hspace{24 mm} (eqn 3) \] Plugging those into equation 1, we find: \[ 0 = \sum_{j=1}^n \big[ A_{ij} \theta_j \big] - B_i \] If we can invert the matrix \(\underline{A}\) then we can obtain \( \theta \) \[ \underline{\theta} = \underline{A}^{-1} \underline{B} \] If we look back at equation 2, we see that each vector \( \underline{x}^t\) effectively has the same weighting.
We could rewrite equations 2 and 3 as: \[ A_{ij} = \sum_{t=1}^T ( x^t_i x^t_j \omega_t) \hspace{24 mm} (eqn 4) \] and \[ B_i = \sum_{t=1}^T ( y^t x^t_i \omega_t) \hspace{24 mm} (eqn 5) \] where \[ \omega_t = \frac{1}{T} \hspace{24 mm} \forall t: 1 \le t \le T \] However, suppose we wanted more recent values of \( \underline{x}^t\) to have higher weighting. We could fix the ratio of consecutive weights: \[ \frac{\omega_{t+1}}{\omega_t} = 1 + \lambda \] with \( \lambda > 0\)
So we would have: \[ \omega_t = \frac{\omega_T} { (1+\lambda)^{T-t}} \] Suppose want to find the speed at which the weight drops down to half the weight of the most recently added entry, then we would seek \(\tau\) such that \[ \frac{\omega_T}{\omega_{T - \tau}} = 2 \] which implies: \[ (1 + \lambda)^{\tau} = 2 \] so: \[ \lambda = 2^{1/ \tau } -1 \hspace{24 mm} (eqn 6) \] So, if we want the most recent data to have double the weighting of a point 1,000 rows back, then we would set \(\tau = 1000 \) and use equation 6 to determine \( \lambda \).
The parameter \( \lambda \) determines how much bigger the weights of the recent data will have, when compared with older data. When choosing it, it may be helpful to first choose \( \tau\) ( which is something like a half-life ) and then use equation 6 to evaluate \( \lambda \)
If we wish to preserve the condition that the sum of the weights is 1, then we can do the geometric sum and after a little algebra we find that: \[ \omega_T = \frac{\lambda}{(1+\lambda)^T-1} \hspace{24 mm} (eqn 7) \]
For a given set of \(\underline{x}^t \) and \(y^t\) with \(1 \le t \le T \)
we can evaluate \(\underline{A} \) and \( \underline{B}\).
Since they were generated with T rows of data, we could label them \(\underline{A}^T \) and \( \underline{B}^T\).
Now suppose we have already evaluated \(\underline{A}^{(T-1)} \) and \( \underline{B}^{(T-1)}\)
with T-1 rows of data and we want to introduce one more,
then we find: \[ A^T_{ij} = \omega_T x^T_i x^T_j + ( 1 - \omega_T ) A^{(T-1)}_{ij} \hspace{24 mm} (eqn 8) \] and \[ B^T_i = \omega_T y^T x^T_i + ( 1 - \omega_T ) B^{(T-1)}_i \hspace{24 mm} (eqn 9) \] where \( \omega_T \) has been defined in equation 7.
So when we have evaluated \( \underline{A} \) and \( \underline{B} \) for a given set of data and then later want to include the contribution from a new \( \underline{x}^T \) and \( y^T \), we can amend the existing \( \underline{A} \) and \( \underline{B} \) using equations 8 and 9, without the need to retrieve all the past \( \underline{x}^t \) and \( y^t \).
As a result, when data ( \( \underline{x}^T \) and \( y^T \) ) comes in, we can use it to update \( \underline{A} \) and \( \underline{B} \) and then we can discard the \( \underline{x}^T \) and \( y^T \). They have made their contribution to \( \underline{A} \) and \( \underline{B} \) and we can continually update \( \underline{A} \) and \( \underline{B} \) without the need to look back at old values of \( \underline{x}^t \) and \( y^t \). When T is very large, say in the hundreds of millions, using this algorithm to continually update the machine learning results is rather efficient. Since we don't need to keep retrieving the old data. We just keep the \( \underline{A} \) and \( \underline{B} \) up to date.
Subscribe to:
Posts (Atom)