Friday, November 30, 2012

KD Tree Range Bounded Algorithm

Searching a K-d Tree is simple enough, its just a basic binary search based off the axis you're splitting by on your nodes. Doing a nearest neighbor search is one of the most basic operations you can do on a K-d Tree and is typically what you use this type of tree for. But because of the geometric properties of the tree itself and how each node creates a splitting plane for the space, we can make an awesome algorithm that returns points in the tree that are within a specific region of space.

This is for a 2 dimensional tree and space, but could be extended to 3 easily, and probably up to k dimensions after having a headache for a while:

So First off we need to be able to define a Region in space. Because the K-d Tree splits on planes, essentially we're going to define a box in K space, so it makes sense to have our regions be square in some fashion. So here's the code to construct a region:


public class Region{

double xleft   =  -Float.MAX_VALUE;
double xright  =   Float.MAX_VALUE;
double ybottom =  -Float.MAX_VALUE;
double ytop    =   Float.MAX_VALUE;


//Creates a region containing the entire coordinate plane
public Region(){
}


//Creates a Region defined by the four locations of its sides
public Region(double left, double right, double top, double bottom){
//Assume we might mess up and not put them in the right order for lefts and rights
if(left < right){
xleft = left;
xright = right;
}else{
xleft = right;
xright = left;
}
if(bottom < top){
ybottom = bottom;
ytop = top;
}else{
ybottom = top;
ytop = bottom;
}
}
}

I've made some assumptions about not being able to tell my left from my right but the key point that we'll take advantage of in the algorithm later is that a Region's default is to be the entire coordinate space. Next we need to add some helping functions to alter the region


public Region setLeft(double left){
this.xleft = left;
return this;
}

public Region setRight(double right){
this.xright = right;
return this;
}

public Region setTop(double top){
this.ytop = top;
return this;
}

public Region setBottom(double bottom){
this.ybottom = bottom;
return this;
}


//Checks to see if this Region contains the point
public boolean fullyContains(Node node){
float y =node.getY();
float x = node.getX();
return ybottom <= y && y <= ytop && xleft <= x && x <= xright;
}

public boolean fullyContains(Region r){
return xleft <= r.xleft && r.xright <= xright && r.ytop <= ytop && ybottom <= r.ybottom;
}

public boolean intersects(Region r){
return !(xright < r.xleft) && !(r.xright < xleft) && !(r.ytop < ybottom) && !(ytop < r.ybottom);
}

Now it's important that the setLeft,Right,Top, and Bottom sections return a Region, we'll see why in a bit. But the more interesting part of this code is the intersects function. To see if two Regions intersect, you could do an 8 part boolean expression checking all the possible combinations of the two Regions intersecting. OR you can be clever about it. The expression to see if two Regions don't intersect is far easier than the larger expression we just talked about. You just check if it's right side is strictly less than the other regions is the left side. You do this for all 4 sides and then you negate the expression. By deMorgans laws your OR's become not ands and pow. Your intersects function is quick, efficient and done. Now lets get to the actual algorithm:

private ArrayList<Node> boundedSearch(Region sRegion,ArrayList<Node> results,int depth,Region bRegion){
int axis = depth % coordinates.length;
if(this.isLeaf()){
if(sRegion.fullyContains(this)){
results.add(this);
}
}else{
//Subtree we need to redefine our bounding region bRegion
if(axis == 0){
//We are splitting on the x axis
if(sRegion.fullyContains(bRegion)){
//We are in the region so we report ourselves
results.add(this);
}else{
if(sRegion.fullyContains(this)){
results.add(this);
}
}
if(sRegion.intersects(bRegion)){
if(this.left != null){
//Search down the left with our splitting line as a bound on the right
return this.left.innerBoundedSearch(sRegion,results,depth+1,bRegion.setRight(this.getCoordinate(axis)));
}else{
//Null link return results
return results;
}
}
if(sRegion.intersects(bRegion)){
if(this.right != null){
//Search down the left with a splitting line as a bound on the left
return this.right.innerBoundedSearch(sRegion,results,depth+1,bRegion.setLeft(this.getCoordinate(axis)));
}
}
}else{
//We are splitting on the y  axis
if(sRegion.fullyContains(bRegion)){
//We are in the region so we report ourselves
results.add(this);
}else{
if(sRegion.fullyContains(this)){
results.add(this);
}
}
if(sRegion.intersects(bRegion)){
if(this.left != null){
//Search down the left with our splitting line as a bound on the right
return this.left.innerBoundedSearch(sRegion,results,depth+1,bRegion.setTop(this.getCoordinate(axis)));
}else{
//Null link return results
return results;
}
}
if(sRegion.intersects(bRegion)){
if(this.right != null){
//Search down the left with a splitting line as a bound on the left
return this.right.innerBoundedSearch(sRegion,results,depth+1,bRegion.setBottom(this.getCoordinate(axis)));
}
}
}
}
return results;
}

Alright, (one day I'll figure out how to display code nicer on these blog posts.) Let me describe how the algorithm works. The basic idea is that as you recurse down the tree, the splitting planes of the node you're visiting becomes a sides of a bounded region. This bounded region begins as the entire coordinate axis, then becomes half of that, then half of that, and etc etc. So each time you're creating a smaller and smaller space in which nodes can exist. Once this bounded region is contained within the search region, then we can report that entire sub tree as being contained. If we reach a leaf node, its a simple check to see if it is contained within the tree. 

I find that thinking of this geometrically is much easier than staring at just the code and trying to understand what it does. There is some work you have to do after the results is returned. You do need to collect all the leaves in the subtrees and add them to the results. 

public  ArrayList<Node> collectTree(ArrayList<Node> results){
//Traverse the tree and put all children in there
if(this.left!= null){
results = this.left.collectTree(results);
}
if(this.right!=null){
results = this.right.collectTree(results);
}
if(!results.contains(this)){
results.add(this);
}
return results;
}


Once you've collected these lists for each node you do need to add all together. But why write an arraylist merging function when you can do it all at once with a flatten. Observe:


private static ArrayList<Node> flatten(ArrayList<Node> nodes){
//Flatten each nodes subtree out.
ArrayList<Node> temp = new ArrayList<Node>();
for(Node node : nodes){
temp = node.collectTree(temp);
}
return temp;
}

Once you have this, its easy to collect the results of your search and report all of them in one list to a client. There is one important thing I'd like to mention though, in the collectTree function, notice the containment check at the end. This ensures no duplicate nodes are added to the list. If you didn't have this, you would report the subtree of any subtree returned by the search at least twice. Or precisely, the leaves would be reported for whatever depth they were away from the subtree that was reported.


The project I've used this in is located at:
Tree Class
Region

Thursday, September 6, 2012

Budget Buddy Transactions and such

 


Above are two snapshots of the transaction Area. In the left image, the +Add Transaction button causes some Javascript to display a form to add transactions, and in the right image the Add Account screen is shown. When transactions are actually in the system, it looks something like the image below:



I'm working on the Edit button right now, which will allow you to change a transactions Name, Amount, Or Date. The trick is going to be updating the account to reflect the change. But once thats done I can get into the meat of the program itself, which isn't its checkbook, but tagging transactions and reporting spending habits based on them.

Sunday, September 2, 2012

SQL foreign key issue. Errno 150 in BudgetBuddy

Budget buddy is coming along, Im working on the transactions page. I worked for a couple hours trying to get an htaccess file to work before realizing that my apache server wasn't set up right, and then had to rework a bunch of code to make the site work again. Alot of relative linking was going awry. Luckily a bit of GIT magic brought me back to working correctly so, its ok!

Coding today took a fun detour for about 10 minutes while I tried to figure out why I couldn't apply a foreign key to my database after successfully applying one before. Heres what I had as a problem and how I solved it:

3 Tables, userinfo which has a primary key of userid, accounts which has a userid associated with it and a name (as well as an amount), and then a transactions table I had just made. So I successfully altered transactions to reference userid from userinfo so that it cascades for both updating and deleting. And if anyone doesn't know how to do it, this is the page I go to everytime I need it: This site is good for foreign key info

But then I went to apply the accountname from transactions to be a foreign key from accounts and started getting this errono-150 bit. Completely unhelpful, saying I couldn't create a table such and such. This unhelpful bit led me to google the error number and I quickly stumbled onto this link. After looking at a couple of the reasons for error I figured it was because the account names weren't indexed. I hadn't told them to be primary keys because multiple users could have an account called "Checking". But then I read up on indexing and then used the mysql documentation on create index to add an index to my table. Tried to alter it again, and viola, foreign key accepted.

I hope that if anyone gets an error similar to the one I experienced that they find this blog and use the good couple of links to fix it!

On a side note:
Has anyone ever noticed that viola, when pronounced with a bit of an accent should probably be spelt walah?

Saturday, September 1, 2012

A break from BudgetBuddy for some evolutionary computation

http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/#python-code

I just found this bit of code to break a simple substitution cipher. Its an extremely simple hill climbing algorithm but I'm wondering if I couldn't improve on it by using different methods. I wonder how ALPS or another evolutionary tactic would fare against solving ciphers.


Friday, August 31, 2012

Budget Buddy Homepage


After a half hour of messing with the css, I finally got the buttons in my home page to center well. This is the main home page of budget buddy, if you have accounts it displays them like the above and if it doesn't then it displays the following error message:


All in all, the login, signup, and now home page are functioning correctly, now I just have to make everything else! So excited!


Tuesday, August 28, 2012

Budget Buddy in php

https://github.com/EJEHardenberg/BudgetBuddy


Well I've tried to do this project a few times already, and most of the time the method of storing the data was the primary inconvenience in java and c#. But with php I can use mysql to easily store anything and everything.

So I'm modeling it like an app, and this is what I have so far. A clean interface, and a sign up and login page that are working. Well, I'm currently working on making the log-in secure but besides that its all good. This has been my baby for the last 2 days. And after some CSS magic and stack overflow results I fixed an error that had stuck me and I can keep working.

Word for the wise, do NOT store hash's into a binary type sql field. Binary types mess with strings and can cause string comparisons to result in errors, I learned this the hard way over the past few days until I stumbled onto a small comment on a stack overflow page about hashing.

Tuesday, July 17, 2012

Complete



As you can see, I added a little bit because I forgot about youtube linking. But tada, theres the input, a few button clicks later and the second image is what results. Cool right?

This literally took about 30 minutes or so to whip out. A simple iterator goes through the item lists (0000,242323, 2323) and makes the links to the SKU's. And besides all that its simple plug in play. A file stream and a stream writer object are all thats neccesary to use.

Also, I have it generate simple random file names by using the Path.getRandomeFileName() function.


Here's all the code in very zoomed out mode, 142 lines

SKU Maker Basic Interface

So I've finished up the basic interface design. I might mess with the color scheme a little to make it easy on the eyes, but now let the coding begin! I figure it will be fairly basic and easy. All I'm doing is generating some xml from the information I'm getting from my text boxes. The only thing that I'm going to probably have to watch out for is escaping special characters. 

Oh, and of course change the default form name to a good name for the program. Probably going to call it Sku Maker or something. Also I've been thinking about causing the add sku button to either just do a simple pop up dialog, or to have it able to read from Excel datasheets, because I do have a good amount of data in excel... we'll see how ambitious I am after coding the basics

New Practical Project

For an internship/subcontracting job I'm doing right now, I have to do a lot of xml. Most of it is the same, and only 4 or so things change for each item I work with. Copying and pasting everything is rather a bore, and clicking and highlighting what I have to change is also tedious, so I had a thought.

Why not automate most of it and put some of my skills to work?

The answer? HECK YEAH NEW PROJECT

Its simple and I imagine I can get done with it in a day or soon depending on how my other work keeps me. (Website work and actual support myself work)

I'm doing it in C# since the file capabilities are really superb in that language, not too mention using visual study means that I'll have an interface up really fast.

I'll keep you all posted!

Thursday, July 12, 2012

Object Oriented Approaches to Websites

So far this summer, I haven't had any superbly ambitious goals or projects like I did last summer. But I have been working on revamping a website with a friend. The website is for an organization we're apart of, myself being one of the people who run it, and him being next years definite choice for one of three leadership positions.

Anyway, we're working on the website, and we start to take an OOP style on it. Using database objects to handle database queries and information we need from them, specialized entry objects for the database objects to accept and play with. Validation objects that act as decorators on those entry objects to make sure they're not malicious and such. Its pretty fun. But sometimes I wonder if I'm going too far with it.

It makes sense in concept to do this. Have a simple interface for the database, with a few core functions exposed, and a sure fire way to have the data we need by using an object for the data structure passed around. But at the same time, making an object simply to hold data thats there anyway and then pass it along seems a little silly. But I mean, by making that object and passing it, you're guaranteeing that the information you'd like will be there to pass along to the database. It's nice. Reliable and definitely a bonus of the OOP design. Also, by enforcing a standard for our models in our MVC design, we make it very easy to extend the website by future organization runners. A few controllers and a lot of models work well.

I wish I had a project to keep my occupied though. I thought about an inference engine in ruby, but I'm not sure yet.

Tuesday, May 1, 2012

Q-Learning Oscillatory Problems Solved

So, in implementing Q-Learning I found that often the situation would arise where the agent would move back and forth, back and forth, between the same adjacent squares. I thought about this for a bit, then decided this must be the case:

0        0    0  Initially on left
.25-> 0    0  Moves to right and evaluates space it was on
.25     0    0 Searchs for most valuable space near it
.25 <-.25 0 Finds the left space and moves
.50 ->.25 0 sees that the right space has value and moves, updating the leftmost as well
ad. infitum.
implement

After a bit of investigation I found my suspicions confirmed and proceeded to implement a few solutions. One being a varying epsilon during the total number of episodes, allowing for max exploration (completely random movements) in the beginning and then controlled exploitation (the Q-Learning algorithm itself chooses what to do, albeit with a small epsilon percent chance of random moves) later on. -- This strategy did not work very well.

I also implemented a type of memory, where during a single episode the agent would not get a reward for visiting the same space twice, and a modified version where the agent recieved a reward the first time it entered the food space from the left or right, but never recieved it again if it moved into the space from the left or right, and likewise on up and down. This was to try to cancel out oscillations. I also created a version where not just food, but all rewards were (including negative reinforcement) were taken away after the first visit. All these methods improved the performance of the algorithm drastically! It was great.

Saturday, April 14, 2012

Implementing Q-Learning

For a course, I'm currently trying to implement Q-Learning in Matlab on a simple problem. The problem is thus: Given a maze with walls surrounding the outside, a line of food to a goal point, and some designated start point. Have a small agent using Q-Learning techniques develop the ability to follow the line of food.

Q-Learning works, in the general sense like this:

From your current state take an action
What reward did you get from this action?
Update the state-action pair from before you moved with this reward that you got
Repeat until you find good estimates of the domain space in which you exist.

This is a vague description is good enough to develop an intuition for how the reinforcement learning paradigm of Machine Learning works in general. In specificity

Q(s,a) = Q(s,a) + a[ R + g*max(Q(s',a')-Q(s,a)]

Where a and g are scalar parameters that effect how the algorithm itself learns. The tricky thing in this case is that the s' and a' (standing for the next state and action pair ) are unknown if you were to take this equation literally. Q(s,a) stands for the state-action pair. In my implementation this is Q(x,y,a) where (x,y) is the position of the agent in the space, and the a is the action it took. Because my agent exists within an MxN grid, and can move left right up and down it has a total of MxNx4 possible states. Which for a simple sized grid of 25x25 is already above 2000 possible states. With such a large search space its surprising that this type of techniques works at all. Anyway, before I get distracted by complexity details...

With an initial Q(s,a) with an arbitrary a for the state you're given, you can then move into your algorithm, find the next state (chosen by picking the most valuable looking state around you with respect to your Q matrix), and then you can update old state with the state you just found. In other words, your most recently found Q pair is your prime terms in the equation above.

Sutton and Barto's book on reinforcement learning is available online at
http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node65.html

and is a standard book for reinforcement learning. Or so I'm told.



The cool thing I'd like to mention is that I create my environment by using paint, then use matlab to load in the image and create my environment from it. Unforunately, because I prefer my complexity small both bitmaps are rather small and beefing them up for view on this blog has messed with the resolution a bit. But take my word, the red around the outside is a single pixel wide and represents a wall. The black dot is the goal point, the purplish is the food that the agent must follow to the goal and of course the white is empty space. You can see it better in the top picture, but the start location is indicated by the green pixel. Anywho, once this is loaded into matlab you end up with something like this:


The purple dot is the agent, the blue next to the red is the start state, the cyan is the goal, and the red is the food. Blue around the edges is of course the wall.

The image is completely animated during runtime so I can watch how well or poorly the reinforcement learning is coming. 

Tuesday, April 3, 2012

Another interesting article - Back Propagation

http://itee.uq.edu.au/~cogs2010/cmc/chapters/BackProp/index2.html

For my CS 295 Machine Learning class, I was reading up on back propagation algorithms. This is a really good page that describes the principles really well. I'm currently implementing a back propagation algorithm which is classifying some data that my professor provided us. It's pretty interesting, and rather fun. Although using something like a blackbox ANN is kind of confusing, only because it's so very annoying to debug.

Sunday, March 25, 2012

Article my friend shared with me

http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf

Even if you only read the abstract, this is a really cool paper.

Wednesday, March 21, 2012

Wiimote Whiteboard Demonstration

http://www.youtube.com/watch?v=VwhGGChEUHg

This is an alpha demonstration of the Wiimote Whiteboard project that the project group that I'm in through UVM's C.S. Crew is a part of. My part in this project was project director and chief software engineer (if I had to give a title to it). In other words, I was responsible for delegating tasks out to each team member according to their ability as well as taking on a portion of the coding myself. Also, since I built the fundamentals of the program and held the master copy of the files I was also the one in direct contact with each group member for assistance on integrating things.

So let me break down what you're seeing in this short video (besides my Whistling). On the surface, you're seeing a projection of the screen from my laptop onto a canvas. There is (out of the picture) a Wiimote facing dead on to the canvas, and in my hand is a small IR LED attached to a 22 Ohm resistor and 2 1.5V batteries. The wiimote functions as a sensor that picks up the IR LED output. (Infrared light), this wiimote is paired to my laptop through a bluetooth dongle. This device is then found by C# software written by my group and Brian Peek's Wiimote Library.

The program pairs to the wiimote using Peek's library, and from there a wrapper class allows for points found from the Wiimote to be sent to the program. This wrapper class was my task in the group. The UI queries the wrapper class for another point and then decides to either draw, or to click a button depending on the points it recieves. There a few other things that I'd like to mention without talking about the details. The program is a completely multithreaded program. The UI runs on it's own thread, and the wrapper class is queried on a seperate thread. There a few timers that run during the course of the program, during calibration timers run to fill up streams of points that are then interpolated to configure the wiimote's point of view into one that transforms into the picturebox on the form.

After calibration, points are queued as well as written out to a data file, and whenever the UI asks for a point, a point is dequeued from the queue and shown on the drawing pane, or causes a click. A few windows 32 dll's are used to cause the mouse to follow the IR pen and to help aid clicking a button. There is a variable rate of points coming in from the queue, this is decided by a variable normally set to 10, that corresponds to a timer querying the queue every 10 milliseconds to sync up with the Wiimotes 100 report generations a second. All of this combined enables us to do what we did in that short video.

Monday, January 30, 2012

Lucid Charts

http://www.lucidchart.com/ 

The other day I was working on a group project (whose entire summary would be beyond this quick post, but will more than likely soon to be coming) and was creating some diagrams to model the general flow of the programs execution. I was doing this in my notebook, but got the compulsion to create a flow chart. I had just moved over to start up paint.net when I decided to see if there was a free online flow chart maker available. Wonderfully, there was. The above link is a fantastic resource for anyone who organizes and likes to keep a stable head during their projects. Signing up is free and can be done through a google or yahoo account, although the free version does limit the number of objects you have in your diagram to about 60.

Despite the limit on the free version, the software is fantastic and you edit the diagrams directly in your browser. My favorite part about this is that there's built in UML tools. Which is really great for creating project documents.