Please do your SEO somewhere else

Recently people have started to post spam comments that only serve to advertise their sites/trainings in India. For the time being I have deactivated the comment function. Do your SEO somewhere else.

Gotcha: CDH manager killed, but no error log, on VM

I recently experienced a problem where the Cloudera Manager silently died during startup or a few seconds after. No useful entries in the error log, nothing. If this had been a problem with Heap space, I would have seen an OutOfMemoryError. Some other problem, I would probably have seen some kind of log entry. But the OS just killed the service for some reason.

I was using a VM managed by vagrant, and it turns out the base box I was using had the memory configured by default to be around 512MB, while the Cloudera Manager was configured to have a max heap space of 2 GB. Ouch. What happened was that the service would at some point exhaust the available memory, and the OS killed it.

I finally found the important information hidden on the requirements page: http://www.cloudera.com/content/cloudera/en/documentation/core/v5-3-x/topics/cm_ig_cm_requirements.html

There it says (highlighting added):

• RAM - 4 GB is recommended for most cases and is required when using Oracle databases. 2 GB may be sufficient for non-Oracle deployments with fewer than 100 hosts. However, to run the Cloudera Manager Server on a machine with 2 GB of RAM, you must tune down its maximum heap size (by modifying -Xmx in /etc/default/cloudera-scm-server). Otherwise the kernel may kill the Server for consuming too much RAM.

Well thank you, may I suggest you put something like that on the Troubleshooting page as well?

After seeing this, it didn't take long to figure out what was going on (that was after, roughly, 2 or 3 days of debugging...)

Connecting to Hadoop CDH with a windows client

Random notes and links on getting Windows clients to work with CDH-5.3.1:

1. Use the CDH-releases of your hadoop libraries, see http://blog.cloudera.com/blog/2012/08/developing-cdh-applications-with-maven-and-eclipse/  (for other hadoop distributions, this just means: use the same versions on the client as in the cluster)
2. Set the necessary properties for cross-os functioning (why, oh why is such a thing necessary?), and get winutils.exe, see https://github.com/spring-projects/spring-hadoop/wiki/Using-a-Windows-client-together-with-a-Linux-cluster
3. set the environment variable HADOOP_USERNAME to an appropriate value, see http://stackoverflow.com/a/11062529/1319284
4. if you are using HDFS (which you probably are), you need to add hadoop-hdfs to your classpath if it is not already, see http://stackoverflow.com/a/24492225/1319284
5. check the firewall rules of the nodes, on centOS you can do this with system-config-firewall. See https://www.centos.org/docs/5/html/Deployment_Guide-en-US/ch-fw.html, see here for a list of the ports used by the various CDH components http://www.cloudera.com/content/cloudera/en/documentation/core/latest/topics/cdh_ig_ports_cdh5.html
6. make sure all configured host names can be resolved, and edit the Hosts file if necessary. (It is located under C:\Windows\System32\drivers\etc\Hosts)
7. Make sure your compiler compliance level is set to target the right Java version. Right now this is 1.7. Failing to do so generates errors like Unsupported major.minor version 52.0. See here for example http://stackoverflow.com/questions/22489398/unsupported-major-minor-version-52-0
8. When using eclipse, make sure to export a jar (or build with maven), and then add it to the classpath of the Launch command. That way, Job.setJarByClass will find the jar which can then be uploaded to the cluster. Granted, this is a little hacky, but works.

After doing all this, I successfully ran my MapReduce job from Eclipse.

[Update]
For CDH 5.5.0 (Hadoop 2.6.0), a binary build with winutils.exe can be downloaded from http://www.barik.net/archive/2015/01/19/172716/
In addition to setting hadoop.home.dir, java.library.path must be set to the bin directory.

The mean is a horrible measure for profiling/benchmarking

The mean is a horrible measure for profiling/benchmarking. When the computation chokes, it generally results in a peak execution time. The mean as measure is not good when you have extreme outliers like that. The median is much more robust in such cases.


So: Don't average over your execution time when you benchmark an algorithm, take the median!

My Code is in the Juno release train!

I just wanted to point out that Code Recommenders, and with it Jayes, is in the Juno release train! (see http://www.eclipse.org/org/press-release/20120627_junorelease.php) How sweet is that? Code i wrote as my Bachelor's thesis is now at Eclipse :-)

The Code Recommenders feature is distributed as part of the "Eclipse IDE for Java Developers" Download at Eclipse, thus my code now lives on thousands of developer machines :-D

Minimizing Horn formulas using domain knowledge

Assume you have several implications

(x1 & x2) -> x3
(x1 & !x2) -> x3
...

As, often, you will want to query whether x3 needs to be true for different truth values of your different variables, you might want to optimize your formulas with respect to the number of literals.

For a given right-hand side variable, this is equivalent to a (DNF) logic minimization task that can be done, e.g. with the Quine-McCluskey Algorithm. As your left-hand-side formulas form a formula in DNF, the minterms of this formula are exactly those left-hand-side formulas.

The formula above can be optimised by optimizing (x1 & x2) || (x1 & !x2), which would yield the formula x1, and thus your optimized implication x1 -> x3.

What does this have to do with HornSAT? As you may have noticed, my examples are not Horn formulas. However, in practice you will sometimes model a problem as HornSAT that has additional, implicit constraints. For example, if some variable v potentially has n states, you may model this as n logical variables in your formulas.

These variables have properties that you normally don't explicity model in your formulas, because they only blow up the logical representation without helping the original problem. The property i am refering to is the assumption that v will take exactly one of it's n states, thus exactly one of the n logical variables will be true at any time.

This (also called principle of bivalence for logic) is the same property that allows logic minimization! Thus, using domain knowledge, one can, with a little alteration of "normal" logic minimization algorithms, derive domain-specific logic minimization algorithms. I did this once for extracting logical rules that were implicitly contained inside bayesian networks (didn't help for inference, but gave me the idea).

Note that, while HornSAT is an easy problem, logic minimization is hard.

Jayes 0.2.0 release

Jayes 0.2.0 is here!

I finally removed the SNAPSHOT marker from the plugin.xml and pom.xml files - which means i consider this a release version. Find it at Github

What is Jayes?

Jayes is an open-source Bayesian Network library written in pure Java. I wrote it as part of my Bachelor's thesis. It is used by the Code Recommenders project at Eclipse, where it predicts method calls for code completion. It performs very well, as i showed in my Bachelor's thesis (also available in the repository), and can compete even with native Bayesian Network libraries.

Why version it 0.2.0?

The reason the current version number is 0.2.0 is that at the point where i first wrote Jayes, the Code Recommenders project was in version 0.2.0. This version number is in no wise related to the state of the development of the library.

Features in version 0.2.0

- exact inference in Bayesian Networks with discrete-valued variables
- File formats: XMLBIF v0.3, GeNIe's XDSL format

License

Jayes is licensed under the EPL 1.0

Tools I don't want to miss

Inkscape

Inkscape is an open-source SVG editor. Vector graphics have many advantages over pixel graphics that can be done with e.g. GIMP, Paint etc.
I had to draw several diagrams for my bachelors thesis, and I found Inkscape offers lots of functions that make it suitable for that:

• alignment of different objects
• drawing perfect squares / circles (press Ctrl while you draw the shape)
• (very important!) export to PDF and PNG format

The only thing I feel it lacks (maybe i just haven't found that function?) is something modern pixel graphics programs have: multiple layers. But apart from that, it is perfect for drawing diagrams etc. especially when you will need to scale them, as SVG is scale-independent.

Skype / VoIP

because Instant Messaging and mailing sometimes is not productive enough. I spared so much time in university by communicating with my fellow students through Skype, it's ridiculous. Which medium is best for your communication really depends on your task, but sometimes calling someone is just better than messaging!

Cygwin

Yes, i'm still a Windows user, but i can't live without my shell anymore. I do most things through my IDE or some GUI, but often enough, something needs to be automated through a script, and then i open up my cygwin shell and just love it :-)

SSH-Clients (e.g. PuTTy)

It happens more and more that I need to run stuff remotely, so...

Colaboration Tool: Online Screen Sharing

While this can also be done with e.g. Skype, maybe you find this useful:
http://www.screenleap.com/ allows for the sharing of screens through a browser interface. Have fun!

The importance of secure email accounts

Email accounts are extremely vulnerable to attacks on the online identity. Why? If someone can capture an email-account, this at the same time means he gets the power to capture accounts on other websites e.g. facebook, paypal(?) etc.
This is because people tend to register one single email address for multiple other accounts, which gives attackers the power to reset passwords, and thus gain control over these other accounts. Fortunately, for some of these accounts you need to know the nickname that is registered. I don't have the statistics, but i would guess the nicknames aren't incredibly hard to guess most of the time (people probably tend to reuse those).

==> keep your email accounts safe guys (especially don't use your email password for other accounts!)

What do chatbots say to each other when no human is around?

Researchers, probably just for fun, asked that question - and surprisingly, a pretty funny (albeit a little artificial) dialogue is what came out. Watch the video here
I find it hilarious :-D

The greatness of CSV

CSV - comma-seperated values - is a simple file-format you all should know. It just consists of values, seperated by commas (or tabs, or whatever), with linebreaks seperating, well, the different lines (or records, or whatever your data may look like). You probably already knew that.

Now, let's suppose you have some data, in a CSV table. Let's also suppose the first line contains the names of the columns, like that:

"No.", "Name", "Price"
1, "Chocolade", 0.99
2, "Noodles", 0.39

and so on. As you see, really simple. Actually, why do i feel like writing about this stuff, it looks that simple you wouldn't think it's interesting to talk about it altogether. I mean, there are things like JSON nowadays...

The reason is, i found you can do an incredible lot with those simple CSV-tables.

1. easy to generate, easy to parse, thus also easy to transform in other formats
2. easy to combine, if you have several matching tables. A quick sed '1d' file1 >> file2 does the job
3. stripping the header, it is also easy to sort the lines using the sort command (see manpage)
4. import in programs like Excel, OpenOffice Calc, etc.
5. direct plotting with gnuplot http://www.gnuplot.info/docs_4.2/gnuplot.html#x1-17200043.14
6. many database programs support CSV as data source, so SQL querying is also an option. I haven't found a command-line tool to integrate SQL-Queries in a scripting workflow, but writing such a tool is not the biggest effort.(there are open-source CSV-database drivers or similar out there, for example h2database has commands to read from and write to CSV-files)
7. as i wrote here, there are also tools to directly transform a CSV-table to a LaTeX-table.
8. data-mining applications like Weka...
9. you name it ;-)

Converting an Excel/CSV table to LaTeX

Hi! Obviously, if you are reading this, you want a way to convert your Excel/CSV-tables to a latex table. There are some tools out there (csv2latex), but i also found this simple online converter i'd like to share:

Excel To Latex

Works with Excel Tables, CSV, and tables with other seperators as well. It does not, however, generate the table header, so you have to do that on your own.
I find this a little easier to use than a command-line tool, but of course such a tool is still useful for some. Just sorch for csv2latex.

LaTeX: Referencing Figures

You may have had the following problem:
You want to reference a figure in your LaTeX-document, but instead of it's number, you get the section/subsection number.

First, the solution: You simply have to put the \label after the \caption of the figure.

Second, why: It seems the caption is the thing that actually SETS the number. This is a "feature" that allows multiple captions/labels per figure.

Can you boot from an email-account?

Hi! You know how there are programs like Gmail Drive that let you use your email account as normal storage space? And you also know how you can boot from the network, right?

Now, if we had our OS mirrored to our Gmail account using Gmail drive, and have some other PC forward the virtual drive to us over the LAN, could we actually boot from that?

I'd love seeing anyone trying this and tell about his experience. Of course there is absolutely no use to this, but i felt it would be a funny experiment.

Google Flu Trends

Hi, check out this: Google Flu Trends

Apparently, Google is generating flu statistics from their search statistics - and it seems to work! Makes you wonder what other kind of information might be hidden in that statistical data, doesn't it?

Infinity: Hypercubes

We all know what a square and a cube is, and their generalization for higher dimensions is called Hypercube.

Now, let's see... A square has four vertices (0,0) , (0,1), (1,0), (1,1), thus representing 2 bits of information in it's vertices. A cube has 8 = 2^3 vertices and so on... You get the image.

According to wikipedia, the human genome has 3 billion DNA base pairs. We ll know there are four bases, thus every base encodes 2 bits of information. Any human's DNA is therefore one vertex of a 6 billion dimensional Hypercube. Somewhat scary, isn't it? Even more if we realize that all humans together, wo ever lived and will live, only cover an incredibly small subset of the vertices of that hypercube.

Now, let's get to something bigger - Infinity. We can encode every natural number as an infinite sequence of 0's and 1's. Therefore, every natural number is a vertex of an infinite dimensional hypercube. Note that the power set of the natural numbers can as well be expressed as an infinite sequence of 0's and 1's showing whether a number is in the subset or not. However, this does not show N = P(N), as N does not cover any vertices with an infinite amount of 1's in the sequence, while P(N) does. P(N) actually covers ALL vertices of that hypercube.

Now to an even fancier Vector space: The space of R -> R is also a vector space, but this space has uncountably infinite base vectors. R -> {0,1} is a subset of that space, our hypercube again (this time with oncountably infinite dimensions).

... Wait a second, didn't the last one look familiar? Right, looks like binary classification, doesn't it? Binary classifiers are the vertices of that last hypercube. This can be generalized to R^d -> R, but i won't discuss that further. Can we do search in such a space, maybe to find a binary classifier? Of course this is not as good as an SVM or even a Neural Network, but for the heck of it: Why not build a Bounding Volume Hierarchy (Bounding Squares, that is)? Here is how i imagine such an algorithm:

let train(i) be the i'th train data point. Let f(]x,y[) be defined such that for all x' in ]x,y[ f(x') = f(]x,y[) -> we are building some sort of hierarchical structure

1.) set f(]-∞,∞[) = 0
2.) partition(f,-∞,∞,0,n)

partition(f,a,b,i,j):-
3.) let m = (i - j)/2
3.) set f(]a,b[) = label(train(m))
4.) partition(a,train(m),i,m - 1)
5.) partition(train(m),b,m+1,j)

This should run in O(n) or O(n log n) depending on our data structures.
This can be generalized to more than 1 dimension, but it's obvious that this yields a classifier prone to overfitting (and also, i didn't want to invest too much time in something obviously bad).

How secure are my windows passwords?

I just stumbled upon this Guide for cracking Passwords, through a reference on heise.de.
As you might know, passwords are most of the time (hopefully) not stored in clear text, but in the form of one-way hashes. Thus, even if an attacker got hold of a complete copy of the user data (username + password), this does not automatically mean he will be able to access the user's data immediately.
Hash-Functions, to be secure, have to have the property that it is difficult to determine to a given hash(x) one possible x. Some hash-functions however, are a little weak, at least they become weak as the computational power of PCs grow.

For short passwords, Windows (before Vista) seems to store such a weak hash-value. The Guide above has links to the Windows articles showing how to deactivate this behavior. Also, the Guide gives a way for encrypting the hash-file, making things a little more complicated for the potentiall attacker.

Anyway, the truth is: no one actually ever needs your windows password to access your data. If someone has access to the pc, he/she can just boot it from a Boot Disk and access any data that is stored on the hard drive. Since cracking the passwords as described above would need access to the PC, we can assume the attacker has that access. In such a case, it is much easier to just bypass the OS and boot from a CD. The only protection against this is encrypting the hard drive, and/or setting up a BIOS password. If you lose your password, however, you will lose your data (in case of the encrypted hard drive) or your laptop altogether (in the case of PC, the BIOS password can be reset, but it's a hassle). Also, if only using BIOS password, you data could still be read by stealing the (non-encrypted) Hard Drive.


Another easy way to get access to a windows account described in the guide above, is to reset the account's password (which is far easier than cracking it). There are programs which can do this, see the guide for details. The good message about this is, you can reset your password if you have forgotten it! Plus, if someone did this to you, you would be able to realize there was an attack.

I also found a link about hard drive password protection (which is not like Encryption, but like the BIOS-Password) here.

Solving HornSAT in linear time

Recently, i wanted to program a simple horn sat solver for a project (turned out i didn't need it, oh well).
I couldn't find anything on the net (in reasonable time) about how to solve HornSAT in linear time, only references to that it's possible. The naive approach, however, at least the one i took, has quadratic worst-case complexity. Now i thought i might spread the knowledge a bit about how to solve the horn satisfiability problem in linear time.
See also Unit Propagation

---

1.) build a directed (bipartite) graph, connecting the Horn clauses to their respective positive literal (if they have one), and connecting the literals to all clauses where they appear negated.
2.)[UPDATE] for every clause c not containing a negated literal, do {
if c has no positive literal STOP -> unsatisfiable
else propagate(c)
}

3.) finally, the function for the unit propagation:

propagate(c) :-
if the positive literal of c (p) is not yet marked true {

mark p true
for all (p,c') in the Edge set of the graph{
remove p from c'
if c' has no more negated literals, propagate(c')
}

}

---

The marked literals form the minimal model of that Horn formula.

Because every literal is only marked true once, the whole algorithm runs in linear time (with respect to the number of literals, because of the graph building).

[Update]
While thinking about this some more, i figured the above algorithm is only better than the naive one, if the number of literals is in O(#clauses²). For completeness, here the algorithm i call the "naive":

---

while there exists a clause c without negative literals{

if c has no positive literal then STOP -> formula not satisfiable;
mark the variable of the positive literal of c as true;
for all clauses c'  remove the just marked literal from the list of negated literals of c'

}

---

Let c be the number of clauses and l the number of literals.
With the proper implementation, the naive algorithm can run in O(min(c², cl)). This is better then the algorithm above if l is in Ω(c²).
We can easily check this by summing the sizes of the sets of negated literals, which can be done in O(c). If we wire this all together, we get an algorithm in O(min(l,c²)), as c is in O(l).

Here is also a paper on linear time algorithms for Horn Sat: Link

What to do when you cannot post comments on blogger.com

Hi! Just a short notice:
Some people have problems not being able to post comments on blogger. Happened to me actually.
The reason for this is that blogger uses third-party cookies for the commenting. I have no clue why they would do that (probably trying to give a cookie from blogger.com or google.com while you are actually at blogspot.com).
Anyway, the solution is accepting third-party cookies. You can do that through your browser configuration.


What are third-party cookies?

Websites use third-party cookies for tracking people, to identify the users when they visit (revisit, actually) their site. This could ALSO be done without cookies, through the IP-Address (except for some Providers, where the IP-Address changes repeatedly, or someone using Thor), but the IP-Address changes every time you connect to the Internet (normally. that is), so they can only be used for short-term tracking. The really interesting data comes from long-term tracking, as web sites can get a feeling for how many regular visitors they really have. So, third-party cookies don't harm you physically, but to a certain extent, violate your privacy.