Putnam

http://www.math.purdue.edu/pow/ http://www.math.hmc.edu/putnam/ http://math.ucsd.edu/~pfitz/pastputnam.html

windows'da rm -rf

dataset\ klasorundeki tum .s2b uzantili dosyalari silelim: del dataset\*.s2b /s /f /q

Counting the number of non-zero bits in a a 32bit unsigned integer

from http://stackoverflow.com/questions/9244153/what-is-the-most-efficient-way-of-counting-the-number-of-1s-in-an-integer: Given a 32bit unsigned integer, we want to count the number of non-zero bits in its binary representation. What is the fastest way to do that ? We want to do this N~10^10 times. note: using a large look up table is usually not a good idea because of the architecture of current cpu's . it is much faster to calculate it locally than to use a huge array that needs looking at the external memory --------------------------------------------------------------------------------------------------------------------------------- ZarakiKenpachi: There are actually several options, I presume the native way is way too slow for this. You can go with lookup table for 8-bit value and do it in parallel for all four bytes from unsigned int value, then sum the result. This one could be also quite well-paralelizable (be it multi-core, or maybe even some SSE3/4 could help). You can also go with Brian Kernighan's solution: unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set } And the last possible way I found somewhere some time ago is (on 64-bit machines, as the modulo operation would be really fast there): unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f; c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Mulakat sorulari

1. Bir oda içinde 3 tane elektrik düğmesi var. Her bir düğme odanın dışındaki 3 ampülden birine bağlı. Odadan sadece bir kere dışarı çıkma şansınız varsa hangi düğmenin hangi lambaya bağlı olduğunu nasıl anlarsınız?

2. Elinizde 2 tane ip var. her iki ipin de bir ucundan diğer ucuna kadar tamamen yanması (bir taraftan başlayarak) tam bir saat sürüyor. İp üzerinde ateşin ilerleme hızı (yanma hızı) sabit değil, yani ipin farklı kısımları değişik hızda yanmakta. Ayrıca ipler birbirleriyle de eş olmak zorunda değil. Bu iki ipi ve bir çakmak kullanarak 45 dakika nasıl ölçülür?

3. 2 kadın ve 2 erkek şöyle bir el sıkışma gerçekleştirmek istiyor:
- her erkek her bir kadınla el sıkışacak
- Hemcinsler el sıkışmayacak
Aynı zamanda her bir kişide farklı bir tür hastalık olduğunu varsayıyoruz ve bu hastalık el teması ile geçmekte. eldivenler de bu hastalığı taşımakta. Örneğin bir eldivenin dışı a kişisinin çıplak eline değerse ve sonra da b kişisinin eline değerse hastalık a'dan b'ye geçmiş olur. Fakat eldivenin bir yüzünden diğer yüzüne hastalık geçmez.
İçi-dışı bir bir çift eldiven ile el sıkışma işlemi nasıl olmalıdır?

soru

Michigan State Men's Basketball (Spartans) team has 4 games left in their schedule. The probability of a loss -independent of who they are playing against- for Spartans is theta. On the other hand, if they lose a game, the probability of losing the next game becomes 0.6.theta^2.
If they lose two cnsecutive games, the probability of losing the third consecutive game is again theta. Given these characteristics of Spartans and the observation that Spartans loses only 2 of their final 4 matches, what is the most likely value for theta?

kernel bandwidths for imagenet dataset

dene - nxd matrix (very small subset of imagenet)

s=sum(dene,2);
ind=find(s>0);
dene=dene(ind,:);

aa=sum(dene.^2,2)*ones(1,size(dene,1));
bb=ones(size(dene,1),1)*sum(dene'.^2);
s2b=sqrt(aa+bb-2*dene*dene')./sqrt(aa+bb+2*dene*dene');

rbf=sqrt(aa+bb-2*dene*dene');
chi2 = vl_alldist(dene', dene', 'chi2') ;

1/mean(chi2(:)) = 0.1925
1/mean(rbf(:)) = 1.0693
1/mean(s2b(:)) = 1.8578

for BoW representation:
1/mean(chi2(:)) = 0.0011
1/mean(rbf(:)) = 0.013
1/mean(s2b(:)) = 1.25

MATLAB ile hızlı RBF kernel hesaplama

x=rand(1800,500);
y=rand(2000,500);

% MATLAB versiyonu
tic
K1=dist(x,y');
toc

% YGZ versiyonu
tic
a=sum(x.^2,2)*ones(1,size(y,1));
b=ones(size(x,1),1)*sum(y'.^2);
K2=sqrt(a+b-2*x*y');
toc

LIBSVM kullanımı

Olay şu: LIBSVM'in -t4 (precomputed kernel) seçeneği ile öğrenmek yaptık, fakat test için kullanacağımız kernel matrisi yok. LIBSVM'in bu iki kullanımı arasıdaki dönüşüm şöyle yapılır:

model= svmtrain(ytr, [(1:ntr)' Ktr], ['-t 4 -c ' num2str(100)]); % öğrenme
xtr2=xtr(model.SVs,:); % 'support set'
Mts2=dist(xts,xtr2'); % uzaklık matrisi
Kts2=exp(-mu*Mts2); % kernel matrisi
ssalphas=model.sv_coef; % SVM katsayıları
dec_values3=(ssalphas'*Kts2')'-model.rho; % sonuç vektörü

dosyadan 'string' okumak, bunlarla işlem yapmak

cat wid.txt |

while read CMD; do
str1='http://www.image-net.org/downloads/features/sbow/'
str2='.sbow.mat'
echo "$CMD"
str3="$str1$CMD$str2"
echo "$str3"
wget "$str3"
done

Basit bir şey ama hafızamın ne kadar kötü olduğunu düşünürsek yazmakta fayda var. bu arada '=' işaretinden sonra boşluk bırakmamak önemli.

çevrimiçi öğrenme-1:perceptron

Benim kullandığım algoritma şöyle:

for t=1...T
receive (x_t,y_t)
make a prediction f=w^T*x_t
if y_t*f update w: w = w + s_t*y_t*x_t (s_t:step size)
end
end



Bu algoritmaya 'regularizer' (düzenleyici?) katmak istersek şöyle yapmamız gerekir:

for t=1...T
receive (x_t,y_t)
make a prediction f=w^T*x_t
if y_t*f update w: w = (1-s_t)w + s_t*y_t*x_t (s_t:step size)
end
end

Neden bu düzenleyici etkisine ihtiyaç duyuyoruz. Tahminimce şöyle: başarım oranı düşük sınıflarda algoritma çok hata yapar. Çok hata demek w'ya çok terim eklemek demek (güncelleme adımında). Olay nihayet w'nun tahmininde hata yapılan örneklerin ortalamasına yakınsaması, hatta 'norm'nun büyümesi (pozitif ve negatif örnek sayıları arasında fark var bizim deneylerde) anlamına gelir. Düzenleyici etkisi ise w'nun normunu belli bir büyüklükte tutar.

çevrimiçi öğrenme (online learning)

Bir sürü test yapmaya başladım yine. Her zamanki gibi tüm yaptıklarımı 2 hafta içinde unutmak istemediğimden dolayı kısa bir özet geçmekte fayda var. Hem yaptıklarımı Türkçe özetlemek olayı gerçekten kavrayıp kavrayamadığımı anlamamı da sağlar.

Nedir bu çevrimiçi öğrenme denilen şey (bilgisayar bilimlerinde)? Tüm örnekler üzerinde sadece bir defa geçerek model oluşturmaya çalışmak diye kabaca özetlemiş olayım. sonra da olaya dalalım:

Calteh-101'le başladım ama nedense sonuçlarda bir gariplik vardı. bunda özniteliklerin çok iyi olmaması da bir etken olabilir. Dr Jin MAP tabanlı değerlendirmeden de şüphelendi. AUC-ROC deneyeceğim. Ama önce deneyler için bildiğimiz, güvendiğimiz VOC2007 verisini seçerek başlayalım. elimizde 5011 tane eğitim örneği/resmi (training sample) var: x_1,...,x_5011. Sırasıyla şu metodları deneyeceğiz:

1. toplu (batch işleme)
a. lineer SVM
b. kernel SVM (chi2 uzeklığını kullanan RBF)
2. lineer çevrimiçi
a. perceptron
b. perceptron+regularizer
3. kernel (çekirdek fonksiyon?) tabanlı çevrimiçi öğrenme
a. NORMA

Mevcut sorun (Caltech101 deneylerinin sonuçlarına göre) ne peki? Sorun şu: toplu işlemenin iyi sonuç verdiği (apr>50) sınıflarda çevrimiçi idare eder sonuç veriyor (%10 daha düşük). Ama toplu işlemenin iyi sonuç vermediği sınıflarda ise çevrimiçi sonuçları berbat, ki aslında iki yöntem arasındaki farkın bu tür sınıflarda daha az olmasını bekleriz normalde.