Sunday, August 31, 2014

Tips for LaTeX

So I used LaTeX using Texmaker in order to do my thesis. Here are some tips worth sharing.

Bibliography
For bibliography use BibTeX since you'll find BibTeX citations all over the Internet and use JabRef to edit the bibliographic details. Unfortunately the default for rendering citations is number in square brackets type like [1]. This might not be your preferred option as it doesn't show any information about what you're citing (although its great to save space in your text). If you want to use the "(author, year)" type of citation like "(Smith, 2014)" you'll need to use "\usepackage[round]{natbib}" in your preamble and then use "\pcite{}" instead of "\cite{}" to insert citations.

Unicode
Unless you're writing only in pure English, you'll often need to use non-ASCII characters. The LaTeX compiler doesn't let you compile non-ASCII text but allows you to make these characters using codes like \'{o}; however they make the text unreadable when used frequently. Instead you can type your text using unicode and then compile using XeLaTeX which allows you to compile unicode text.

Single line compilation
LaTeX requires multiple compilations to get a final product. So, if using command line commands, you'll need to enter something like this to have a bibliography in your document:
latex x.tex
bibtex x.tex
latex x.tex

In order to get around this, IDEs such as Texmaker allow you to customize a compilation button to make it run a command line instruction of your choice. In Linux you can use | to combine multiple instructions in one line (use && in Windows). Here is how I was doing my compilation in the Texmaker quick build function:

xelatex -synctex=1 -interaction=nonstopmode %.tex|makeindex %.idx|bibtex %.aux|makeindex %.nlo -s nomencl.ist -o %.nls|xelatex -synctex=1 -interaction=nonstopmode %.tex|xelatex -synctex=1 -interaction=nonstopmode %.tex

Notice that in Texmaker "%" means the file name of the main LaTeX source file.

Overfull/underfull hbox error handling
LaTeX has a rather poor handling of word wrap and often needs some help from you. When this happens, it gives you an overful hbox or underfull hbox error, depending on whether a line in the text is too long or too short. To fix it you need to either reword the words in the offending line (yes it's normal in the LaTeX community), or you add hyphenation marks using "\-" inside long words such as "ele\-phant". This tells LaTeX where to split a word if it occurs at the end of a line. LaTeX usually does this on its own but if it's an unknown word you'll need to help it.

Overfull/underfull hbox error handling on URLs
Long URLs are particularly problematic in LaTeX because you cannot hyphenate them as the hyphen might be thought to be part of the link. I found that the best way to handle it is to just line break the URL using "\\". Here's an example:

\href{http://www.url.com/very/very/very/very/very/long}{http://www.url.com/very/\\very/very/very/\\very/long}}

In this way you'll be telling LaTeX where to split the URL without adding hyphens.

Tables
Ouch. Tables are quite nightmare in LaTeX since you get no word wrapping in the table cells. You can fix this by putting your text in a par box which wraps words by itself and then putting this par box in the table cells here's the inefficient way to do this:

\begin{table}
 \begin{center}
  \begin{tabular}{ccc}
   \hline
   
    \parbox[t][][t]{2cm}{
     \begin{flushleft}\vspace{-0.3cm}Title 1\vspace{-0.3cm}\end{flushleft}
    }
    &
    \parbox[t][][t]{4cm}{
     \begin{center}\vspace{-0.3cm}Title 2\vspace{-0.3cm}\end{center}
    }
    &
    \parbox[t][][t]{6cm}{
     \begin{flushright}\vspace{-0.3cm}Title 3\vspace{-0.3cm}\end{flushright}
    }
    
   \\ \hline

    \parbox[t][][t]{2cm}{
     \begin{flushleft}\vspace{-0.3cm}Data 1\vspace{-0.3cm}\end{flushleft}
    }
    &
    \parbox[t][][t]{4cm}{
     \begin{center}\vspace{-0.3cm}Data 2\vspace{-0.3cm}\end{center}
    }
    &
    \parbox[t][][t]{6cm}{
     \begin{flushright}\vspace{-0.3cm}Data 3\vspace{-0.3cm}\end{flushright}
    }

   \\ \hline
  \end{tabular}
 \end{center}
 \caption{A caption about this table.}
 \label{tbl:some_identifier_to_refer_to_this_table}
\end{table}

This will make the table have the first column be left aligned 2cm wide, the second centred 4cm, and the third right aligned 6cm. The \vspace is there to keep the rows from being too big. Of course the problem with this approach is if you need to change the width or alignment of a column, in which case using custom commands would be the best way forward:

\newcommand{\col1}[1] {
 \parbox[t][][t]{2cm}{
  \begin{flushleft}\vspace{-0.3cm}#1\vspace{-0.3cm}\end{flushleft}
 }
}
\newcommand{\col2}[1] {
 \parbox[t][][t]{4cm}{
  \begin{center}\vspace{-0.3cm}#1\vspace{-0.3cm}\end{center}
 }
}
\newcommand{\col3}[1] {
 \parbox[t][][t]{6cm}{
  \begin{flushright}\vspace{-0.3cm}#1\vspace{-0.3cm}\end{flushright}
 }
}

\begin{table}
 \begin{center}
  \begin{tabular}{ccc}
   \hline
   
    \col1{Title 1}
    &
    \col2{Title 2}
    &
    \col3{Title 3}
    
   \\ \hline

    \col1{Data 1}
    &
    \col2{Data 2}
    &
    \col3{Data 3}

   \\ \hline
  \end{tabular}
 \end{center}
 \caption{A caption about this table.}
 \label{tbl:some_identifier_to_refer_to_this_table}
\end{table}

Commands are very useful for repetitive code in LaTeX but you need to use a different name for each different table; otherwise you'll need to use \renewcommand instead of \newcommand.

Positioning images and tables (floats)
I used to think that LaTeX intelligently places my floats at the best, most sensible place, but no it does not. It places them in the middle of bullet points without feeling guilty if you place your \begin{table} or \being{figure} anywhere near them. So what I did was that I placed the floats where ever it was sensible myself and then forced LaTeX to do it by surrounding the float with "\FloatBarrier" which requires "\usepackage{placeins}" in the preamble.

Thursday, July 24, 2014

Shape of the Universe

At the moment I'm reading A Universe From Nothing by Lawrence Krauss and there's a section which talks about the shape of the universe. So what does it mean for the universe to have a shape?

Let's imagine a flat 2D universe. What this means is that things can move left, right, forward, and backward but not up and down. Everything is flat, as shown in this picture:



Now think of this universe as a bed sheet. The sheet may be laid on the floor, in which case it would have a flat shape, but it might be placed on some curved surface, such as a ball.



Is there a way for the inhabitants of such a spherical universe to know that their universe is a sphere? Yes. By using triangles. A triangle in a flat universe follows Euclidian geometry rules, such as that the sum of its angles add up to 180 degrees, but what about on the surface of a sphere?

On a sphere, it is actually possible to draw a triangle consisting of three 90 degree angles. Divide the sphere into 8 quadrants (break it into two halves, then each halve into another two halves, and each of those into yet another two halves). Each quadrant is a triangle consisting of only 90 degree angles. How can this happen? Its because lines on a sphere that diverge tend to reconverge at some point, which doesn't happen on a flat plane.

So, if the inhabitants of this spherical universe were to try to construct a triangle (which has to be really big) and find that each angle is 90 degrees, then they would have proven that they live in a spherical universe.

There are other shapes of the universe that are possible, such as the saddle shape below, also from Wikipedia:

HyperbolicParaboloid.png
"HyperbolicParaboloid". Licensed under CC BY-SA 3.0 via Wikimedia Commons.


The inhabitants of a saddle shaped universe can tell that their universe is a saddle shape and not a sphere because lines tend to diverge rather than converge, and so the triangle will have angles which are too small, rather than too big.

This is what the inhabitants would see if they drew a triangle on a...

spherical universe:


flat universe:


saddle shaped universe:


You might be asking about other weird shapes that the universe can be in. These shapes were derived from general relativity and depend on the mass of the universe. Different masses give rise to variations of these three shapes (how curved the triangles are) so this is all we will consider.

Now there is no actual need to measure all the angles of the triangle in order to see if they add up to 180 degrees. A more practical solution might be to stand at one of the points, say the top point, put a ruler at the bottom of the triangle a known distance away from you, and check how wide you have to open your field of vision in order to see the whole ruler. From the above three triangles you will have noticed that the top corner of each triangle has a different angle in order to achieve the same base length. In a spherical universe you'd have to have a wider top angle in order to achieve a 1 km base length, whilst in a saddle shaped universe you'd have to have a narrower top angle in order to achieve a 1 km base length. By measuring how wide the angle of vision has to be in order to see a ruler of a known length, a known distance away, the inhabitants of the universe can know what shape their universe is.



Of course there is no ruler readily available for us to use, especially not one that is big enough and far enough to measure subtle curvatures, and of course the universe is not two dimensional. Let's deal with these one at a time.

Does it matter than the universe is three dimensional? No, these same shapes can happen in any number of dimensions, as long as there is another dimension along which to curve. So can there be four dimensions? Determining if our universe is flat or not can answer that question. But if there is a fourth dimension, then we wouldn't be aware of it, just like the inhabitants of the flat universe would not be aware of a third dimension as they can only travel along the surface and cannot jump up or dig down. In the same way, we can only travel along our three dimensional space but we cannot move along a fourth dimension so we never needed to be aware of it. One thing is for sure however, 3D triangles still behave in the same way on a 4D sphere.

So how do we use the ruler experiment to determine the shape of the universe? Obviously we won't be using an actual ruler, but we can use something that is almost as good. The universe is expanding as we speak and everything is going further apart from each other, which means that in the past it was smaller and everything was closer together. What does this mean? That's not all. If you look far away, you will be seeing things from the past. This is because light is not instantaneous but travels at a constant speed, which means if you're looking at something which is so far away that the light reaching your eyes took 1000 years of travel, you are seeing what it looked like 1000 years ago. The oldest thing you can see is called the cosmic microwave background radiation. This is when the universe was 300,000 years old and was so dense that it was an opaque blob (light could not pass). This means that we cannot "see" past this 300,000 year mark, it is the oldest thing we can see in the universe.

Now here comes the crux of the matter: Gravity also travels at the speed of light. If the sun suddenly disappeared, the Earth would still be revolving around it as if nothing happened for 8 minutes. After 8 minutes, the Earth would fling out of orbit. This is because the Earth is 8 light minutes away from the sun. Since this Cosmic Microwave Background Radiation is only 300,000 years old, anything further apart than 300,000 light years would not be gravitationally affected. In other words, if there are two blobs that are more than 300,000 light years apart would not be gravitationally attracted to each other. This sets our ruler, a 300,000 light year long ruler. All you have to do is see how far apart from each other blobs have to be in order to not be attracted to each other. This is translated as checking how packed together the blobs were; with gravity attracting only blobs that were closer than 300,000 light years together, there will be a certain density of blobs that can be found by computer simulation.

So the trick is to check how wide an angle of vision must be used in order to see a certain number of blobs. If the universe is spherical, a narrower angle must be used, if saddle shaped, a wide angle must be used, and if flat, an angle in between must be used. Another approach was taken however in the BOOMERanG experiment. Rather than check what angle must be used to see a number of blobs, the number of blobs for a particular angle was found, together with the actual number of blobs seen, and illustrated in here (see the last picture).

The actual observation is very similar to what should have been seen if it was flat. This is evidence that the universe is, in fact, "flat", that is it is not curved upon some fourth dimensional curve.

Sunday, June 22, 2014

Thoughts on Aritificial Intelligence

I've always had issues with the Turing Test, not because I disagree with equating computed intelligence with the ability to imitate intelligence, but simply because it equates intelligence with speaking skills. Obviously intelligence has numerous ways of expressing itself other than through speech. Apart from there being no reason for this particular expression of intelligence to be superior to other expressions of intelligence (provided it is a sufficiently powerful intelligence), the Turing Test is actually impeding the progress of artificial intelligence by diverting attention to natural language processing rather than pure artificial intelligence.

The fact is that a sufficiently intelligent organism will learn to communicate with us in whatever way is most appropriate for it, even if it is not in English, just like a dog would. Communication is a consequence of intelligence rather than the other way round. So what I'm saying is that we should focus on developing pure artificial intelligence rather than chat bots, which will then be able to learn to communicate with us in whatever form is most efficient rather than using English. It may be the case than pure artificial intelligence is easier to achieve than programming a convincing chat bot using the methods we are using right now.

If human imitation is what is being sought, than perhaps it would be more practical to imitate something simpler than conversation. An example would be playing a game. Any video game player can vouch for the differences between playing against a computer and playing against another player. Even simple path finding can give away that you are playing against a computer rather than a real human, or even the ability to adapt to strategies used by the player rather than having a fixed exploitable pattern.

But even this is limiting the expression of intelligence, which the computer would ideally be free to express its intelligence in any way. So then how can intelligence be measured without being limited by a particular expression? Intelligence is the ability to discover patterns which can be used to increase the probability of reaching a goal. The process of discovery is usually called "learning". If we are to accept this definition, then I shall make a case against the Turing Test by showing how a plant can be tested for intelligence.

I have lately been dabbling in some indoor gardening by placing a potato in a pot and watering it. Let's illustrate this in a picture:



I have noticed that if you place a light source to one side of the plant, after some time the plant will bend itself to face the light, like so:



And if the light is then moved, the plant will bend appropriately:



This seems like pretty nifty behaviour, but it is not intelligence for it is only responding to a fixed stimulus, in other words, there are no patterns being taken advantage of. But now suppose that we set a revolving light that orbits around the plant which goes around slowly enough for the plant to bend towards it synchronously with the light revolutions. In the absence of intelligence, the plant will simply keep on bending towards the light forever, but what if we come back to check on the plant a few months later and find this:



The plant, rather than bending towards the light, responds to the pattern of the revolving light by adapting itself so that there are leaves at every side of the plant so that at any point in time, there are some of the leaves which are facing the light. Should we ignore biological details on whether or not the extra leaves do more good than harm (maybe the leaves take less energy to maintain than the constant bending), this would be evidence that the plant is intelligent.

Now, if even a plant can be considered intelligent, which is as far away from holding a conversation with a human as an organism can be (I think), think of how unfair the Turing Test is on computers, which requires them to master the human language so much that it fools people into thinking that it is a human. Alan Turing came up with a test for human imitation, and the Turing Test is a perfect test for this, but to claim that this is the best test of intelligence is silly.

I will intentionally not propose a specific test myself, because a specific test would be quantitative and formal in nature, and intelligence is not that. Intelligence can be surprising and we should accept it as that. I would much rather take a qualitative approach to intelligence, where someone proposes a pattern that is being learnt by a computer and researchers investigate its validity.

Sunday, June 8, 2014

Operant Conditioning

In behaviour psychology, in order to change the behaviour of a subject, you can use one of 4 different methods. These are categorized into reinforcements (rewards) and punishments and further into positive and negative. It is important to note that positive and negative have nothing to do with how they are perceived, only with whether something is added or removed to the subject.

MethodDescriptionExample
Positive reinforcement This is when a pleasurable experience is given to the subject in exchange for increasing the desired behaviour Getting a good mark for studying or giving a dog a treat for doing a trick.
Negative reinforcement This is when an unpleasant experience is removed from the subject in exchange for increasing the desired behaviour Removing some of a class's homework for being quiet or removing a dog's chain for not pulling it.
Positive punishment This is when an unpleasant experience is given to the subject in exchange for decreasing the undesired behaviour Getting a report for bad behaviour or giving a dog a scolding for not obeying.
Negative punishment This is when a pleasurable experience is removed from the subject in exchange for decreasing the undesired behaviour Removing a class's break time for being disruptive or removing a dog's toy for making noise.

Notice that these need not be manually applied by someone. It could be something like eating too many sweets giving you a stomach ache, which would be positive punishment.

Thursday, May 22, 2014

Boolean Algebra and Probability

Boolean Algebra is a field of algebra which formalizes the operations performed in logic, that is, on propositional statements (statements that are either true or false). This requires operations such as "AND", "OR" and "NOT" in order to compose complex statements from simpler ones, such as "it is raining" and "the road is wet" being composed into something like "NOT(it is raining) AND the road is wet". These operators work in the following way:

The statement "Math is awesome AND One Direction suck" is true because each of the simpler statements being joined together is true. If at least one of the simpler statements is false, then the whole thing becomes false.

The nice thing about this algebra is that it can be naturally extended from normal numeric algebra by representing a true statement with 1 and a false statement with 0. So then we can turn the statement "Math is awesome AND One Direction suck" into "1 AND 1" which is equal to "1". Why does it equal 1? Because for "X AND Y" to be true, both X and Y have be true individually. For example the statement "Math is awesome AND One Direction make great music" is false because one of those substatements is false. With the OR operator, as long as at least one of the substatements is true, the whole thing becomes true. For example "Math is awesome OR One Direction make great music" is true because one of the substatements is true. The NOT operator takes one substatement and inverts it, that is, if it was true then it becomes false and if it was false then it becomes true. For example "NOT Math is awesome" is false and "NOT One Direction make great music" is true. Numerically speaking, the following list summarizes these rules:

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

NOT 0 = 1
NOT 1 = 0

Can the be some normal arithmetic equations which will give us these outputs?

NOT is easy. What arithmetic equation returns 1 when given 0 and returns 0 when given 1?
NOT X = 1 - X
1 - 0 gives 1 and 1 - 1 gives 0.

AND is also easy. Just multiply the two operands together.
X AND Y = X × Y

OR is a little more tricky. This is because there is not single operation that gives the same outputs as OR. However we can easily derive an equation by using DeMorgan's laws which express an OR using AND and NOT only. The statement "in order to apply for the job you need a degree or five year's experience" can be expressed as "do not apply for the job if you do not have a degree and have less than five year's experience". Formally this is written as

X OR Y = NOT(NOT X AND NOT Y)

which numerically becomes

X OR Y = 1 - ((1 - X)(1 - Y))
X OR Y = 1 - (1 - Y - X + XY)
X OR Y = 1 - 1 + Y + X - XY
X OR Y = Y + X - XY

This makes sense. The OR operator is the addition of the two substatements minus one in case they are both true. This will return 1 whenever at least one of the two substatements is a 1.

But it also makes sense on a higher scale. If you think about it, these rules are the exact same rules for probability. Probability is a generalization of Boolean algebra. Rather than just considering truth and falsity like Boolean algebra does, probability considers values between those two cases, such that 1 is certainty, 0 is impossibility and all the numbers in between are a degree of uncertainty, where the closer the number is to 1 the more certain the statement is.

In fact AND and NOT are defined in exactly the same way in probability. But isn't OR defined simply as X + Y? That is in fact only the case when X and Y are events which are independent, that is, cannot happen together. In this case X AND Y is always zero and hence can be dropped from OR's equation. The equation we have derived is useful for dependent events as well such as asking for the probability of "two fair dice resulting in an even number and a number greater than 3". In this case you can't just add the probability of a die being even (3/6) and the probability of a die being greater than 3 (3/6) as otherwise you get 3/6 + 3/6 = 1 which means that you are certain that this will happen. The problem is that it is possible for the two substatements to be both true, that is, a die being both even and greater than 3 (namely 4 and 6). To fix this just subtract the probability of this special case occurring (2/6) which gives 3/6 + 3/6 - 2/6 = 2/3.

Let's illustrate it with a Venn diagram:


The Venn diagram above is showing two events as a red and blue circle. They have some overlap between them which is coloured purple. If the red circle represented the chance of a die being even and the blue circle represented the chance of a die being greater than 3, then the purple overlap would be the numbers 4 and 6. Now we want to find the probability of the red OR the blue circle occurring. If we just add their areas together we end up with the purple overlap being added twice since it is common to both circles, but we just want to add it once. So we subtract it once after adding both circles, which will result in having just one purple overlap. This is what is happening when you use the equation X + Y - XY.

Sunday, April 20, 2014

Don't edit batch files during runtime

So it turns out that Windows batch files running under cmd (at least in Windows 7) are not preloaded into memory before runtime. Instead each line is loaded from disk right before it is executed. What this means is that if you edit the batch file during its runtime, you'll end up modifying the behaviour of the batch file being run.

Try this:
echo started
timeout 10
echo continued
echo ended
pause

This will make the batch file show "started", then wait for 10 seconds and finally show "continued" and "ended". To run it just paste the above code into Notepad and save it as "something.bat", then just double click the saved file.

Now open the batch file with Notepad again and run the file at the same time. As the batch file is waiting for 10 seconds, delete the "echo continued" line and save (before the 10 seconds are up). When the batch file continues, it will not show "continued" but will immediately jump to "ended".

Strange behaviour since this sort of thing does not happen with Python for example. I noticed this when I was trying to run multiple versions of the same batch file by just changing something in the file and running a new instance of it. Be careful of this.

Tuesday, March 18, 2014

Random Indexing for word space context vectors

Last time I had described what a term document matrix is and how to make it's use faster using Latent Semantic Analysis. Today I shall be explaining how to use Random Indexing as an alternative to LSA. You can read more about it here.

Unlike LSA, random indexing is a very easy and very fast online process. It is online in the sense that you don't need to first completely construct the co-occurrence matrix in order to use it, but can instead use it as you are counting co-occurrences. It also works just as well as LSA. Interested yet?

First of all, how do you construct a co-occurrence matrix? You start off with a matrix full of zeros with columns for words in context w1, w2, w3, and w4 and rows for neighbouring words n1, n2, n3, and n4:
   n1 n2 n3 n4
w1 0  0  0  0
w2 0  0  0  0
w3 0  0  0  0
w4 0  0  0  0
You go through the corpus and you encounter word w2 and near it is word n4. You record this encounter by incrementing the matrix element for w2-n4:
   n1 n2 n3 n4
w1 0  0  0  0
w2 0  0  0  1
w3 0  0  0  0
w4 0  0  0  0
You do this for every neighbouring word next to every word in context and finally you have your co-occurrence matrix.

Now this very same process can be viewed in a different way. Instead of incrementing single numbers, it can be viewed as vector addition. Forget the names given to the columns:
w1 0  0  0  0
w2 0  0  0  0
w3 0  0  0  0
w4 0  0  0  0
Instead assign a vector to each neighbour word where each vector consists of just zeros and a single 1. No two vectors can have a 1 in the same position. So these could be the vectors assigned to our 4 neighbour words:
n1: (1 0 0 0)
n2: (0 1 0 0)
n3: (0 0 1 0)
n4: (0 0 0 1)
Now when you encounter neighbour word n4 next to word in context w2, you just take w2's row, which is a vector, and add it to n4's vector:
w2: (0 0 0 0) +
n4: (0 0 0 1)
    =========
    (0 0 0 1)
Which gives you the updated matrix:
w1 0  0  0  0
w2 0  0  0  1
w3 0  0  0  0
w4 0  0  0  0
Do this for every neighbour next to every word in context and you have your co-occurrence matrix.

All random indexing does is change the neighbour words' vectors. Instead of the vectors being as long as the number of neighbours, the vectors are shortened to a fraction of what they are supposed to be. Consequently the number of columns in the matrix will also be reduced. "But how can you put a 1 in a different position for every neighbour word?" I hear you ask. You don't. What you do is you still keep the vectors mostly zero, but now you randomly put a few 1s and -1s in it:
w1 0  0  0
w2 0  0  0
w3 0  0  0
w4 0  0  0

n1: ( 1  0 -1)
n2: ( 0  1 -1)
n3: ( 0 -1  1)
n4: (-1  1  0)
If we encounter word in context w2 with neighbour word n4, then the matrix will become:
w1  0  0  0
w2 -1  1  0
w3  0  0  0
w4  0  0  0
If word in context w2 also has word n2 as a neighbour, then the matrix will become:
w1  0  0  0
w2 -1  2 -1
w3  0  0  0
w4  0  0  0

Now it will not be possible to know how many times each neighbour word co-occurs with each word in context, but that's OK. What matters is that each time you encounter a neighbour word, it leaves its mark on the word in context's row and that the more often it is encountered, the more its mark is pronounced. This means that you can still find similar words by comparing their rows together. The difference is that the rows are shorter and hence faster to compare.

Notice the online nature of this process. At any point in the corpus traversal, the matrix is always in its compressed form and there are no complex transformations that need to be made on it. You can ever add more words to or remove words from the matrix, without any further processing or extra data. You just have to find a compromise between how many columns to remove from the matrix and the individuality of the rows. The smaller the rows, the less of an individual mark each neighbour word will leave after adding its vector.