Four Years Remaining

Logic versus Statistics

Consider the two algorithms presented below.

Algorithm 1:

   If, for a given brick B,
      B.width(cm) * B.height(cm) * B.length(cm) > 1000
   Then the brick is heavy

Algorithm 2:

   If, for a given male person P,
      P.age(years) + P.weight(kg) * 4 - P.height(cm) * 2 > 100
   Then the person might have health problems

Note that the two algorithms are quite similar, at least from the point of view of the machine executing them: in both cases a decision is produced by performing some simple mathematical operations with a given object. The algorithms are also similar in their behaviour: both work well on average, but can make mistakes from time to time, when given an unusual person, or a rare hollow brick. However, there is one crucial difference between them from the point of view of a human: it is much easier to explain how the algorithm "works'' in the first case, than it is in the second one. And this is what in general distinguishes traditional "logical" algorithms from the machine learning-based approaches.

Of course, explanation is a subjective notion: something, which looks like a reasonable explanation to one person, might seem incomprehensible or insufficient to another one. In general, however, any proper explanation is always a logical reduction of a complex statement to a set of "axioms". An "axiom" here means any "obvious" fact that requires no further explanations. Depending on the subjective simplicity of the axioms and the obviousness of the logical steps, the explanation can be judged as being good or bad, easy or difficult, true or false.

Here is, for example, an explanation of Algorithm 1, that would hopefully satisfy most readers:

• The volume of a rectangular object can be computed as its width*height*length. (axiom, i.e. no further explanation needed)
• A brick is a rectangular object. (axiom)
• Thus, the volume of a brick can be computed as its width*height*length. (logical step)
• The mass of a brick is its volume times the density. (axiom)
• We consider the density of a brick to be at least 1g/cm³ and we consider a brick heavy if it weighs at least 1 kg. (axiom)
• Thus a brick is heavy if its mass > width*height*length > 1000. (logical step, end of explanation)

If you try to deduce a similar explanation for Algorithm 2 you will probably stumble into problems: there are no nice and easy "axioms" to start with, unless, at least, you are really deep into modeling body fat and can assign a meaning to the sum of a person's age with his weight. Things become even murkier if you consider a typical linear classification algorithm used in OCR systems for deciding whether a given picture contains the handwritten letter A or not. The algorithm in its most simple form might look as follows:

   If 
   Then there is a letter A on the picture,

where are some real numbers that were obtained using an obscure statistical procedure from an obscure dataset of pre-labeled pictures. There is really no good way to explain why the values of are what they are and how this algorithm gets the result, other than to present the dataset of pictures it was trained upon and state that "well, these are all pictures of the letter A, therefore our algorithm detects the letter A on pictures".

Note that, in a sense, such an "explanation" uses each picture of the letter A from the training set as an axiom. However, these axioms are not the kind of statements we used to justify Algorithm 1. The evidence they provide is way too weak for traditional logical inferences. Indeed, the fact that one known image has a letter A on it does not help much in proving that some other given image has an A too. Yet, as there are many of these "weak axioms", one statistical inference step can combine them into a well-performing algorithm. Notice how different this step is from the traditional logical steps, which typically derive each "strong" fact from a small number of other "strong" facts.

So to summarize again: there are two kinds of algorithms, logical and statistical.
The former ones are derived from a few strong facts and can be logically explained. Very often you can find the exact specifications of such algorithms in the internet. The latter ones are based on a large number of "weak facts" and rely on induction rather than logical (i.e. deductive) explanation. Their exact specification (e.g. the actual values for the parameters used in that OCR classifier) does not make as much general sense as the description of classical algorithms. Instead, you would typically find general principles for constructing such algorithms.

The Human Aspect

What I find interesting, is that the mentioned dichotomy stems more from human psychology than mathematics. After all, the "small" logical steps as well as the "big" statistical inference steps are all just "steps" from the point of view of maths and computation. The crucial difference is mainly due to a human aspect. The logical algorithms, as well as all of the logical decisions we make in our life, is what we often call "reason" or "intelligence". We make decisions based on reasoning many times a day, and we could easily explain the small logical steps behind each of them. But even more often do we make the kind of reason-free decisions that we call "intuitive". Take, for example, visual perception and body control. We do these things by analogy with our previous experiences and cannot really explain the exact algorithm. Professional intuition is another nice example. Suppose a skilled project manager says "I have doubts about this project because I've seen a lot of similar projects and all of them failed". Can he justify his claim? No, no matter how many examples of "similar projects" he presents, none of them will be considered as reasonable evidence from the logical point of view. Is his decision valid? Most probably yes.

Thus, the aforementioned classes of logical (deductive) and statistical (inductive) algorithms seem to directly correspond to reason and intuition in the human mind. But why do we, as humans, tend to consider intuition to be inexplicable and thus make "less sense" than reason? Note that the formal difference between the two classes of algorithms is that in the former case the number of axioms is small and the logical steps are "easy". We are therefore capable of representing the separate axioms and the small logical steps in our minds somehow. However, when the number of axioms is virtually unlimited and the statistical step for combining them is way more complicated, we seem to have no convenient way of tracking them consciously due to our limited brain capacity. This is somewhat analogous to how we can "really understand" why 1+1=2, but will have difficulties trying to grasp the meaning of 121*121=14641. Instead, the corresponding inductive computations can be "wired in" to the lower, unconscious level of our neural tissue by learning patterns from experience.

The Consequences

There was a time at the dawn of computer science, when much hope was put in the area of Artificial Intelligence. There, people attempted to devise "intelligent" algorithms based on formal logic and proofs. The promise was that in a number of years the methods of formal logic would develop to such heights, that would allow computer algorithms to attain "human" level of intelligence. That is, they would be able to walk like humans, talk like humans and do a lot of other cool things that we humans do. Half a century has passed and this still didn't happen. Computer science has seen enormous progress, but we have not found an algorithm based on formal logic that could imitate intuitive human actions. I believe that we never shall, because devising an algorithm based on formal logic actually means understanding and explaining an action in terms of a fixed number of axioms.

Firstly, it is unreasonable to expect that we can precisely explain much of the real world, because, strictly speaking, there exist mathematical statements that can't in principle be explained. Secondly, and most importantly, this expectation contradicts the assumption that most "truly human" actions are intuitive, i.e. we are simply incapable of understanding them.

Now what follows is a strange conclusion. There is no doubt that sooner or later computers will get really good at performing "truly human" actions, the trend is clear already. But, contradictory to our expectations, the fact that we shall create a machine that acts like a human will not really bring us closer to understanding how "a human" really "works". In other words, we shall never create Artificial Intelligence. What we are creating now, whether we want it or not, is Artificial Intuition.

It is good to attend lectures from time to time, even if these are on the topics that you "already know". Because, once in a while, you get to find out something new about things that are so "simple" and "familiar", that you thought there was nothing new you could possibly discover about them. So, today I've had an accidental revelation regarding a simple yet amusing property of the maximum likelihood estimation method. I think I should have been told that years ago, right on the first statistics course.

Maximum Likelihood

Maximum likelihood estimation is one of the simplest and most popular methods for fitting mathematical models to given data. It is most easily illustrated by an example. Suppose you are given a list of numbers , which, you believe, are all instances of a normally distributed random variable with mean and variance . The problem is that the value of is unknown to you and you would like to estimate it from the data. How do you do it? The maximum likelihood method suggests you to search for a value of , for which the probability (or probability density) of obtaining exactly this set of numbers would be maximal. That is:

In most cases this turns out to be quite a reasonable suggestion, which leads to good estimates (although, there are some rare exceptions). Here, for example, it turns out that to estimate the mean you should simply compute the average of the given numbers:

This is more-or-less all what a typical textbook has to say about maximal likelihood, but there's more to it.

Counting Lightbulbs

Consider the following example. Suppose you are willing to measure the average lifetime of a common lightbulb (that is, the amount of time it will glow until burning out). For that you buy 1000 lightbulbs in a general store, switch all of them on and wait for a year, keeping track of the timepoints at which the  individual lightbulbs burn out. Suppose the year has passed and you managed to record the lifetime of just 50 "dead" lightbulbs (the remaining 950 keep on glowing even after the whole year of uninterrupted work). What do you do now? Do you wait for other lightbulbs to burn out? But this can take ages! Do you just discard the 950 lightbulbs and only consider the 50 for which you have "available data"? This is also not good, because, clearly, the knowledge that 95% of lightbulbs live longer than a year is important. Indeed, from this fact alone you could infer that the average lifetime must be between 18 and 21 years with 95% confidence (an interested reader is invited to verify this claim). So what do you do?

Assume that the lifetime of a lightbulb can be modeled using exponential distribution with mean (this is a natural assumption because exponential distribution is well-suited for describing the lifetime of electric equipment). Then the probability (probability density, in fact) that lightbulb i burns out after years can be expressed as:

.

Naturally, the likelihood of lightbulbs 1,2,3,...,50 burning out after years correspondingly, is just the product of the corresponding expressions:

.

Now what about the lightbulbs that are still alive? The likelihood that a lightbulb will glow longer than a year can be easily expressed as:

.

Therefore, the total likelihood of having 50 lightbulbs burn out at time moments and 950 lightbulbs keep working longer than a year is the following product:

.

Finding the estimate of that maximizes this expression is now a simple technical detail of minor importance. What is important is the ease with which we managed to operate the "uncertain measurements" for the 950 lightbulbs.

Final Remarks

Note that the idea can be extended to nearly arbitrary kinds of uncertainty. For example, if, for some lightbulb we knew that its lifetime was a number between a and b, we would include this piece of knowledge by using the term in the likelihood function. This inherent flexibility of the maximum likelihood method looks like a feature quite useful for the analysis of noisy data.

Surprisingly, however, it does not seem to be applied much in practice. The reason for that could lie in the fact that many nontrivial constraints on the data will make the likelihood function highly nonconvex and hard to optimize. Consider, for example, the probability density

for a normally distributed variable X. Depending on the choice of , , and , the likelihood function will have either three different peaks at , two peaks or just one. Thus, finding an exact optimum is much harder than in the typical textbook case. But on the other hand, there are various cases where the likelihood function is nicely convex (consider the interval constraint mentioned above) and besides there are numerous less efficient algorithms around anyway. So maybe the trick is not used much, simply because it's not in the textbook?

Effective time management is an important and an interesting issue. It is important because, theoretically, it should provide a way to be more efficient and thus spend less time doing work and more time having fun. It is interesting because of the wide range of methodologies, techniques and advices lying around: there is clearly no universal method that fits everyone. Some people say that the key trick to efficiency is being goal-oriented and managing priorities, others believe it is all about proper todo-lists, calendars and reminders. Some say you must constantly motivate yourself to work hard, others believe you better learn to go with the flow and follow your internal desires. There are also those who say that being organized is an inherent character trait and not a skill that one can acquire.

I strongly disagree with the latter statement. Being in general a lazy, careless, unmotivated and not at all a responsible person, I still manage to be somewhat productive from time to time, and I think a significant role in that is due to simple tricks. I realized it most clearly amidst master's studies, when my lecture schedule was suddenly over and I had to figure out myself what to do with my time.

Now, the whole "time management theory" is actually quite trivial, just a bunch of obvious pieces of advice. One can read through a book or two of those in a pair of days. It takes much longer, however, to figure out which of those pieces of advice would work for you personally. Take for example the popular suggestion to keep a notebook with a todo-list and spend 5 minutes every day to plan the day. I tried that several times, and although it does seem to help temporarily, I just can't make myself follow the routine. First of all, the requirement to write trivialities into the notebook is demanding. The mind resists it and tries to optimize the notebook away as quickly as possible. Secondly, the need to follow some routine "5 minutes every day" is a disciplinary burden too heavy for my lazy personality.

Here's another popular suggestion that I found to be somewhat useless: plan your projects, set yourself deadlines and keep up to them. This doesn't work for me for two reasons. Firstly, there is not much added value in explicit planning for most day-to-day tasks, intuition does a pretty good job here anyway. And then, no matter how detailed a plan you would have for each project, you'll still have the problem of scheduling your time among these, as well as handling all those tiny routine events and unexpected tasks. Finally, the requirement of keeping up to deadlines sounds more like a problem than a solution to me.

Fortunately, there are tricks that work much better, and it is them that I was planning to write about. The best time management ideas that I know of, have been nicely summarized by D. Allen in his GTD ideology. His advice is based on three obvious (as usually), but nonetheless insightful observations:

1. A time management system won't work unless you put everything in it. This includes every smallest idea that you ever had to think about, including "I want to go see that stupid movie some day" and all the less important things. Although it might seem like an overkill, it's not. These small ideas, unless materialized somehow, can use up quite a lot of your brainpower by just "being on your mind". As soon as you write them out in a safe place, your mind gets much clearer. Also, you can only manage your schedule if you really know that everything is there.
2. If there's an idea, it is not immediately clear what action it implies. For example, "I want to see a movie" is an idea. The first action that needs to be done to make it happen is actually "Call a friend". It's not a big deal to figure it out, but nonetheless there's some amount of thought involved. Surprisingly often, this small amount of thought is a terrible hurdle while undone. Indeed, isn't it much more pleasant to know that you need to "call a friend" than to have a vague "go see a movie" entry on the todo-list? What GTD essentially suggests is to make this "first action" decision as early as possible and keep the todo-lists in terms of actions, not ideas.
3. A proper file management/archiving system is crucial. There has to be a place where you can store all these ideas, "first actions", reference materials, schedule, reminders, etc. Ideally, this storage has to be organized in an associative manner, i.e. you should be able to retrieve things in context easily. "I'm in a mood to write an email now, do I have a task that fits this context?", "I'm working on this project now, what are the related materials?". Once again, if you can trust your system to store things for you, your mind is relieved.

The GTD ideology describes a simple workflow process based on these observations. The whole process uses heavily the notion of "inboxes" and goes as follows:

1. All the ideas or tasks you might have arrive at your "IN" inbox.
2. You review this inbox regularly, and decide for each item it's first action. Upon decision, you must move items out of the "IN" inbox, and you have the following limited set of options:
   1. There is nothing to do about it. Delete and forget.
   2. This is some useful information. Archive for future reference.
   3. This requires you to do something small (it'll take 2 minutes or so). Do it now. Delete message.
   4. This requires you to do something that will take longer than 2 minutes. Then:
      1. You can schedule doing it to a fixed date and time (add an entry to the calendar). Delete message or archive for reference.
      2. You can move the message into the "ASAP" inbox. You'll review that inbox next time you have some free time. Note that the choice between (1) and (2) allows to balance conveniently between "100% planning" and "no scheduling at all" while still keeping track of all your stuff.
      3. You can move it into the "Someday" inbox. You'll review that inbox someday later.
      4. This is something you have to delegate. Then you move the item to the "Pending" inbox, so that you won't forget about it.
3. Besides the inboxes "IN", "ASAP", "Later" and "Pending" you also need to keep a list of ongoing projects as folders with relevant information. You can review this list from time to time to make sure you haven't forgotten anything.

The best part in this whole process (and this is what actually makes it suitable for me personally), is the fact that it can be implemented using e-mail. This way it does not force much additional discipline: I'm reading email several times a day anyway as part of my compulsory procrastination activities. Most of my tasks, even the smallest ones, are in one way or another reflected in the e-mail. It is then only a matter of keeping the proper folder structure and moving emails out of INBOX according to the above protocol, remembering to think about the "next action" in the process. That is quite easy, it forces to manage and schedule more or less all of my activities, and it keeps the mind reasonably free, too.

The amusing fact that Minesweeper was proven to be NP-complete is quite well known in certain circles. However, it seems that no one has yet cared to publicly demonstrate the (probably obvious, but not a single bit less amusing) fact, that constructing LEGO toys is also an NP-complete task. Here I fix this disturbing flaw and present a reduction of SAT to LEGO by a simple example.

Suppose you are given the following set of LEGO blocks

and you wish to construct the following structure from them (using only this picture as a reference):

It turns out that devising such a configuration is equivalent to finding a satisfying assignment for the boolean formula , and it is possible to devise an analogous configuration for any other logical formula in CNF. Thus, building LEGO must be at least as hard as satisfying boolean formulas, that is, NP-hard.

Indeed, let the red brick correspond to the variable , the blue brick let be , the pink brick and the light blue brick .
Consider the part I of the target configuration (the one in the upper left). It contains one red brick and one light blue brick, but because of the black block in front of them we don't know whether the red and the light blue bricks are of height 1 or 2. There are three possible options:

We say that this configuration corresponds to the term , where having a higher brick for a given variable corresponds to setting the value of that variable to True. Clearly, for the configuration to be possible either the red brick () or the light blue brick () must be high, and therefore a proper choice of bricks here corresponds to a choice of values in the expression . Analogously, part II corresponds to the term and the fact that both parts are possible translates to the full equation .

Now what about parts III and IV? These guarantee that if we choose the high red brick when constructing parts I and II, we shall necessarily have to use the shorter pink brick there, and similarly for the blue and light blue bricks. Indeed, due to the choice of white bricks there are two ways of constructing part III:

In the first case we use up the high red brick and the short pink brick for constructing part III, and therefore end up with the short red brick and high pink brick for building parts I and II. This corresponds to picking the value False for . Similarly, the second way of constructing part III would enforce the value True for the variable .

A short reflection should convince you now, that the same scheme can be used to represent any other CNF boolean expression. As it is well known that finding a satisfying assignment for a boolean formula is NP-complete, it follows that LEGO is NP-complete too.

Q.E.D.

This week I had a chance to participate in a project meeting related to soft computing. A part of the meeting was a brainstorm-like session, dedicated to the generation of relevant topics for future research in the field. I was listening very carefully, writing everything down, and trying to generalize somewhat. By the end of the meeting my generalization attempts succeeded and now I can easily generate relevant topics in arbitrary numbers without any external help. In an act of openness, unprecedented elsewhere in scientific circles, I'm sharing this secret technology with you here.

For the curious: here is the source code.

A beloved child has many names, and so does the field of pattern analysis. Some people call it soft computing, others refer to it as machine learning or data-driven statistics. Although in practice all those terms denote the same approach to data analysis, there is always a certain bias hidden behind each name that relates it to its history and origins. I'm not sure whether I understand these biases correctly, but here's how I would define the terms:

Pattern Analysis

This is probably the most general term that refers to a kind of data analysis, where the goal is to find "something interesting" in a given dataset. We typically know what kind of things (patterns) we consider interesting (this might be an association rule, a frequent subsequence, a classifier, etc), and the task is to detect the instances of this kind of patterns. Conceptually somewhat opposite to pattern analysis would be statistical hypothesis testing, where the task is to test a given pattern for interestingness. In this sense pattern analysis is very close to the multiple hypothesis testing statistical problem.
The simplest way to formalize this generic notion I've seen in this exposition by Tilj de Bie. Let denote the dataset, let be the pattern space (e.g. "the space of all sequences", or "the space of all classifiers", etc), and let for each there be a pattern function , so that measures the "interestingness" of this pattern with respect to the data . Then the general task of pattern analysis is just the following maximization problem:

Machine Learning

Machine learning can be regarded as a specific type of pattern analysis, where the central interest lies in finding classifiers or regression functions. The dataset in this case consists of a number of "instances" , and the task is to find a function that maps these instances to corresponding "outputs" in various ways.
In the case of supervised machine learning, a "true" output is provided with each instance , and the resulting function should aim to match this output for given instances (i.e. ) as well as generalize to the unseen ones. Statisticians call this task regression analysis. A classical example is the problem of detecting incoming spam mail by learning the classification rule from previously labeled messages.
The task of unsupervised machine learning is to find a classifier without any prespecified labeling of data. Typically one searches for a function that maps similar inputs to similar outputs. If the set of outputs is small and discrete, the task is referred to as clustering and somewhat resembles the problem of quantization. If the outputs are continuous, the task can often be related to either factor analysis or noise reduction.
Finally, the problem of semi-supervised machine learning is to find a classifier for a dataset where some instances have labels and some don't. This can sometimes be regarded as task of missing value imputation.
The typical approach to all types of machine learning task usually employs the definition of a loss measure , that estimates the goodness of fit for a given classifier , and then searching for a classifier that optimizes this measure, i.e.:

This defines machine learning as a certain kind of pattern analysis.

Soft Computing

If the previous terms denote purely mathematical approaches, for which the exact computational method of obtaining a solution is somewhat irrelevant, then this term, on the contrary, denotes a set of certain metaheuristical computational techniques for obtaining these solutions. In the narrowest sense, by soft computing one might collectively denote the areas of evolutionary algorithms, fuzzy logic and neural networks. This gives soft computing a somewhat ad-hockish flavour: "If you don't know how to solve it, simply put it into a neural network, neural networks just work".

Data Mining

This might be just my opinion, but I define data mining as any kind of pattern analysis, that is applied in an offline setting. Moreover, I'd say that, ideally, true data mining happens when you attempt to search for patterns in data that was not initially meant for that specific analysis, thus contradicting the classical statistical ideology "specify your hypothesis first, collect the data later".

Knowledge Discovery from Databases

As far as I understand it, KDD is just a YABA and marketingspeak for "data mining", somewhat in the same manner as OLAP and Business Intelligence are marketingspeak for "descriptive statistics".

Data-Driven Statistics

In the narrowest sense, data-driven statistics denotes all kinds of nonparametric statistical approaches. These are those methods, where one manages to perform data analysis without specifying any parameterized distributions for the inputs or the like. Typical examples would be the various resampling and randomization techniques. In the broad sense, again, this might very much be the same as pattern analysis in general.

Any other popular terms for the same thing I've forgotten here?

Dan said once that I should produce more Weltschmertz in this blog. However, I find this area to be expremely complex to write about because it is really difficult to be even marginally constructive or at least analytic in this field. Anyway, here's an attempt to touch on the classics.

Today we had a "CS institute day" - a local-scale PR-event aiming at introducing the inner workings of the computer science institute to the students and answering whatever questions they might have about their present or future studies. As it often is the case with such events, the majority of the attendees were not the students but rather the members of the faculty who were either willing to help answer potential questions or just curious about the event. Not more than a dozen students attended. This is unfortunate, as it displays a significant lack of interest of the students towards their studies. There are several reasons for that, the most prominent being perhaps the following two issues:

• The first "problem" is that studies are free (for most people) here and many students regard them as a nuisance rather than as a way to learn necessary skills. It's often about "I go to university because of some stupid tradition" rather than "I study because I really need knowledge and skills". I heard that the attitude is different in those universities where students pay for their studies. Of course, I'm not promoting the idea of paid studies, but I think that the students would benefit if they could at least mentally put themselves in a situation where the university is something expensive and optional (rather than free and necessary). I'm not sure how to do that, though: whenever the faculty attempts to arrange a motivational event, noone attends.
• The second "problem" lies in the bloated market demand for IT specialists of any level. Nowadays one can easily get a disproportionately well-paid code-monkey position without any education. This will change, however. As the price level rises, Estonia quickly loses its appeal as an IT outsource country. The internal market for IT solutions does exist, but the pool of available developers grows faster than demand. Three years ago the local large IT companies were literally fighting to recruit as many IT students of any age as possible. Today they are probably still glad to get new people, but it's not as critical. Tomorrow they won't have free projects to assign to arbitrary new people. Finally, the day after tomorrow we are hopefully going to see real competition in IT-skills, which will be the normal situation for an industry. It is high time for a lazy student to think about that seriously now.

Note: This is a brief transcript of actions related to my recent hard disk crash recovery. I'm publishing it here in the hope it might be of use to someone someday, just as all those similar posts out there are every so often of great use to me. So if you, dear reader, are not really interested in replacing a hard disk of your DELL PC, you better save your time and skip to the next post.

A pair of days ago I accidentally managed to test what happens if you throw a running 3-year-old DELL XPS M1210 laptop from a height of about 1.3 meters against solid floor. The result, fortunately, was radically different from what one might expect after observing that painful inelastic crash. After switching the screen off for a period of 5 seconds or so (the reasons behind this behavior being a complete mystery for me) the laptop happily resumed as if nothing had happened. A later examination revealed that the only part that was damaged was the hard disk where a number of files became unreadable.

I presumed that it must have been the result of a strong head crash. Common knowledge suggests that a head-crashed hard disk should better be replaced, even if it continues functioning. This is because new head crashes are much more probable after the first one has happened. Thus, I went to the shop and got myself a new average-grade 160Gb SATA hard disk (these are surprisingly cheap nowadays, btw). I also bought a small external case to put my old drive into, so that I could continue using it as an external storage medium.

In principle, the whole procedure could have ended here: I could have taken the old hard disk out, put the new one in, installed the OS onto the new disk from a CD and copied my files from the old disk with the help of the external case. However, there was one thing I didn't like about this approach. If I were to restart with a blank OS, I'd have to bother installing the proper drivers as well as several pieces of software that were shipped with the factory preinstallation of Windows XP (in particular, that enormously useless yet really impressive Logitech Video Effects webcam feature). I knew, however, that there was a way to restore the disk to the factory setting so I went on to figure out how to do it for a new hard disk. In hindsight, the whole procedure is actually rather straightforward, at least if you appreciate the virtues of the dd command.

DELL System Restore Partition

It seems that most DELL laptops nowadays come with a "DELL System Restore" feature, which means that there is a hidden partition on the hard disk that stores the factory-installed Ghost image of the system drive. If at boot time you press Ctrl+F11, you get the opportunity to write this image to disk thus destroying all your data but bringing the computer to its retail state.

The hidden partition is labeled DellRestore and besides the image file it contains a bootable DOS operating system (yes, real DOS!), the program for restoring the Ghost image (restore.exe) and an autoexec.bat script that invokes this program on boot. So, if I'm not mistaken, by pressing Ctrl+F11 you just direct the laptop to boot the DellRestore partition.

In theory, if you mirror the partition structure of your old hard drive on the new one and copy the data of the DellRestore partition, it should be possible to simply put in the new drive and press Ctrl+F11 for a proper restoration. However, my new drive was larger in capacity than the old one so I didn't want to mirror the partition structure exactly and I ended up with a somewhat more complicated procedure. The following is an approximate list of steps I went through. Don't try repeating them unless you really understand everything, though. You are also strongly advised to visit this site first.

The Walkthrough

1. I needed two bootable CDs here: one Knoppix Live CD and one DOS bootable CD.
2. First, keep the old (damaged) hard disk in the laptop, put the new disk into the external case, but don't plug it in yet.
3. Boot the Knoppix CD, when it starts switch to the command line (Ctrl+Alt+F1)
4. Ensure that the laptop's hard disk is seen as /dev/sda and examine its partition table:
   # cfdisk /dev/sda
5. It should have 3 partitions: DellUtility (sda1), the main NTFS partition (sda2) and DellRestore (sda3). Write down their sizes and quit cfdisk.
6. Plug in the new disk (the one in the external case) into the USB port. Ensure that OS detects it: type
   # dmesg
   and examine the output.
7. 

   New Drive's Partition Table

   Type
   # cfdisk /dev/sdb
   and create a partition table for the new disk that mimics the one of the old one. In my case I created the first DellUtility partition of the same size and type as was sda1. I then added one NTFS partition (for the main Windows OS) and a small Linux partition (just for fun) choosing the sizes of both to my liking. Finally the fourth partition was created of the same size and type as sda3. See Figure.

8. Copy the data of sda1 to sdb1 and sda3 to sdb4.
   # dd if=/dev/sda1 of=/dev/sdb1 bs=1024
# dd if=/dev/sda3 of=/dev/sdb4 bs=1024
9. Copy the master boot record of the old drive to the new one.
   # dd if=/dev/sda of=/dev/sdb bs=446 count=1
10. Now, shutdown Knoppix
    # shutdown -h now
    remove the old disk from the laptop, take the new disk from the case and put it into the laptop. Now boot the DOS CD.
11. When in DOS, go to disk C: (this is the DellRestore partition) subdirectory bat\:
    > cd c:\bat
12. Execute restore.bat
> restore.bat
    This should initiate the restore process and write the factory image to your second partition.
13. After the restore process completed I somewhy still had the problem that the system would not boot. I booted Knoppix, opened the partition table (cfdisk /dev/sda) and discovered that the bootable flag of the second partition was gone after the restoration process. Making the partition bootable again and restarting fixed the problem.

That's it.

I received a number of "why" and "how" questions regarding the pri.ee domain name of this site and I thought the answers are worth a post. The technically savvy audience can safely skip it, though.

The pri.ee subdomain is reserved by EENet for private individuals, who have an estonian ID code. The registration is free of charge and very simple: you just fill in a short form and wait a day or two until your application is processed. As a result you end up with a simple affiliation-free way of designating your site. Of course, it does not have the bling of a www.your-name.com, but I find it quite appropriate for an aspiring blog (and besides, I'm just too greedy and lazy to bother paying for the privilege of a flashy name for my homepage).

Now on to the "how" part. The only potentially tricky issue of the registration process is the need to fill in the "Name servers" field. Why do you need that and why can't you just directly provide the IP address of the server where you host your site? Well, if you could register the specific IP of your server with EENet, you would have to to contact EENet every time your hosting provider changed, right? In addition, you would need to bother EENet about any subdomain (i.e. <whatever>.yourname.pri.ee) you might be willing to add in the future. Certainly not the most convenient option. Therefore, instead of providing an IP address directly, you specify a reference to an intermediate server, which will perform the mapping of your domain name (and any subdomains) to IP addresses. That's how the internet domain naming system actually works.

So which name server should you choose? Most reasonable hosting providers (that is, the ones that allow to host arbitrary domains) allow you to use their name servers for mapping your domain name. The exact server names depend on the provider and you should consult the documentation. For example, if you were hosting your site at 110mb.com (which is here just an arbitrarily chosen example of a reasonable free web hosting I'm aware of), the corresponding name servers would be ns1.110mb.com and ns2.110mb.com.

However, using the name server of your provider is, to my mind, not the best option. In most cases the provider will not allow you to add subdomains and if you change your hosting you'll probably lose access to the name server, too. Thus, a smarter choice would be to manage your domain names yourself using an independent name server. Luckily enough, there are several name servers out there that you can use completely free of charge (or for a symbolic donation): EveryDNS and EditDNS are two examples of such services that I know of.

After you register an account with, say, EveryDNS, you can specify the EveryDNS nameservers (ns1.everydns.net, ..., ns4.everydns.net) in the pri.ee domain registration form. You are now free to configure arbitrary address records for yourname.pri.ee or <whatever>.yourname.pri.ee to your liking.

To summarize, here how one can get a reasonable website with a pri.ee domain name for free:

1. Register with a reasonable web hosting provider
   • 110mb.com is one simple free option (with an exception that they charge $10 once if you need MySQL)
   • other options
2. Register a DNS account
   • EveryDNS
   • other options
3. Fill out this form.
   • If you chose EveryDNS in step 2, state ns1.everydns.net, ns2.everydns.net, ns3.everydns.net, ns4.everydns.net as your name servers.
   • Wait for a day or two.
4. Suppose you applied for yourname.pri.ee (the domain is still free, by the way!), then:
   • Add this domain in your hosting's control panel and upload your website.
   • Add this domain to your DNS account.
     • You can add an A ("address") record mapping yourname.pri.ee to an IP address.
     • Alternatively, you can add a NS ("name server") record referencing yourname.pri.ee further to ns1.110mb.com (or whatever name server your hoster provides).
5. Profit!

Probability theory is often used as a sound mathematical foundation to formalize and derive solutions to the real-life problems in fields such as game theory, decision theory or theoretical economics. However, it often turns out that the somewhat simplistic "traditional" probabilistic approach is insufficient to formalize the real world, and this results in a large number of rather curious paradoxes.

One of my favourite examples is the Ellsberg's paradox, which goes as follows. Imagine that you are presented with an urn, containing 3 white balls and 5 other balls, that can be gray or black (but you don't know how many of these 5 exactly are gray, and how many are black). You will now draw one ball from the urn at random, and you have to choose between one of the two gambles:

1A)

You win if you draw a white ball.

1B)

You win if you draw a black ball.

Which one would you prefer to play? Next, imagine the same urn with the same balls, but the following choice of gambles:

2A)

You win if you draw either a white or a gray ball.

2B)

You win if you draw either a black or a gray ball.

The paradox lies in the fact, that most people would strictly prefer 1A to 1B, and 2B to 2A, which seems illogical. Indeed, let the number of white balls be W=3, the number of gray balls be G and the number of black balls - B. If you prefer 1A to 1B, you seem to be presuming that W > B. But then W+G > B+G and you should necessarily also be preferring 2A to 2B.

What is the problem here? Of course, the problem lies in the uncertainty behind the number of black balls. We know absolutely nothing about it, and we have to guess. Putting it in Bayesian terms, in order to make a decision we have specify our prior belief in what is the probability that there would be 0, 1, 2, 3, 4 or 5 black balls in the urn. The classical way of modeling the "complete uncertainty" would be to state that all the options are equiprobable. In this case the probability of having more black balls in the urn than the white balls is only 2/6 (this can happen when there are 4 or 5 black balls, each option having probability 1/6), and it is therefore reasonable to bet on the whites. We should therefore prefer 1A to 1B and 2A to 2B.

The real life, however, demonstrates that the above logic does not adequately describe how most people decide in practice. The reason is that we would not assign equal probabilities to the presumed number of black balls in the urn. Moreover, in the two situations our prior beliefs would differ, and there is a good reason for that.

If the whole game were real, there would be someone who had proposed it to us in the first place. This someone was also responsible for the number of black balls in the urn. If we knew who this person was, we could base our prior belief on our knowledge of that person's motives and character traits. Is he a kindhearted person who wants us to win, or is he an evil adversary who would do everything to make us lose? In our situation we don't know, and we have to guess. Would it be natural to presume the uncertainty to be a kindhearted friend? No, for at least the following reasons:

• If the initiator of the game is not a complete idiot, he would aim at gaining something from it, or why would he arrange the game in the first place?
• If we bet on the kindness of the opponent we can lose a lot when mistaken. If, on the contrary, we presume the opponent to be evil rather than kind, we are choosing a more robust solution: it will also work fine for the kind opponent.

Therefore, it is natural to regard any such game as being played against an adversary and skew our prior beliefs to the safer, more robust side. The statement of the problem does not clearly require the adversary to select the same number of black balls for the two situations. Thus, depending on the setting, the safe side may be different. Now it becomes clear why in the first case it is reasonable to presume that the number of black balls is probably less than the number of white balls: this is the only way the adversary can make our life more difficult. In the second case, the adversary would prefer the contrary: a larger number of black balls. Therefore, we would be better off reversing our preferences. This, it seems to me, explains the above paradox and also nicely illustrates how the popular way of modeling total uncertainty using a uniform prior irrespective of the context fails to consider the real-life common sense biases.

The somewhat strange issue remains, however. If you now rephrase the original problem more precisely and define that the number of black balls is uniformly distributed, many people will still intuitively tend to prefer 2B over 2A. One reason for that is philosophical: we might believe that the game with a uniform prior on the black balls is so unrealistic, that we shall never really have the chance to take a decision in such a setting. Thus, there is nothing wrong in providing a "wrong" answer for this case, and it is still reasonable to prefer the "wrong" decision because in practice it is more robust. Secondly, I think most people never really grasp the notion of true uniform randomness. Intuitively, the odds are always against us.

Appendix

There are still a pair of subtleties behind the Ellsberg's problem, which might be of limited interest to you, but I find the discussion somewhat incomplete without them. Read on if really want to get bored.

Namely, what if we especially stress, that you have to play both games, and both of them from the same urn? Note that in this case the paradox is not that obvious any more: you will probably think twice before betting on white and black simultaneously. In fact, you'd probably base your decision on whether you wish to win at least one or rather both of the games. Secondly, what if we say that you play both games simultaneously by picking just one ball? This would provide an additional twist, as we shall see in a moment.

I. Two independent games

So first of all, consider the setting where you have one urn, and you play two games by drawing two balls with replacement. Consider two goals: winning at least one of the two games, and winning both.

I-a) Winning at least one game

To undestand the problem we compute the probabilities of winning game 1A, 1B, 2A, 2B for different numbers of black balls, and then the probabilities of winning at least one of two games for our different choices:

Now the problem can be regarded as a classical game between us and "the odds": we want to maximize our probabilities by choosing the gamble correctly, and "the odds" wants to minimize our chances by providing us with a bad number of black balls. The game presented above has no Nash equilibrium, but it seems that the choice of 3 black balls is the worst for us on average. And if we follow this pessimistic assumption, we see that the correct choice would be to pick consistently either both "A" or both "B" gambles (a further look suggests that both "A"-s is probably the better choice of the two).

I-b) Winning two games
Next, assume that we really need to win both of the games. The following table summarizes our options:

This game actually has a Nash equilibrium, realized when we select options 1A and 2B. Remarkably, it corresponds exactly to the claim of the paradox: when we need to win both games and are pessimistic about the odds, we should prefer the options with the least amount of uncertainty.

II. Two dependent games
Finally, what if both games are played simultaneously by taking just one ball from the urn. In this case we also have two versions: aiming to win at least one, or aiming to win both games.

II-a) Winning at least one game
The solution here is to choose either the 1A-2B or the 1B-2A version, which always guarantees exactly one win. Indeed, if you pick a white ball, you win 1A, and otherwise you win 2B. The game matrix is the following:

II-b) Winning both games
The game matrix looks as follows:

The situation here is contrary to the previous: if you win 1A, you necessarily lose 2B, so here you have to bet both "A"-s to achieve a Nash equilibrium.

Summary
If you managed to read to this point, then I hope you've got the main idea, but let me summarize it once more: the main "problem" with the Ellsberg's paradox (as well as a number of other similar paradoxes) can be in part due to the fact that pure "uniform-prior" probability theory is not the correct way to approach game-theoretical problems, as it tends to hide from view a number of aspects that we, as humans, usually handle nearly subconsciously.