Relativity Theory in Actual Formulas

I think a lot of people know some basic elements of Einstein's Relativity Theory. Some things which are not as commonly known are actual equations with numerical examples. Everything is relative, except for the light of speed. That includes space and time, which were always viewed as absolute.

However, what might be interesting, how much do space and time get stretched or compressed? Obviously, most people know that the effects are only important at speeds close to the speed of light. But what does it mean?

Well, just assume a car, which is going really fast. LIKE REALLY FAST. The following table starts with 0.001 of c as the start speed, which is still 29,979 m/s. Here, the car is still (to an unomved observer) 5 m long with an error of 0.0000025 m. That is accurate enough to say that it is negligible. So any car going at regular (even lower) speeds will not be subject to any noticeable space compression.

But we see that around 30% of c, the car will look noticeably shorter, roughly 25 cm. At speeds almost equal to c, for example 99.9999% of c (second-to-last row), the car will only be 7 mm long. You read that right. An observer standing on a road where a car just happens to pass by at that speed will (if he is able to notice any differences due to how fast it will probably be out of sight) estimate the length of the car at 7 mm.

That graph shows the relationship. The length of the car goes down the closer you come to c and reaches 0 at exactly c. It also practically 5 at all speeds which will be encountered. Just to emphasize, if you were sitting in the car, you would not feel compressed. Rather, the surrounding environment would be compressed. 

Automatic Text Summarization with Neural Networks

Automatic Text Summarization is one of the more interesting fields in text processing and text analysis. I had previous experience with artificial neural networks (ANNs) programmed in MATLAB and decided to implement the model by Khosrow Kaikhah, published in June 2004 under the same title as this blog entry. I did not follow the paper exactly, especially in regard to the ANN architecture.

The basic premise is relatively simple: One seperates texts (six simple texts from www.newsinlevels.com) into paragraphs and single sentences. Each sentence is then analyzed in regard to the following seven features:

1. Sentence is in Paragraph which follows the Title [0/1]
2. Location of the Paragraph containing the Sentence within the Text [0-1]
3. Location of the Sentence within the Paragraph [0-1]
4. First Sentence in Paragraph [0/1]
5. Length of the Sentence [0+]
6. Number of the Text's most important (frequent) Words in the Sentence [0+]
7. Number of Title Words in the Sentence [0+]

All these values are retrieved with different MATLAB functions and constructs. In regard to feature number (1), this value is "1" for all sentences which are in the leading paragraph and "0" otherwise. For (2), the position within the text is given in percentages. Again, this value is the same for all sentences in each paragraph. A text with 3 paragraphs would result in giving all sentences in the first paragraph the value 0.333, since one is "a third" through the paragraph after reading this paragraph. The last paragraph (or more precisely, each sentence in it) would have the value "1". Feature number [3] is exactly the same, only in regard to the position of the sentence within the paragraph, giving every sentence a unique location, with the last sentence having the position "1". [4] is easy, either "0" or "1" depending on whether or not the sentence is the first in the paragraph. Feature [5] simply shows how many symbols are contained in the sentence. The last two features are slightly more complex. [6] basically creates a list of the most used words in the text. I decided to use the three most frequent words for each text and counted for every sentence the respective occurrences. The last feature [7] counts how often a word contained in the title is occurring in the sentence. For the last two features, I only used words with a minimum length of 4/3, so I could erase common words like "the" or "and" from the text analysis and very short words common in titles like "a" or "is" from the title analysis.

Basically, the selection of these exact features is dependent on some studies and general assumptions that a sentence should be more important if its "scoring" high on several of those measures. For a more detailed intuition, please refer to the original paper. The picture above shows the resulting array for the first few texts (every row is a sentence). The columns represent the features from [1] to [7]. This array is then z-score normalized, which is good practice for ANN inputs.

Obviously, before we can train the ANN, we need to provide it with targets. So a test person summarizes (selects summary sentences) six test texts. This is only a "0"/"1" vector, implying whether or not the respective sentence is a summary sentence or not.

I used a simple feed-forward ANN with three layers, four hidden neurons in the hidden layer and the Levenberg-Marquardt training algorithm. The input layers are obviously the seven input feautres, and the output layer consists of a single node. The neural network learns to map the sentences in the training sample to the target vector (sentence is summary sentence or not) by adapting internal structures, processing weights or other methods. After sufficient rounds of training, MATLAB terminates the process.

Now, it is really simple. We have the trained network, and "show" it another text, one the test person has never seen before (see picture above), but should be reasonably similar to the other texts. As a result, it produces a value from "0" to "1" for each sentence in the new text. If this value is reasonably high (i chose a value of over 0.8), I would assume that the ANN recognizes it as a summary sentence. Obviously, this threshold is not objective, maybe a sentence limit would be appropriate, e.g. choose a threshold so that a summary of 3, 4 or 10 sentences is produced.

If we now only "count" the sentences which are classified as being summary sentences, the following summary is produced (all lower case due to the processing; keep in mind that this is an article written in very simple english)

"a man from slovakia is happy. he is working on a flying car. the car has an original design. when you want to fly, the car must change. people want to make the car which can fly next year for others who will buy this car."

This is by no means perfect, but for a very low amount of training texts (six), relatively short texts (three to five paragraphs with one to six sentences per paragraph) and a very quick choice of the ANN structure, the result is pretty good.

The best part is that it includes the test reader's own personal reading/summarization style. With further work, this model could be a very legitimate tool for automatic text summarization. 

Cellular Automata

Cellular Automata are dynamic systems which feature a lot of individual processing units and the status of each unit usually depends on some kind of (simple) function that depends on temporal or spatial neighbors. 1D CAs can be thought of a line of nodes that have some status depending on the previous nodes. 2D CAs start with such a line and add, for each step, another line. Each node then has a predecessor (which is "above" it) and a successor (whis is "below" it). Each nodes status is influenced by a specified amount of predecessors (and its neighbors) and itself influences its successors. 3D CAs, then, can be thought of flat surfaces consisting of individual processing units. For every step, another surface is added, until the whole system resembles a cube, or a huge stack of paper.

They have a lot of practical and theoretical implications. One can easily model dynamic systems, for example how stock markets evolve when each investors considers only his "neighbors" actions from previous points in time. Similarly, one can model spatial dimensions. For example, a traffic model can be constructed, where all actions of individual cars (braking, accelerating), depend on the respective cars in front and behind them.

I played around quite a bit with them and tried to build some models of my own. Maybe someone starting to deal with Cellular Automatas can use some of them. Or maybe someone reads this and becomes interested in constructing such models him/herself. Really any spreadsheet software can be used to produce such models within models and obviously, various programming languages lend themselves to be used as well.

1) ONE SPECIES SURVIVAL
For this CA, I tried to model the survival or (non-survival) of a single species, which needs more than one individuum to reproduce. Each node represents a spatial unit where one individuum could be. Each line is intended to stand for one generation. The "5-neighborhood" is observed. So, if there is more than one individual in the last five spots, an offspring is produced and takes the spot (1/red) with probability 1-p. Otherwise, the spot remains empty (0/white). The initial distribution is randomly distributed with 50/50 probalitity. One can see how clusters of individuums "survive". On the edges of such groups, however, spots can become empty and lone individuals cannot reproduce. Depending on p, the species can die off. If p is reasonably low, the species will flourish and occupy nearly all spots.

1-species survival with p=0.4

1-species survial with p=0.31

1-species survival with p=0.2

2) FOREST FIRE
I tried to model how forest fire spread. This is a little complexer CA, as the nodes have more than 2 statuses and there are various parameters. All nodes represent a spatial unit where there is either nothing (0/white), a tree (1/green) or an ongoing fire (2/yellow). Each line represents one time step. Each node's status only depends on its own status before. p1 is a parameter that models the likelihood that no tree grows on an empty space (fertility factor). p2 indicates the likelihood that an ongoing fire burns out during one period. The last parameter, p3, simply represents the likelihood that a tree is not starting to burn in the next period. Depending on all factors, spots can remain empty for long, trees start to burn at alarming rates or fires rage on for several periods. These parameters can be used to model, for example, dry forests with high danger of ignition. Similarly, it is easy to simulate forests where trees are spaced out wide, meaning that fires are likely to die out.

forest fire with p1=0.9, p2=0.2 and p3=0.995