Job search adventures

Introduction

For a couple of weeks I had an honor to talk to various people in search for a possible position as a software engineer. Personally, I have a quite wide area of interests, however in job search market, this feature of the software engineer is not a good entry in your curriculum vitae .

People

I would like to start with people, who interviewed me. These were various kind of people and professions. From job search agencies (I like to call them people filtering institutions) to the directors of the companies. Obviously, the big companies hire the job search agencies to filter people out, and directors interview people only in small companies. There was also human resources and sometimes project managers in the interviews.

The people filtering agencies are the nicest people in the whole planet. They don’t understand any terms you are saying, but somehow You feel like they listen and You enjoy talking to them. Maybe, it’s because they were all woman and I have had no girlfriend in months, I don’t know. They did not ask any technical related stuff, they were just interest on how You do your work and what you like to do on your free time.

Going directly to the companies, the wide spectrum of interviewing people is displaced. From the managers of human resources to project managers. Wide area of people gives the problem of what to say. Managers are only interested in how much quality your work has while software engineers are interested with which platforms You have worked. In this kind of situation, one can even say some jokes or laugh from some stupid mistakes.

Tests of skills

One of the most obscure thing during the interviews is the technological tests. These things suppose to help company understand on how good Your are in terms of theoretical and practical situations. These things are always unpleasant. For example, writing manual SQL queries is always a pain and usually this kind of stuff is written by testing it. No PC around, just a peace of paper — a lot of stress goes in Your brain and big possibility, that it will go wrong.

I personally more into practical tasks. Some of the technical directors gives quite interesting tasks. For example, the code, which is encoded in basic hex and the task is to perform the profiling of the code. And the question of interest was why the program runs so slowly. Of course, the answer to this question after debugging was pretty obvious — sleep function makes the code slow, but still it was something new. Other tasks was basically to write some simple programs — subscription module or guest-book like application.

The only interesting test was given by a big-corporate-international place. They just need to know how fast You are able to learn new stuff. Of course, in current world, everything changes day by day (except PHP) and so they literally asked some technical stuff only in the second round, then the head of programming asked me about my interests and previous experiences.

Unusual questions

Unusual questions deserves separate topic. Then You go to the interview, You are prepared with some basic answers to the standard and routine questions, like “How You imagine Yourself in 5 years?” or “The most interesting project so far?”. Of course, You get to answer them as a typing machine, nothing can go wrong. But there was couple of unusual ones:

  • What other places You have applied? (should not this be a personal thing?)
  • Are You comfortable to get up at 4 o’clock in the morning? (I’m an engineer, not a hippie)
  • How You react, then the customer changes his mind on the last day of project shipment. (I’m an engineer, not a hippie)

With more like google-type of questions, I would feel more comfortable. These questions does not show any thinking signs from the participant, just very straight-forward and plain.

Conclusions

All in all, it was fun experience. I have never talked to so many people in same area of interest. Some was good, some was bad. The main advice from my point of view — do not rush things. Stay calm and logic through all the job search procedure. Scale everything the interviewer does and doesn’t say. Set up every position in the field of possibilities and only then make a move.

Happy job search adventure in Vilnius! (or Kaunas!)

Hacking vilnius ticket web service

Introduction

Lately I was involved in some sort of web scraping thing, and it was very exciting. One can do so many things automatically with a simple, yet powerful script. In particular what python with lxml can offer.

Challenge

So, in the city of my living I came across the service, which provides You with the current information of Your public transportation card. It’s very-very not user friendly and if I catch myself on the run, I need to go to their site and log in and then I only then I can see the critical information I need — how much money is there in my public transportation card. No app is provided on any platform. So the only possibility is to do some hacking of the system and write an app for myself.

Scrapper

First thing to do, is to analyse the platform. What was really amazing is that there was no form elements. Everything was done, using the JavaScript. This makes life even more easier

2013-03-17-013342_3840x1080_scrot

This only means, that the data from the inputs is send directly to the server with XHR in background and then everything goes straight where it belongs to be. So the next step — what does it send?

2013-03-17-013350_3840x1080_scrot

All the form elements, plus some empty variables (?) and something randomly generated, looking like key-ish thing, which looks like no-changeable thing, because after some testing, I was still able to make a POST request to the server, and he was perfectly fine with this random thing. This is basically it, now the only thing left is the code.

The python library lies @github.com. Fell free to fork it and make something from it. And here’s the screenshot of the text-content of the returned html.

2013-03-17-015132_3840x1080_scrot

Conclusion

After working with scrappers, I’ve realized how insecure the web is. The only thing, which can make some changes in the field is the captcha-ish things included in the forms.

The Problem

Introduction

Here is the thing. Well, it is not the thing exactly, it is more like a frustration or desperate need for deformation. The work in Artificial Intelligence field is less orientated as I expected, nor it is organized. Of course, there are sets of tools to work with, witch works, after some tune-ups, but this time it is not about tools. It is more about the essential of this field, the root, which drives it forwards – the brain.

Problem

We, human living beings, are very subjective on every subject what so ever. We do go to school in order to learn how to write, calculate. There are not so many intelligence, as I define it, in those ages. It is more like an exploring process, which started immediately after memory system has been launched in the brain and finishes then we die. It is more or less continues process.

So, here is the thing: how to define, on what intelligence basis, do we develop the artificial intelligence system? Example: an older person has a quite bad memory, so the brain does not recognize some of the people faces. So does current face-recognition solutions, due to some unique specifications. Personally, sometimes I do mess up with recognising some of my fellow students, but let’s say, machine does a better job. What conclusions does it make? While, after some renewing-faces job, I do perform better job, than the machine, does it makes machine less accurate?

These questions are the essence of the brain working problem – it is not a state machine. It is a dynamic machine. You can not stop it, as a car engine, inspect it, make changes and run again. If You kill the brain, it would not rise from the dead again. This is the problem. The only possible solutions to this is to make changes, while brain is still working. This causes some ethic problems, sadly. Another solution – making models and testing them. Looking how likely it is to work as brain does. More like physics, huh? Just physics people have a good platform to test their ideas – the mighty universe. While we do have only 5 kg of neural matter, which is not possible to model on high level scale.

Conclusion

Brain, the dynamic system of connections, which is not possible to model, is so interesting, so frustrating and depressing on the same time. What gives us energy to explore the brain, also does make the problems to do so.

A simple example of feedforward neural network and image recognition

Introduction

The new field, in which I’ve stepped a little bit is image processing or image recognition. This field has some similarities with the previous field (signal processing) and so it was not so difficult to try something new.

Today, we’re going to review a simple application, which I’ve written for my lab as a bonus for the final mark. The objection of the application is to recognize the areas in the picture, which has the most trees (the greenest ones). All the code can be downloaded here, especially, if you’re good in analyzing codes, the further description of this method is not necessarily to read in order to understand how everything works.

Method

Firstly, we take a picture for training. Originally, images are 1000×1000 pixel size, but because I’m poor and my computer does not have lots of power and memory capacity, the image size is scaled by 0.40. The image size after the scale is 400×400 pixels.

Sample image

Next step is to use a sliding window (not sliding window protocol) to analyse the image. Basically, it is the same sliding window method, as for one dimensional signal, but this time, the samples are taken in two dimensions. The matlab implementation is extremely easy:

for i=2:size(I, 1)-1
 clear j;
 for j=2:size(I, 2)-1
   Id(k,:) = I(j-1:j+1,i-1:i+1,:);
   k = k + 1;
 end
end

The code illustrates the use of 3×3 sliding window. The variable I is the image itself and because it is an RGB image, the selected window has three dimensions. The most important information from the image for the forest discovery problem is the green color, so the identification can be done by this feature. What we can do is not to save all RGB information of the window, but just green color information:

for i=2:size(I, 1)-1
  clear j;
  for j=2:size(I, 2)-1
    Id(k) = mean(mean(I(j-1:j+1,i-1:i+1,2)))/9;
    k = k + 1;
  end
end

Using this code, we can work only with one dimensional feature data, not 27 dimensional data (as would be, using all RGB information).

Next problem is the uncertainty then the window sees the forest and then it is something else. Doing this by hand would be some sort of suicidal work, which could take ages to complete.. But there is a solution! It’s called the k-means clustering algorithm. What KM does, it divides the data by means. Logically, the green color mean of the forest area would be bigger.

It matlab it is realized quite simply:

IDX = kmeans(Id,2);

And this is it. The function returns the labels of the data of KM clusters.

The KM algorithm is sometimes a little bit random, for example – first time, doing KM it can label most green zones as 1, and not so green zones as 2. Do it again and the labels would be turned around. How well KM performed the clustering solution can be tested only after classification, then the `forest` would be recognized. If you see, that the algorithm does not work as good as it suppose to – you need to run it again, to give KM algorithm one more chance (okay, maybe not only one chance, but it is still better, than manually labeling data).

The next step, after KM is to separate original data, which we will need to train our Artificial Neural Network (FeedForward Neural Network (FFNN)), to do classification.

P1 = Id(IDX==1,:);
P2 = Id(IDX==2,:);
number = min(size(P1), size(P2));
number = number(1);

Here, P1 has one cluster of data, and P2 has the other. We’re searching with data cluster has less data, because the training algorithm require, that number of data samples in training set of both data clusters would be the same.

Next step is to train our super-awesome (and slow) FFNN with 10 hidden neurons (the number of neurons was chosen just randomly):

net = feedforwardnet(10);
P = [ P1(1:number,:); P2(1:number,:) ]';
T = [ zeros(1,number) ones(1,number) ];
net = train(net, P, T);

This can take some time.. The final algorithm does training using 4 different pictures of pictures. The classification tests was done using other 15 pictures. Here is some examples of classification done by this algorithm:

Acceptable classification result

Not acceptable classification result

On the left side of illustrations, there is an original image, in the middle there is classification result, and on the right side the mapped data. As we can see, the classification sometimes is done quite good, but sometimes is fails completely.

This algorithm requires more work (and more powerful computer to run on), but as a starting point it is quite good. The possible features to extract may be also mean of yellow color (to classify out roads).

Conclusion

In this article, a simple image processing example is shown and discussed. As a feature to recognize the forest and not forest areas, the mean of green color was used. No dimensional reduction algorithm was used, because only one dimension is used. The data labeling was done using k-means clustering algorithm, which showed quite good results, but it is not recommended to use it for some very important tasks. This time it was more for fun, than for production. The classification was done, using FeedForward Neural Network (FFNN).

The complete code can be downloaded here. Just extract and run `lab_10`. After some time, you must see the same images, as shown in this short example.

Changing the language

For a particular reason, my whole blog was entirely in Lithuanian language.

Starting from today, every single post will be in English. The possible reasons:

  1. English is a language of internets;
  2. English provides the possibility to extend the audience;
  3. (This is a good opportunity to get used writing in English, because my English writing skills are quite terrible);

Pamąstymai apie slankiojančio lango signalų analizavimo metodą

Geriausios mintys kyla tuomet, kai darai ką nors visiškai pašalinio – šiuo atveju besėdint prie visiškai intelektro nereikalaujančio kompiuterinio žaidimo, kilo įdomi mintis kaip galima praplėsti slankiojančiu langu pagrįsta signalų analizavimo sistemą.

Visa idėja remiasi kintamo ilgio slankiojančiu langu (tiksliau jo ilgis kinta tik signalo analizavimo pradžioje), o toliau lieka pastovus. Taip galima praplėsti analizuojamo signalo ilgį, išsaugant mažą reakcijos laiką. Idėja dar reikalauja darbo, tačiau pačią pradžią jau galima publikuoti.

Tikiu, kad jau kažkas iki manęs apturėjo ir aprašė šitą idėja, tačiau vistiek ją aprašiau, kad nepamest.

Kadangi wordpress sistema yra labai, labai nedraugiška grafikams ir lygčių rašymui, nusprendžiau viską aprašyti LaTeX pagalba ir tiesiog patalpinti savo rašliavų interneto kampelyje.

Popierių galite atsisiųsti iš čia.

Įžanga į Paslėptą Markovo modelį (skaidrės)

Šį kart trumpa prezentacija apie Paslėptą Markovo modelį, su trupučiu matematikos.

Skaidrėse pristatomi mašininio apmokymo tipai, parodyta pavyzdinė savybių erdvė, aptariamas Markovo procesas, Markovo grandinė, apibūdinti Paslėpto Markovo modelio parametrai, apžvelgiamas Viterbi kelio radimo algoritmas.

Viskas paruošta nėra super-idealiai, dėl didelio akademinio užimtumo. Skaidrės yra daugiau kaip špargalkė kalbai, negu kaip mokomoji priemonė. Mokomajai priemonei reikia knygas rašyti. Skaidres galite peržiūrėti slideshare, arba atsisiųsti pdf formatu.

Vektoriaus palaikymo mašina

Kažkodėl nusprendžiau, kad seniai berašiau įrašų, kurių niekas nesuprato. Šiandien su plačia tauta norėčiau pasidalinti maža teorijos ir praktikos samprata apie Support Vector Machine (SVM) (lietuviškai galima versti įvairiai, tačiau, kadangi niekur jokio vertimo nerandu, tai sugalvojau savo variantą – Vektoriaus palaikymo mašina); Labiausiai man patiko Christopher J.C. Burgers parašytas įvadas “A Tutorial on Support Vector Machines for Pattern Recognition“. Nors, aišku, galite bandyti skaityti originalų Vapnik straipsnį “An overview of statistical learning theory“. Ten daugiau matematikos, bet ir aišku mažiau.

Įžanga

SVM sprendžia klasifikavimo problemas. Turim tam tikrą savybių erdvę ir mums reikia toje savybių erdvėje gražiai `padalinti` duomenis. SVM genialumas yra tai, kad jis naudoja pačius `duomenis` duomenų praskyrimo erdvei rasti. Daug žada, ne?

Gražioji pusė

Pavyzdį galima paimti iš wiki.

Grafike X_1 ir X_2 suformuoja dvi dimensijas, kur SVM ieško linijinio jų tarpusavio prasiskyrimo. Ryškiau apibrėžti tuščiaviduriai taškai ir pilkai apvesti juodi taškai yra ne kas kitas kaip palaikymo vektoriai. Tai jie pagrindinė priežastis kodėl įmanomas toks duomenų prasiskyrimas. Labai nesigilinant į SVM matematiką (ribinės klaidos radimas ir kt.), tai mes turime dvi linijines lygtis. Viskas ko mums reikia, tai rasti dvi linijinės funkcijas. Mums šiuo klausimu dar padeda ir ta sąlyga, kad nagrinėjamos lygtis turi būti viena kitai lygiagrečios. Nėra jokio Gauso (NaiveBayes), nėra jokios gausios ir gan sunkios matematikos PMM (HMM) atveju. Juk nuostabu, ne? Iš teigiamų savybių galima paminėti ir išgirtą jo naudojimą izoliuotų raidžių atpažinime. Yra pateikiamas net visas projektas su kodu (.NET) (dėl .NET jo net nežiūrėjau).

Negražioji pusė

Tačiau SVM turi ir blogų savybių. Kas nutiks, jeigu po apmokymo, testavimo fazėje savybių erdvėje koks nors taškas pateks tarp dviejų linijų? SVM neturi jokio Gauso (bent jau originalas), todėl atsakymo paprasčiausiai nebus. Kokia loginė funkcija tai gali paaiškinti? Kur `uncertainty` principas? Sekantis SVM trūkumas – tai jo įvairumas. Jeigu prisiminti mokyklinę matematiką, tai visos matematinės plokštumos ir figūros kaip tik ir prasidėdavo tašku ir tiese. Taip pat ir SVM atveju – galime prigalvoti begalės jo variantu ir ieškoti tinkamo iki kol pati saulė sudegs. Žinoma, yra keli populiarūs, oficialiai naudojami sprendimai. Kita neigiama savybė – SVM sugebėjimas vienu laiko momentu klasifikuoti tik du duomenų debesis savybių danguje. Yra, tiesa, neblogas popierius šia tema. Siūlau pasiskaityti, kada nors. Iš praktikos dar galima paminėti, kad SVM apmokymas yra labai lėtas ir nervų reikalaujantis procesas. Stebuklus su juo galima daryti ir neturint baigtinį dimensijų skaičių, tačiau `gyvai` treniruoti klasifikatoriaus tiesiog neįmanoma.

Išvados

Taip ir nesupratau kodėl SVM tapo toks populiarus. Yra geresnių ir greitesnių klasifikavimo metodų (kad ir stebuklingas PMM (HMM), nors ir reikia turėti baigtinį dimensijų skaičių). Reiks gal kada parašyti įžangą į SVM lietuvių kalba. Tiek, trumpai.

Kas iš tikrųjų yra Paslėptas Markovo modelis

Įžanga

Truputi pamankštinęs rankas prie Paslėpto Markovo modelio, galiu pasidalinti ne teoriniais samprotavimas apie nagrinėjamą modelį, o apie konkretų įrankį, kuris veikia ir veikia pakankamai gerai.

Paslėptas Markovo Modelis ir kiti klasifikatoriai

Jeigu padaryti prielaidą, kad Paslėptas Markovo Modelis (PMM) yra klasifikatorius, tuomet palyginus su kitais klasifikatoriais – mes turime labai galingą įrankį.

Pradėkime nuo NaiveBayes klasifikatoriaus, kuris yra labai paprastas – n dimensijų Gauso pasiskirstymas. Kai gauname tašką erdvėje – tiesiog pažiūrime kiekvieno cluster tikimybes ir išrenkam tą cluster, kuris turi didžiausią tikimybę. Paprasta, greita ir pigu. Tačiau kas nutinka, kai du Gauso pasiskirstymai yra arti vienas kito, o taškai iš šaltinio gaunami tik per delta skirtumą tarp dviejų pasiskirstymų – klasifikatorius mėtysis tarp vieno ir kito cluster. Taip mes gauname labai mažą accuracy ir presition.

Support Vector Machine yra kiek sudėtingesnis variantas. SVM’as ieško papildomų dimensijų duomenims atskirti. Tai ypač pagelbėja, kai duomenis linijiniu būdu atskirti tiesiog nėra įmanoma. Geras pavyzdys – naudojant polynomial kernel trick. Pagrindinis SVM darbo arklys yra radial basis function. Tai tas pats Gausas. Mano praktikos metu, SVM’as tik truputi geriau dirbo, negu NaiveBayes klasifikatorius, o kaikuriais atvėjais – net blogiau. Dirbtinio intelekto sistemose, visgi, daug kas priklauso nuo application. Reikia išnagrinėti kokias savybes signalas turi savyje, ką duoda dimensijų mažinimas.

PMM turi vieną labai didelį pranašumą, palyginus su kitais nagrinėtais klasifikatoriais – jis turi savyje laiko informaciją. Matematiškai šnekant, tai kai mes turime du duomenų cluster, kurių variacijos kertasi – mes virš dviejų variacijų galime aprašyti dar vieną variacija, kuri aprašo įvykių tikimybes, kurias atspindi clusters. Taip galima kontroliuoti sąlygas, kurios aprašo įvykio pasikeitimą.

Jeigu nustatyti, kad perėjimo tikimybė tarp vieno ir kito įvykio yra labai maža, tai nors, jeigu ir naujas duomenų taškas bus ant kito Gauso pasiskirstymo – klasifikatorius vistiek neskubės persijungti prie kito įvykio.

Paprastas klasifikatorius

Pagerintas (PMM) klasifikatorius

Išvados

Paslėptas Markovo Modelis yra fantastiškas matematinis įrankis. Skirtingai nuo kitų klasifikatorių, jame lengvai gali būti saugoma bet kokia euristinė informacija apie nagrinėjamus duomenų clusters.

Kas yra `dimensijų mažinimas`

Nejaugi jų daugiau, negu trys ?

Įžanga

Niekad negalvojau, kad galėsiu sau užduoti panašios krypties klausimo, tačiau, tai vienas iš svarbiausių klausimų tiek Statistikoje, tiek Signalų apdorojime ir jį būtina spręsti.

Dimensijų mažinimas

Natūralūs klausimai perskaičius skyrelio antraštę – kas aplamai yra dimensijos ir kodėl jų būna daug? Kam aplamai reikalingas dimensijų mažinimas?

Kas gi yra dimensijos? Pirmiausiai Įsivaizduokite erdvę. Ir pradėkime nuo paprasčiausio fizikinio kūno – taško. Jį aprašyti nereikia visiškai jokių dimensijų. Sakoma, kad jis egzistuoja nulinėje dimensijoje. Vis dar toje pačioje erdvėje įdėkime naują tašką ir sujunkime tą tašką su ankstesniu. Ką gi mes turime – linija. Linija turi priklausomybę nuo ilgio, vadinasi liniją mes galime aprašyti viena dimensija. Dabar ištempkime tą liniją statmenai jos ilgiui. Gausime plokštumą, visų dviejų dimensijų plokštumą. Dabar ta plokštumą mes galime aprašyti ilgiu ir pločiu. Ištempkime mūsų plokštumą statmenai jos pagrindui. Gausime trijų dimensijų kūną, kurį galime aprašyti ilgiu, pločiu ir net aukščiu.

Iš tokio klasikinio pavyzdžio galime prieiti prie išvados, kad dimensijų skaičius – tai parametrų skaičius, kuriuo mes galime aprašyti mus dominančią erdvę. Jeigu mes norime kuo tiksliau ir kuo nuodugniau aprašyti erdvę – mes pasitelkiam vis daugiau parametrų jai aprašyti. Iš čia ir kyla besaikis dimensijų skaičius.

Kodėl mums reikalingas dimensijų mažinimas? Atsakymas yra paprastas – pabandykite įsivaizduoti 120 dimensijų erdvę. Asmeniškai pats galiu įsivaizduoti tik keturias dimensijas. Iš turimo ribotumo kyla būtinybė sumažinti dimensijų skaičių išsaugant erdvės savybes.

Logiškas ir kvailas atsakymas galėtų būti – “Numetam nereikalingas dimensijas ir paliekam tik pirmas tris”. Deja, tačiau taip mes galime pamatyti tik priklausomumą tarp pirmų trijų parametrų. Dimensijų mažinimas realiai sukuria naujus sistemos parametrus, pasiremiant ant senųjų ir išspaudžia mūsų duomenis į naują `savybių erdvę`.

Trumpai aptarkime dvi paprasčiausias ir dažniausiai naudojamas technikas.

Principinė komponentų analizė

PCA ( Principal Component Analysis, “Principinė komponentų analizė” ) tai yra dimensijų mažinimo technika, paremta kovariacijos matrica. PCA sukinėja kovariacijos matricą ir ieško kryptį, kurioje esama didžiausia duomenų variacija, t.y. kuria kryptimi duomenų yra daugiausiai. Po to, kai tokia kryptis buvo rasta, PCA paima statmenį rastai krypčiai ir ieško kuria kryptimi duomenų variacija didžiausia. Procesas kartojasi priklausomai nuo dimensijų skaičiaus.

Jeigu duomenys yra trimačiai – tuomet tokios kryptis bus trys, jeigu duomenys turi 120 dimensijų – krypčių bus tiek pat – 120. Įdomiausia tai, kad nors PCA ir paliko tiek pat dimensijų – realiai visi duomenys yra projektuojami tik pirmose dimensijose, t.y. didžiausią duomenų priklausomybę erdvėje galime pamatyti pirmose dimensijose.

Analizė linijiniu diskriminantu

LDA ( Linear Discriminant Analysis, “Analizė linijinių diskriminantu” ) tai yra dar viena dažai naudojama dimensijų mažinimo technika, paremta duomenų matricos vidurkiu skaičiavimu. LDA paima duomenų sritis, paskaičiuoja jų didžiausio vidurkio tašką ir sukalioja duomenis iki tol, kol vidurkiai nebus atskirti per maksimalų galima atstumą.

Pavyzdys

Užteks kalbų, metas ir pažiūrėti į kažką.

Tarkime mes turime du kiaušinius trijose dimensijose, kurie yra pasiskirstę pagal Gausą.

Po PCA atlikimo, PCA mums gražina kryptis, kuriomis yra didžiausia variacija.

Dabar mes jau turime kryptis, todėl galime suprojektuoti mūsų duomenis gautų krypčių atžvilgiu. Taigi, dviejuose dimensijose mūsų duomenys atrodo taip.

O taip mūsų duomenys atrodys vienoje dimensijoje.

Išvados

Dimensijų mažinimo klausimas liks aktualus visuomet. Egzistuoja labai daug būdų jų mažinimui. Paprastumo dėlei šiame įraše paminėjau tik du paprasčiausius linijinius būdus, tačiau egzistuoja ir gan sėkmingai dirba ir ne-linijiniai dimensijų mažinimo būdai, reikalaujantys žymiai daugiau skaičiavimo resursų.

Dėkojimai HSG-IMIT ir VGTU URD.