Similarity in application features - Cosine Similarity

Lets say you are planning to write a rating system for music songs.

and you are interested in the following queries:
- average rating of a given song
- average rating a user gives to a song
- which songs are most similar
- which users rate similar songs
- which users have similar tastes

here are we gave 2 dimensions user and song rating. We can use cosine similarity to answer the above mentioned queries. Lets do this in a step by step manner

Step 1
Create a 2 dimensional matrix of song_rating vs user

	A	B	C	Avg
song1	3	2	1	2
song2	4	2	3	3
song3	2	4	5	11/3
average	3	8/3	3	26/3

Here the column represent the ratings given by users A, B, C
The last column represents the avg rating of a given song.
The rows represents a song and the ratings given by different users for that song.

Step 2
Normalize the values in the matrix so that they lie between 0 and 1.

divide each column value by square root of the sum of the squares of all the columns in a given row. e.g to normalize column with value 3 divide 3 by
sqrt(3^2 + 2^2 + 1^2)

	A	B	C
song1	3	2	1
song2	4	2	3
song3	2	4	5

Step 3
Normalize the values in the matrix so that they lie between 0 and 1.

divide each column value by square root of the sum of the squares of all the columns in a given row. e.g to normalize column with value 3 divide 3 by
sqrt(3^2 + 2^2 + 1^2)

	A	B	C
song1	3	2	1
song2	4	2	3
song3	2	4	5

Step 4
obtain a new table after applying normalization rule

	A	B	C
song1	.8018	.5345	.2673
song2	.7428	.3714	.557
song3	.2981	.5963	.7454

Now each row with every other row to obtain a similarity matrix.
The multiplication should be a dot product of the 2 rows

for example the song1 and song2 dot product yields in
.8018*.7428 + .5345*.3714 + .2673*.557 = .943

Step 5
Use the dot product rule to obtain the similarity rule

	Song1	Song2	Song3
song1	1	.943	.757
song2	.943	1	.858
song3	.757	.858	1

From this matrix its easy to figure out that song1 is more likely to be similar to song2 than song3

Step 6
Finding similar users is similar to finding similar songs, just align the
users as rows of the initial matrix and song rating as the columns of the initialization matrix.

Then apply Step 2 - Step 5 in order and you can obtain the similarity matrix for users also

Adding feedback loop to your applications

These days everyone is talking about smart applications.

One very simple feature that smart applications have is measuring user interactions.
Learning from user interactions and acting in a more personalized manner towards the user.

User interaction can mean different things for different applications. Here i am going to talk about one popular user interaction metric.

"Time spent by a user on a given feature"

Assuming you have some way of measuring the time spent by a user on a given feature. You can calculate the average time spent by a user and compare it with the time spent by other realistic users by using some statistics.

Assuming you have a list of users and their corresponding time's spent on the feature.
You can calculate the mean time for the list.

Lets call this mean_time.

You can also calculate the standard deviation for the list.

Lets call this time_range_delta

you actual time_range interval is then (mean_time - (time_range_delta * range_factor), mean_time + (time_range_delta * range_factor))

where range factor is the amount spurious information you are will to tolerate a range of [1-3] for this factor is generally considered good.

once you have this range interval, you can ignore all times that fall outside this range interval.

this will give a new list, from which you can calculate the mean and standard deviation again.

By following this process iteratively you can get the actual list of genuine users and their corresponding times.

Calculating the mean of this list will give the average time spent by the user.

You can then classify any user by using this average time.

Little Sugar: Creating a device node

To create a device node use mknod

mknod /dev/mem c 1 1

here the device name is /dev/mem

c represents character device this can be block device also

the first 1 represents the major number
the second 1 represents the minor number

Little Sugar: FreeBSD total RAM

to find out the total RAM installed on your FreeBSD box use something like this

sysctl hw.physmem

Little Sugar: insmod

Linux kernel extensions have a .ko extension are inserted directly into the kernel
using insmod command.

The kernel modules are removed using rmmod.

Kernel modules are generally placed at /lib/modules.

To update kernel dependencies run depmod

Finding Document Similarity

If you need to find how similar a document is we can use vector algebra to our advantage. If we have 2 document d1 and d2 then

Let D1 be a vector of the word-frequency of the document d1
Let D2 be a vector of the word-frequency of the document d2

then the deviation of the 2 documents can be calculated by

using the fact that

cos(theta) = (D1 * D2)/(N(D1) * N(D2))

where N(D) is the normalized vector represented by

N(D) = sqrt(D * D)

OpenGL: Diffuse, Specular, Ambient, Emissive lights

In the OpenGL world there are different types of light types

Diffuse
--------
These type come from one direction bu are scattered equally in all directions.

Specular
--------
This type of light comes in one directions and is also bounced off in one direction

Ambient
--------
This type of light source comes from different light sources and is also scattered in different directions

Emissive
---------
This represents light originating from the object

So in general A light source has two types of properties associated with it
LR,LG,LB => the RGB components that make up the light and
MR,MG,MB => the RGB components that are reflected away
Hence the net effect of the RGB is given by a vector

(LR.MR, LG.MG, LB.MB)

if light is coming from two or more sources the light is added and next effect is
of the form

(R1 + R2, G1 + G2, B1 + B2)

Opengl : Hidden Surface Removal and LIghting

Hidden surface removal is a common technique in the graphics world. The technique says
we should draw only parts of objects that are visible to the user.

What support does OpenGL have for hidden surface removal.OpenGL supports hidden surface removal through a combination of DEPTH BUFFER and COLOR BUFFER.

Depth Buffer and Color Buffer
------------------------------
Our screen is flat basically we see a flat 2D rectangular screen made up of pixels. Associated with these pixels we have a corresponding value in the Depth Buffer and
Color Buffer. So what pixel appears forward or backward depends on its value in the depth buffer. The color value it shows depends on its value in the color buffer.

to enable the depth buffer we need use something like the following:

glClear(GL_COLOR_BUFFER_BIT GL_DEPTH_BUFFER_BIT);

Material And Ambient Light
---------------------------
OpenGL understands RGB. A material quality decides the amount of RGB that is reflected or absorbed. An area can be lit by many light sources.Say in a room the bulb can the primary source of light.But there might be light reflected from walls which can be called secondory sources, the light contributed by such sources is called ambient light.

ps options

If you invoke the ps command like this

ps -C -o etime,pid,pri,cmd

this will show processes that match the command name and show output using the
fields followed after -o i.e

etime - how long the process is running
pid - the pid of the process
pri - priority of the process
cmd - the full command line of the command

Looking back at mergesort

For mergesort the recurrence relation is

T(N) = 1 if N == 1
T(N) = cn + 2T(N/2) if N != 1

so if we draw the recursion tree for such a recurrence relation we get
Height of tree = lg N
Number of leaves = N
--------------
Leaves at level 0 -> 1
Leaves at level 1 -> 2
Leaves at level 2 -> 4
Leaves at level 3 -> 8
...
Leaves at level lg N -> N

Total Work Done
----------------
Work done at level 0 -> cn
Work done at level 1 -> cn
Work done at level 2 -> cn
....
Work done at level lg N -> cn

So total work done => cn * lg N => O(n lg n)

Similarity between objects

Lets say we need to find the similarity between people based on how they rank different items. Based on the that collected data we need to recommend some new
items to the users.People who are similar to each other have a higher likelihood of
liking things that we recommend them.

Now lets consider a Set of Users.A Set of Items and a set of Rankings which users give to these Items.

Given this information how can we find the similarity between 2 Users.

Approach 1)
------------
Take user A and user B
Calculate union of items chosen by user A & B , call it A_UNION_B
Calculate the intersection of the items chosen between A & b, call it A_INT_B
then the value A_INT_B/A_UNION_B represents the similarity of the 2 users A and B

Approach 2)
------------
For every item that is common between A & B we can calculate the Euclidean distance between the rankings of the 2 items.
D = RA (ranking A gave to an item) - RB (ranking B gave to an item)
Sum = Sum + D^2

The once we have the sum we can call it Similarity Sum and use a formula
like

Similarity = 1/(1 + Sum)

The 1 is added to prevent the 1/0 off case, where our magic factor factor is 1
we can choose an arbitrary magic factor say N

Then Similarity = N/(N + Sum)

Approach 3)
-----------
Use the Sum that we got in Approach 2 above
Similarity = Sum / N where N is the number of items common between A and B that have the same rating
Similarity = Sqrt(Similarity)
then to make Similarity fall between the range 0 and 1

Similarity = 1 - tanh(Similarity)

Approach 4)
-----------
Use the Similarity that we calculated in Approach 3
NN = Number of items common between A and B
Similarity = Similarity * (N / NN)

Little Sugar: Writing an oscillator function

Say you need to transform values v1, v2 in such a way that they lie between lowerlimit L and upper limit U

then u can use an oscillator function

new value = U - (L + (U * (1 / (1 + value))))

this new value will be between L and U, if u omit L then new value
would be between 0 - U

Little Sugar: Useful commands while programming on Unix Systems

Here are a list of commands that re use file while programming on unix systems

pid = process id

ps aux | grep process_name
- to search for a given process name , generally use this to fetch pid of process

lsof -p pid
- to get all the files or file descriptors being used by the process having pid

lsof | grep file_name
- to get the list processes using a given file

sockstat | grep process_name
- to see the socket connections between a host and desinations

strace -p pid
- to see what the process is doing in general

nc hostname port
- to see data flowing from the hostname at the given portu

Little Sugar: Things to remember while creating a daemon

While writing a daemon on unix systems. The daemon should not be attached to any
terminals. So make sure the following things hold valid.

chdir '/'

umask 0

Map STDIN to /dev/null
Map STDOUT to your logging system
MAP STRERR to STDOUT

setsid # Make the daemon a session leader

use find magic to create etags

To create a TAGS file so that you can work with emacs / vim use the following command

find . -ipath '*.p*' -print | etags -

the above command for example will create etags for all the pl , pm files in the current directory

Little Sugar:Decreasing capacity in C++

When you use vector,string class in C++, the problem that happens is that the capacity just increases and does not decrease, causing the data structure to hog lot of memory.
For example, say in the vector 10 elements were added , then to the same vector 1000000 elements were added. Then 900000 were deleted. This will not cause the capacity to decrease. This might result in the vector still holding on to a lot of memory.

One way to fix this is the sap trick.

vector < int > elements; // the original vector

vector < int > (elements.begin(), elements.end() ).swap(elements)

vector::assign

"assign" is a method in STL for the vector class. When ever you need to erase the contents of the vector and replace it with totally new contents use the assign member function .You should use the operator= then all elements of the right hand side container would be copied to the container on the left hand side.

e.g

v1.assign(v2.begin() + v2.size()/2 , v2.end())

C++ : std::swap and template specialization

say you want to use the swap method provided in std namespace for your own class . Then instead of using the std::swap option blindly , that would involve making use that your class has at least a copy constructor and that the assignment operator is overridden.

It makes more sense to use template specialization for std::swap

class MyClass {
public:
void Swap(MyClass &) ;
};

namespace std {
template<> swap(MyClass& a, MyClass& b){
a.Swap(b);
}
}

so that way we just tune the default swap to use our class specific Swap and things become fast and simple for us .

C++ : std::mem_fun

Say you have a class

class MyClass {
public:
int DoSomething(){
}
};

now say you have

std::vector classes;

you can use something like this

for_each(classes.begin(), classes.end(), &DoSomething);

where DoSomething is

int DoSomething(MyClass& e){
d.DoSomething();
}


to call the member function DoSomething rather than the wrapper function use function calls like these

for_each(classes.begin(), classes.end(), mem_fun_ref(&MyClass::DoSomething));

if the classes vector was defined something like this

vector classes

then you would use something like this

for_each(classes.begin(), classes.end(), mem_fun(&MyClass::DoSomething));

C++ : Template specializations

Assuming you have a piece of code that is templatized and looks like this

template
void prettyPrint(T value, char* buf);

now assume that you are using sprintf for formatting the input .

that being the case you can use template specializations like this :

template<> void prettyPrint(int value, char* buf){
sprintf(buf, "%d", value);
}

template<> void prettyPrint(char value, char* buf){
sprintf(buf, "%c", value);
}