September 30, 2006

Beta distribution

[Math_] Neat fact about the Beta distribution: starting with a uniform prior, after observing k/n successes, the CDF for parameter p (the probability of success in a single trial), i.e. the probability that p is smaller than a certain value x, is equal to the probability that we get k+1 or more successes out of n+1 trials using that x!
Full post... Related link

Mathematics of Generalization

[Learning_ Books_] Mathematics of Generalization was one of those books that had been waiting on my shelf for quite some time. Partly because I was intimidated by the possible difficulty of mathematics. It turns out the articles are very well written and not that intimidating at all. I will post small perls of wisdom I get from the book in the comments of this post.

Full post... Related link

September 29, 2006

Kralın Yeni Usu - Roger Penrose

Penrose'un "Kralın Yeni Usu" isimli kitabının dayandığı "Gödel'in
teoremi, matematik formülizasyon ile bazı önermelerin doğruluğunun ya
da yanlışlığının ispatlanamayacağını söyler ama bir matematikçi
sezgileri ile bu önermelerin doğruluğu hakkında rahatlıkla yorum
yapabilir" varsayımı üzerine yorumlar...

Gödel'in teoremi insan makine ayrımı yapmaz. Söylediği tek şey
aritmetik kurallarını içeren herhangi bir sistemin hem complete (yani
her önermeye true/false assign edebilecek) hem de consistent (yani
contradiction içermeyecek) olmasının mümkün olmadığı. İnsanlar pekala
consistent olmayı bırakıp istedikleri önermeye istedikleri doğruluğu
verebilirler - bu onların makinelerin yapamadığı birşeyi yapabildiği
anlamına gelmez. Bilgisayarları fuzzy, deneyim tabanlı bir şekilde
programlayıp 99% doğru tahminlerde bulunmalarını engelleyecek herhangi bir prensip de yok.

Şu sezgi konusunu bir örnekle açalım: Cantor reel sayıların
oluşturduğu sonsuzluğun, tam sayıların oluşturduğu sonsuzluktan daha
büyük olduğunu gösterdi. Gösteremediği şey ise bu ikisi arasında bir
sonsuzluk olup olmadığı. Şimdi sezgimiz bu konuda ne diyor? Benimki
birşey demiyor. Diyenler olabilir. Fakat daha sonra ispatlandı ki
böyle bir ara-sonsuzluk olduğunu varsaysak da consistent bir sistem
elde ediyoruz, varsaymasak da consistent bir sistem elde ediyoruz.
Peki şimdi sezgimiz ne diyor? Uğraştığımız probleme göre belki bu
modellerden birini ya da diğerini tercih ederiz. Örneğin geometride
paralel aksiyomun doğruluğunu tüm matematikçiler 2000 yıl boyunca
sezdiler. Fakat önce bu aksiyomun alternatiflerinin de consistent
olduğu, sonra da bazı problemleri incelemede (örneğin dünyanın eğimli
yüzeyi üzerine çizilen geometrik şekiller için) diğer aksiyom
seçeneklerinin daha uygun olduğu anlaşıldı. Bu örnek gösteriyor ki
sezilmesi gereken şey bir aksiyomun doğruluğu ya da yanlışlığından
ziyade onun modellediği objeye uygun olup olmadığı.

Bu da beni Penrose ile esas problemime getiriyor: birşey algoritmik mi
değil mi sorusu yanlış olan. Bir çiçek matematiksel midir? Bir
okyanus mantık kurallarına uyar mı? Sonuçta algoritmik sistemler,
matematik, mantık bizim evreni anlamak için kullandığımız diller.
Hiçbirşey kendi içinde matematiksel ya da algoritmik değil - bizim
onlara bakış açımız matematiksel ya da algoritmik olabilir.
Dolayısıyla matematiksel ya da algoritmik gibi sıfatlar incelenen
objeleri değil, incelemede kullanılan yöntemleri tanımlamak için
kullanılmalı. Peki bazı şeyleri (örneğin insan aklını) incelerken
belli dillerin (örneğin algoritmik yaklaşımın) yanlış olduğunu iddia
edemez miyiz? Burada doğru yanlıştan ziyade uygunluk uygunsuzluk
kavramını sorgulamak lazım. Bir objeyi (örneğin dünya üzerindeki
geometrik şekilleri) uygun olmayan bir dille (örneğin Euclidean
geometriyle) incelemeye kalkarsak yanlış sonuçlara varmayız - sadece
analiz olması gerektiğinden daha kompleks ve uzun olur.

Full post... Related link

September 27, 2006

Aklın Ötesi

Bana "aklın ötesinde" birşeyler olduğu iddiaları hep antipatik
gelmiştir. Herhalde eleştiriden hoşlanmayan liderlerin kullarını
uyutmak için kullandıkları genel bir kavram olabildiği için. Burada
sadece Tanrı kavramını kastetmiyorum. Kültürümüzde nedense böyle bir
oto-sansür var: "o konuyu çok düşünme, kafayı yersin" gibi. Bu bize
de mahsus değil sadece: Cantor'un sonsuzluk konusunu çok düşündüğü
için sonunda delirdiği popüler bir inanç. İki açıdan üzücü: birincisi
adamın delirme sebebi zamanının meslektaşları tarafından
anlaşılamamak, ikincisi insanlığa verdiği en büyük hediye sonsuzluğun
akıl tarafından tame edilmesi (evcilleştirilmesi?) olduğu halde onun
bu yendiği canavar tarafından delirtildiğinin iddia edilmesi...

Evrende anlayamayacağımız birşeyler olup olmadığı tabi ki tartışılır. Fakat bu tartışmanın henüz kesin sonuç vermediği konuları "anlaşılamaz" ilan etmek o konuda düşünceyi köreltmekten başka ne işe yarar? Bence bu tip belirsiz durumlarda iyimser olmak ve imkansızlığı ispatlanana kadar o konuyu anlamaya çalışmak doğru seçim.

Genel olarak "bir parçanın bütünü içeremeyeceği" kavramı insanın
kendi beynini - aklını anlayamayacağı konusunda da kullanıldığı için
üzerinde düşünmüşlüğüm var. Bu gün popüler olan complex systems
çalışmaları parçanın bütünü içerdiği örneklerle dolu: örneğin
fraktal'ların parçaları tüm fraktal'ı içerir. Bir bilgisayar gayet
rahat kendi çalışmasını simüle edebilir. Bir bilgisayar dili
kullanılarak o dilin kendisi define edilebilir. Yine bir bilgisayar
kullanılarak kısıtlı fiziksel bir evren simüle edilmesi, o evrende
evrimleşecek virtual yaratıkların bir gün akıl kazanarak daha komplex
bilgisayarlar dizayn etmeleri vs gibi olayların bilimsel olarak hiç
bir imkansızlığı yok. Parçaların bütünü içeremeyeceği kavramı
insanların sonlu nesnelerle (top, kova gibi) olan fiziksel deneyimine
analoji ile yaratılmış bir kavram. Cantor ile birlikte bu kavramın
sınırları ortaya çıktı, recursive function theory (yani bilgisayar
teorisi) ile birlikte pek çok pratik counter-example ortaya çıktı.

Peki imkansız birşey yok mu? Var: Mantıksal imkansızlıklar
(contradiction'ların bir arada yaşayamaması), computational
imkansızlıklar (bazı well defined fonksiyonların hiç bir şekilde insan
ya da makine ile compute edilemez oluşu), fiziksel imkansızlıklar
(heisenberg belirsizliği yüzünden fiziksel dünyayı istediğimiz
incelikte ölçemememiz), ve teknolojik imkansızlıklar (evrende yeterli
madde ve enerji olmadığı için belki galaksileri istediğimiz
konfigürasyona sokamayacağız, yeterli zaman olmadığı için onuncu
Ramsey sayısını hiç bir zaman hesaplayamayacağız vs.) Bunlar dışında
birileri birşeylere imkansız derse lütfen neden diye soralım.

Full post... Related link

September 21, 2006

Best visual illusion ever

This has got to be the strongest visual illusion I have seen. BTW I got to it from the web site of Jeff Bridges, which is very cool - www.jeffbridges.com. And i got to that using Stumble! - www.stumbleupon.com... I know I know I should be working right now...
Full post... Related link

September 16, 2006

Skeptics and True Believers by Chet Raymo

Faith reason sentezi konusunda okuyup etkilendiğim bir insan Chet
Raymo: "Skeptics and True Believers" kitabında Amerika'nın bible
belt'inde bizim kuran kursu tipinde bir eğitimle yetiştikten sonra
fizik PhD'si yaparken nasıl inanç sisteminin çöktüğünü anlatıyor.
İşin ilginç tarafı sonunda cynical bir atheist olarak değil inancını
revize edip koruyarak çıkmış oluşu.

Vaktiyle bilim ve din ile uğraşan insan grubu birken bugün uzlaşamıyor
olmaları dinin yozlaşmasından mı, bir güç savaşı mı bilmiyorum. Belki
Judeo-Christian kültürün bir enfeksiyonu sadece. Doğu dinlerinde
böyle bir problem var mı?

Skeptics and True Believers (Amazon)
http://www.sciencemusings.com
Tao is Silent
Full post... Related link

September 11, 2006

Bengi Mizrahi, M.S. 2006

Current position: Software Engineering Manager, Juniper Networks. (email, linkedin).
M.S. Thesis: Paraphrase Extraction from Parallel News Corpora. Koç University Department of Computer Engineering. September, 2006. (Download PDF).



Abstract:
Different expressions of the same statement is said to be paraphrases of each other. An example is the phrases 'solved' and 'found a solution to' in 'Alice solved the problem' and 'Alice found a solution to the problem'. Paraphrase Extraction is the method of finding and grouping such paraphrases from free text. Finding equivalent paraphrases and structures can be very beneficial in a number of NLP applications, such as Question Answering, Machine Translation, and Multi-text Summarization, e.g. in Question Answering, alternative questions can be created using alternative paraphrases. We attack the problem by first grouping news articles that describe the same event and then collecting sentence pairs from these articles that are semantically close to each other, and then finally extracting paraphrases out of these sentence pairs to learn paraphrase structures. The precision of finding two equivalent documents turned out to be 0.56 and 0.70 on average, when matching criterion was strict and flexible, respectively. We tried 9 different evaluation techniques for sentence-level matching. Although, exact word match count approach had a better precision value than the n-gram precision count approaches, paraphrase extraction phase shows that the latter approaches catch sentence pairs with higher quality pairs for paraphrase extraction. Our system can extract paraphrases with 0.66 precision when only equivalent document pairs are used as a test set.

Full post... Related link

September 06, 2006

Using Google as a Language Model

[Language_] A statistical language model assigns probabilities to the strings in a language. Speech recognition and other language technologies rely on language models to judge the likeliness of an utterance. The field has long been dominated by n-gram language models which estimate the probability for a word conditional on the previous n-1 words (where n is typically 3). Data sparseness is a big problem, no corpus contains enough samples of all n-word sequences. Here I present some experiments with using Google counts as a language model.

Some rough estimates to give the reader intuition on the sparseness of data: English has roughly 100,000 unique words. This means the number of unique bigrams is on the order of 10 billion and unique trigrams is on the order of 10^15. The distributions are far from flat: the most frequent word "the" occurs approximately 5% of the time. The frequency of a "typical" English noun would be in the 1/10,000 - 1/50,000 range, so to get a good sampling of its concordance (say to observe it 1000 times) would require a corpus of 50 million words. A typical novel contains 200,000 words. A year of Wall Street Journal has 20 million. The Gigaword news corpus from LDC contains roughly one billion (as the name suggests).

How many words does Google have? Well I took some sample words and did some calculations. The columns of the table below give:
1. word
2. bnc frequency in a million words
3. google count in millions of words
4. implied total number of words in google if it had the same ratios as bnc

a 21626 16770 7.75455e+11
in 18214 15360 8.43307e+11
of 29391 14030 4.77357e+11
the 61847 13880 2.24425e+11
to 16284 13850 8.50528e+11
and 26817 12740 4.75072e+11

whose 198 395 1.99495e+12
sculpture 13 64.8 4.98462e+12
current 133 1930 1.45113e+13
reliable 22 226 1.02727e+13
down 98 1540 1.57143e+13
execution 14 153 1.09286e+13
addressed 27 185 6.85185e+12
planted 14 31.9 2.27857e+12
ordered 49 179 3.65306e+12
division 90 553 6.14444e+12
barely 23 66.3 2.88261e+12
dancing 12 138 1.15e+13

My first intuition of using the most frequent words backfired. See, google gives document counts, not occurance counts. That means words that occur multiple times in a document get under-counted. So less frequent words give a more accurate guess (their document and occurance counts will be close). I take the number of English words indexed by Google to be 1e13 looking at the above data.

We still need to do smoothing. I used the baseline smoothing as described by Goodman and Chen and looked for the optimal parameters on some test data (it was hard to find pieces of text that do not exist in Google). Basically I searched for some numbers to multiply each k-gram estimate where k=0...n that gave me the highest likelihood. The biggest bang for the buck comes from 4-grams, in fact the increase in model likelihood from 3 to 4 grams is comparable to the one from 2 to 3 grams. When we go to 5 grams, not so hot.

Here is the results for the file A2/A20.txt from bnc (132 lines, 1557 words). a0 is multiplied by 1/vocabulary_size which is assumed to be 1e6. a1 is multiplied by the frequency of the word which is assumed to be google_count/1e13. a2..a6 are the coefficients of bigram...six-gram conditional probabilities.

bits a0 a1 a2 a3 a4 a5 a6
N=1 13.7334 .01925 .98075
N=2 9.3085 .01103 .03460 .95436
N=3 8.9581 .01167 .03649 .62960 .32224
N=4 8.5835 .01214 .03965 .52324 .15047 .27450
N=5 8.5453 .01218 .04013 .51352 .14090 .23877 .05449
N=6 8.5345 .01220 .04044 .50807 .14147 .23397 .04314 .02070

The resulting bit-rate per word is 8.5. The best models reported in Goodman and Chen dip below 7 bits with 10 million words of data and trigrams. The possible explanations are:

- I ignored sentence breaks. (Starting word of a sentence is conditioned on the last words in the previous sentence).
- They only used news data. (Their results on the brown corpus are significantly worse).
- Google counts are not very accurate. Here are some examples:
223 cherished memory is
497 most cherished memory is
958 author of the legend
1010 and author of the legend
- Bias due to document vs. occurance counts effect the most frequent words badly. (The frequency of "the" is 0.1% according to my estimate)
- I did nothing special for numbers, proper nouns etc. (They are not clear about the treatment of unknown words, but most likely they just relied on 1/vocabulary_size which they took to be about 50,000)

Which of these reasons dominate or whether there is another significant reason is a matter of future research :)


Full post...

September 05, 2006

Linux novell setup

[Hacking_] CIT's new Novell setup broke everything on my linux machine as usual. As there is no documentation about the changes it took me a while to get things working again. Here is a summary:

/etc/fstab: storage/dyuret.usr.ku /mnt/novell ncp defaults,server=storage,ipserver=storage,passwd=xxxxxx,volume=vol,uid=dyuret,gid=dyuret

system-config-printer: Server: login.ku.edu.tr, User: dyuret.usr.ku Queue: eng12.iprint


Full post...

September 03, 2006

J.B.S. Haldane

[Biology_] I first got to know J.B.S. Haldane as the author of one of my favorite quotes:

"I have come to the conclusion that my subjective account of my own motivation is largely mythical on almost all occasions. I don't know why I do things."

How prescient of him before we knew about Libet's half second delay and Gazzaniga's split brain patients.

It turns out he has very nice articles on the physics of animals and the future of science. What is it with these Scots?
On Being the Right Size

Also here are his predictions on the future of science written in 1923:
Daedalus, or, Science and the Future

With the exception of his pessimism on atomic power and optimism on the progress of biology and eugenics, I'd say he has quite a few accurate observations. On the evils of science I like how he turns the argument around and says the magnification of good and evil by science is what forces the common man to finally take action:

"I think then that the tendency of applied science is to magnify injustices until they become too intolerable to be borne, and the average man whom all the prophets and poets could not move, turns at least and extinguishes the evil at its source."


Full post... Related link