Saturday, April 16, 2011
F14 doesn't install Perl by default?!
WTF!? Just installed Fedora14 32-bit It doesn't have Perl installed by default? Lame!
Monday, January 3, 2011
Antlr 3.3 Sanity Setup
These are the steps to follow to setup Antlr v3.3 on Ubuntu 10.04
- Download the antlrworks-1.4.2.jar
- Add antlrworks-1.4.2.jar to the CLASSPATH variable. For example: export CLASSPATH=.:/path/to/jar/antlrworks-1.4.2.jar
- Create a simple grammar called Expr.g. It's contents are:
prog: stat+ ;
stat: expr NEWLINE
| ID '=' expr NEWLINE { System.out.println("you entered a statement!"); }
| NEWLINE
;
expr: multExpr (('+'|'-') multExpr)*
;
multExpr
: atom ('*' atom)*
;
atom: INT
| ID
| '(' expr ')'
;
ID : ('a'..'z'|'A'..'Z')+ ;
INT : '0'..'9' ;
NEWLINE : '\r'? '\n' ;
WS : (' '|'\t'|'\n'|'\r')+ { skip(); } ;
4. Create a java file called Test.java that will call the objects created by Antlr3. Test.java's contents are:
import java.io.*;
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
public class Test {
public static void main(String args[]) throws Exception {
ExprLexer lex = new ExprLexer(new ANTLRInputStream(System.in));
CommonTokenStream tokens = new CommonTokenStream(lex);
ExprParser parser = new ExprParser(tokens);
parser.prog();
}
}
5. Compile the antlr grammar and Test.java file as follows:
java org.antlr.Tool Expr.g
javac *.java
6. Test your grammer by then typing:
java Test
and entering this expression:
a=1+2
followed by ctrl-d. This should result in the this statement appearing:
you entered a statement!
Sunday, June 6, 2010
haskell.org still down!
In case you were wondering, haskell.org has been down all weekend. I hopw it is back up soon. The 2010 ICFP Programming Contest is only 2 weeks away.
Monday, May 31, 2010
Correcting Towers of Hanoi Haskell Solution
I've been really having fun playing with Haskell. I found a solution via Wikipedia for the Towers of Hanoi. The solution is here http://www.kernelthread.com/projects/hanoi//html/hs.html.
This solution will not compile with ghci v6.12.1. This is the corrected solution I tested and confirmed works with ghci v6.12.1:
dohanoi :: (Num a) => a -> a -> a -> a -> [(a,a)]
dohanoi 0 _ _ _ = []
dohanoi n from to using = let m=n-1
in dohanoi m from using to ++ [(from,to)] ++ dohanoi m using to from
hanoi :: (Num a) => a -> [(a,a)]
hanoi n = dohanoi n 1 3 2
This solution will not compile with ghci v6.12.1. This is the corrected solution I tested and confirmed works with ghci v6.12.1:
dohanoi :: (Num a) => a -> a -> a -> a -> [(a,a)]
dohanoi 0 _ _ _ = []
dohanoi n from to using = let m=n-1
in dohanoi m from using to ++ [(from,to)] ++ dohanoi m using to from
hanoi :: (Num a) => a -> [(a,a)]
hanoi n = dohanoi n 1 3 2
Sunday, May 16, 2010
Parsing notes
Top-down vs. bottom-up
Top-down(e.g. ANTLR) is a left most derivation(LL)
Implemented as a recursive-descent algorithm
Finds next node in left sentential form where a non-terminal is replaced with its equivalent RHS.
Bottom-up(such as yacc or parsec) is a right most derivation(LR)
Find a non-terminal in right sentential form such that non-terminal can be replaced with its equivalent LHS.
Complexity of parsing algorithms ususally O(n^3)
LL parsers cannot handle left-recursion. e.g. A->A+B will never stop
left-recursion is a rule where the LHS rule name is also on the RHS.
Pairwsie disjoint test used to evaluate a grammar if it can be LL parsed.
If a rule passes the pairwise disjoint test, then this means no RHS of a rule has a common terminal token.
left factoring(grouping common terminal/non-terminals together toward the left side) can help wiht LL parsers but not in all cases.
LR usually implemented as shift reduce algorithms.
LR advantages:
Top-down(e.g. ANTLR) is a left most derivation(LL)
Implemented as a recursive-descent algorithm
Finds next node in left sentential form where a non-terminal is replaced with its equivalent RHS.
Bottom-up(such as yacc or parsec) is a right most derivation(LR)
Find a non-terminal in right sentential form such that non-terminal can be replaced with its equivalent LHS.
Complexity of parsing algorithms ususally O(n^3)
LL parsers cannot handle left-recursion. e.g. A->A+B will never stop
left-recursion is a rule where the LHS rule name is also on the RHS.
Pairwsie disjoint test used to evaluate a grammar if it can be LL parsed.
If a rule passes the pairwise disjoint test, then this means no RHS of a rule has a common terminal token.
left factoring(grouping common terminal/non-terminals together toward the left side) can help wiht LL parsers but not in all cases.
LR usually implemented as shift reduce algorithms.
LR advantages:
- Works for almost all grammars
- Works on more grammars than most other bottom-up algorithms
- Syntax errors detected early
- LR grammars are a superset of the grammars parsable by LL grammars
Monday, January 4, 2010
Setup of Wiktionary (Simplified) Android project
Looks like my previous instrutions for Api Demos don't apply for the new Simplewiktionary project for Android.
Even File->Import and other variations are failing. I discovered that something new and more specific was required. You might be wondering why I'm even bothering to blog this. Well, it seems that there are many wrong ways to get these sample projects into Eclipse. It seems that the 'art' is find the few right ways to do this.
1. Start Eclipse
2. File->New->Project->Android->Android Project
3. Click on the 'next' button
4. Choose your build target
5. Uncheck the 'Create Activity' checkbox
6. Specify the Project Name as 'WiktionarySimple'
7. Uncheck the 'Use default location' checkbox
8. Click on the 'Browse' of the Location textbox and go to the WiktionarySimple directory created by unzipping latest_samples.zip in the directory of your choice.
9. In the contents area, select the radio button 'Create project from existing source'
10. In the properties area, set the application name to 'WiktionarySimple'
11. Click the 'Finish' button
12. If these steps were followed, when Eclipse is done updating the workspace, the WiktionarySimple project will be compiled and the R.java file will be generated in the project.
Even File->Import and other variations are failing. I discovered that something new and more specific was required. You might be wondering why I'm even bothering to blog this. Well, it seems that there are many wrong ways to get these sample projects into Eclipse. It seems that the 'art' is find the few right ways to do this.
1. Start Eclipse
2. File->New->Project->Android->Android Project
3. Click on the 'next' button
4. Choose your build target
5. Uncheck the 'Create Activity' checkbox
6. Specify the Project Name as 'WiktionarySimple'
7. Uncheck the 'Use default location' checkbox
8. Click on the 'Browse' of the Location textbox and go to the WiktionarySimple directory created by unzipping latest_samples.zip in the directory of your choice.
9. In the contents area, select the radio button 'Create project from existing source'
10. In the properties area, set the application name to 'WiktionarySimple'
11. Click the 'Finish' button
12. If these steps were followed, when Eclipse is done updating the workspace, the WiktionarySimple project will be compiled and the R.java file will be generated in the project.
Saturday, January 2, 2010
Creating Android Sample Application
Recently, Android 2.0 had some new sample projects added. They are available as a .zip file from the Android developers site. However, if you unzip and import a project, something wrong happens. The R.java is not generated. The instructions for importing these sample project are as follows from the Android developer site:
You can easily create new Android projects with these samples, modify them if you'd like, then run them on an emulator or device. For example, to create a project for the API Demos app from Eclipse, start a new Android Project, select "Create project from existing source", then select ApiDemos in the samples/ directory. To create the API Demos project using the android tool, execute:
android update project -s -n API Demos -t -p /samples/ApiDemos/
The given instructions give 2 possible actions. The first, as indicated previously, does not work. The second action uses the 'android' executable which is part of the SDK. The options given do the following:
update project : updates an existing android project
-s : only errors produce output (silent mode)
-n : name of new android device (in this case it is 'API Demos'
-t : target id of new android device
-p : Location path of the directory where the new AVD will be created
If you run the above 'android' command-line, you will get the following result:
Updated default.properties
Updated local.properties
File build.xml is too old and needs to be updated.
Added file /home/me/Projects/A20/samples/ApiDemos/build.xml
Updated default.properties
Updated local.properties
File build.xml is too old and needs to be updated.
Added file /home/me/Projects/A20/samples/ApiDemos/tests/build.xml
So, neither of the above procedures really lets you create one of the sample projects for use. The entry will show you the right way to do this for the new ApiDemos sample.
1. The ApiDemos project is an Android 1.6 project. So, in general, make sure before using any of the sample projects that you have the right SDK version installed.
2. Start Eclipse.
3. File->New->Project...->Android->Android Project
4. click on the 'next' button
5. In the next window that appears, select the radio button 'Create Project from existing source'
6. Click on the 'Browse...' button next to the 'Location' text box.
7. Browse to the directory that contains the ApiDemos directory from the latest_samples.zip file.
The 'Location' text box should have a path like /path/to/latest/ApiDemos
8. Select OK
9. In the 'Build Target' area, select the 'Android 1.6' build target.
10. Select the radio button 'Create Project from Existing Sample'
11. In the 'Samples' drop-down, select 'ApiDemos'
12. Click on the 'Finsh' button
13. If this is succesful, the ApiDemos project will build with no errors and the R.java files will be generated automagically.
The above method should be used for the other samples, too. If you do not, the R.java file will not be generated.
You can easily create new Android projects with these samples, modify them if you'd like, then run them on an emulator or device. For example, to create a project for the API Demos app from Eclipse, start a new Android Project, select "Create project from existing source", then select ApiDemos in the samples/ directory. To create the API Demos project using the android tool, execute:
android update project -s -n API Demos -t
The given instructions give 2 possible actions. The first, as indicated previously, does not work. The second action uses the 'android' executable which is part of the SDK. The options given do the following:
update project : updates an existing android project
-s : only errors produce output (silent mode)
-n : name of new android device (in this case it is 'API Demos'
-t : target id of new android device
-p : Location path of the directory where the new AVD will be created
If you run the above 'android' command-line, you will get the following result:
Updated default.properties
Updated local.properties
File build.xml is too old and needs to be updated.
Added file /home/me/Projects/A20/samples/ApiDemos/build.xml
Updated default.properties
Updated local.properties
File build.xml is too old and needs to be updated.
Added file /home/me/Projects/A20/samples/ApiDemos/tests/build.xml
So, neither of the above procedures really lets you create one of the sample projects for use. The entry will show you the right way to do this for the new ApiDemos sample.
1. The ApiDemos project is an Android 1.6 project. So, in general, make sure before using any of the sample projects that you have the right SDK version installed.
2. Start Eclipse.
3. File->New->Project...->Android->Android Project
4. click on the 'next' button
5. In the next window that appears, select the radio button 'Create Project from existing source'
6. Click on the 'Browse...' button next to the 'Location' text box.
7. Browse to the directory that contains the ApiDemos directory from the latest_samples.zip file.
The 'Location' text box should have a path like /path/to/latest/ApiDemos
8. Select OK
9. In the 'Build Target' area, select the 'Android 1.6' build target.
10. Select the radio button 'Create Project from Existing Sample'
11. In the 'Samples' drop-down, select 'ApiDemos'
12. Click on the 'Finsh' button
13. If this is succesful, the ApiDemos project will build with no errors and the R.java files will be generated automagically.
The above method should be used for the other samples, too. If you do not, the R.java file will not be generated.
Friday, January 1, 2010
Accessing GPS on Android 2.0 Platform
One of the great things about building applications for an Android device is the ability to create GPS aware applications. In a single hardware platform, using Android, it is possible to create an application that will change behavior based upon real-world coordinates.
The hard part is getting started. At the moment, there are very few tutorials on creating GPS aware Android apps. I've spent the past few days digging through the Android developer sites and other blogs. I finally found the minimal amount of information to create a very simple GPS aware application. This application will list the current longitude and latitude. In addition to the minimal number of steps needed, I will show you how to test the GPS aware app via the Eclipse debugger and ddms tool from the Android SDK.
My setup consists of Ubutnu 9.04 32-bit, Java 1.6.0_17, Android SDK 2.0, and Eclipse build 20090619-0625. The application created will display the current longitude and latitude as a simple ListView.
Steps to create an Android 2.0 application that will display the current longitude and latitude using an Android phone's GPS
1. Open Eclipse and create an Android project.
2. The project you create will be based upon the Andriod ListActivity. Inherit from ListActivity. For purposes of these instructions, I will assume that this new subclass is called MyGps.
3. In your new Android project, open the AndroidManifest.xml file. Add the following entry just after the tag:
android:name="android.permission.ACCESS_FINE_LOCATION" />
This entry is needed to get info from the Android GPS.
4. In the definition of the MyGPS class, you need to define 2 private helper classes inside the MyGPS class. The first private helper class you need to add will implement the GpsStatus.Litener interface.. The second private helper class you need to add will implement the LocationListener interface. For the purposes of these instructions, the helper class that implements the GpsStatus.Listener interface will be callsed MyGpsStatus. The helper class that implements the LocationListener interface will be called MyLocationListener. In MyLocationListener, create a constructor that takes as argument a ListActivity object.
5. In the MyGps class, add these members:
LocationManager myLocationManager;
ArrayList results;
String[] temp;
Criteria myBestCriteria;
String myBestGps;
myLocationManger is an instance of the LocationManager class that is used to check if the GPS feature is available and to set the sensitivity of GPS position changes.
The results ArrayList holds the various info from GPS queries.
The info stored in the ArrayList results is converted into a regular String[] array called temp.
myBestCriteria is an instance of a Criteria class. This instance is used to define the desired features of the GPS. myBestCriteria can be used to define the number of attributes that a given GPS source will provide(such as altitude, speed, bearing, etc). myBestCriteria is also used to define the amount of position change that is considered a 'change'.
The myBestGps is a String object that holds the name of the GPS provider that best meets the myBestCriteria requirements.
6. In the onCreate method of the MyGps class definition, do the following:
a. Initialize the myLocationManager reference with an instance created by the getSystemService method.
b. Initialize the results ArrayList. Add an initial item so that there is at least 1 member of the array is not null.
c. Use addGpsListner to add a GPS listner instance to MyGps. Use the creation of MyGpsStatus object as an argument.
d. Use requestLocationUpdates to define the resolution of GPS change.
e. Instantiate myBestCriteria's Critera object.
f. Initialize the features of the GPS source by using the various methods of the Criteria class.
g. Get the name of the best GPS source by using the getBestProvider method on the myLocationManger object. Use myBestCriteria as an argument.
h. Display the initial contents of the GPS features by using these last lines of code at the end of the onCreate method:
setListAdapter(new ArrayAdapter(this,
android.R.layout.simple_list_item_1, temp));
getListView().setTextFilterEnabled(true);
temp must be the String[] version of results.
i. Go to the private class definition of MyLocationListener and implement the onLocationMethod as follows:
temp = new String[ 3 ];
String tempLatitude = String.valueOf(location.getLatitude());
String tempLongitude = String.valueOf(location.getLongitude());
temp[0] = new String("status");
temp[1] = tempLatitude;
temp[2] = tempLongitude;
listactivity.setListAdapter(new ArrayAdapter(listactivity,
android.R.layout.simple_list_item_1, temp));
The setListAdatper method is sent to the listactivity reference, which points to the MyGps object. The setListAdapter redisplays the new info from the GPS reading. Note, this method of displaying new info is different from what one finds in the current Android 2.0 docs. The current Android 2.0 docs say that the onUpdate method will work but I've found that it does not work.
j. Download the application to the emulator and wait for the emulator to run the application.
k. When the application is running, run the ddms.
m. In the ddms gui, select the instance of the emulator.
n. In the upper right hand corner area of the ddms gui, click on the rh arrow until the 'Emulator Control' tab is selected.
o. Scroll down until you see the 'Location Controls' area in the 'Eumlator Control' area. The textboxes and send button should not be grayed out. If they are, go back to step m and make sure that the instance of the emulator is selected.
p. Change the longitude and/or latitude coordiantes.
q. Hit the send button.
r. When the send button is clicked, you should see the contents of the application on the Android emulator show the new longitude and/or latitude coordinates.
The hard part is getting started. At the moment, there are very few tutorials on creating GPS aware Android apps. I've spent the past few days digging through the Android developer sites and other blogs. I finally found the minimal amount of information to create a very simple GPS aware application. This application will list the current longitude and latitude. In addition to the minimal number of steps needed, I will show you how to test the GPS aware app via the Eclipse debugger and ddms tool from the Android SDK.
My setup consists of Ubutnu 9.04 32-bit, Java 1.6.0_17, Android SDK 2.0, and Eclipse build 20090619-0625. The application created will display the current longitude and latitude as a simple ListView.
Steps to create an Android 2.0 application that will display the current longitude and latitude using an Android phone's GPS
1. Open Eclipse and create an Android project.
2. The project you create will be based upon the Andriod ListActivity. Inherit from ListActivity. For purposes of these instructions, I will assume that this new subclass is called MyGps.
3. In your new Android project, open the AndroidManifest.xml file. Add the following entry just after the
This entry is needed to get info from the Android GPS.
4. In the definition of the MyGPS class, you need to define 2 private helper classes inside the MyGPS class. The first private helper class you need to add will implement the GpsStatus.Litener interface.. The second private helper class you need to add will implement the LocationListener interface. For the purposes of these instructions, the helper class that implements the GpsStatus.Listener interface will be callsed MyGpsStatus. The helper class that implements the LocationListener interface will be called MyLocationListener. In MyLocationListener, create a constructor that takes as argument a ListActivity object.
5. In the MyGps class, add these members:
LocationManager myLocationManager;
ArrayList
String[] temp;
Criteria myBestCriteria;
String myBestGps;
myLocationManger is an instance of the LocationManager class that is used to check if the GPS feature is available and to set the sensitivity of GPS position changes.
The results ArrayList
The info stored in the ArrayList
myBestCriteria is an instance of a Criteria class. This instance is used to define the desired features of the GPS. myBestCriteria can be used to define the number of attributes that a given GPS source will provide(such as altitude, speed, bearing, etc). myBestCriteria is also used to define the amount of position change that is considered a 'change'.
The myBestGps is a String object that holds the name of the GPS provider that best meets the myBestCriteria requirements.
6. In the onCreate method of the MyGps class definition, do the following:
a. Initialize the myLocationManager reference with an instance created by the getSystemService method.
b. Initialize the results ArrayList
c. Use addGpsListner to add a GPS listner instance to MyGps. Use the creation of MyGpsStatus object as an argument.
d. Use requestLocationUpdates to define the resolution of GPS change.
e. Instantiate myBestCriteria's Critera object.
f. Initialize the features of the GPS source by using the various methods of the Criteria class.
g. Get the name of the best GPS source by using the getBestProvider method on the myLocationManger object. Use myBestCriteria as an argument.
h. Display the initial contents of the GPS features by using these last lines of code at the end of the onCreate method:
setListAdapter(new ArrayAdapter
android.R.layout.simple_list_item_1, temp));
getListView().setTextFilterEnabled(true);
temp must be the String[] version of results.
i. Go to the private class definition of MyLocationListener and implement the onLocationMethod as follows:
temp = new String[ 3 ];
String tempLatitude = String.valueOf(location.getLatitude());
String tempLongitude = String.valueOf(location.getLongitude());
temp[0] = new String("status");
temp[1] = tempLatitude;
temp[2] = tempLongitude;
listactivity.setListAdapter(new ArrayAdapter
android.R.layout.simple_list_item_1, temp));
The setListAdatper method is sent to the listactivity reference, which points to the MyGps object. The setListAdapter redisplays the new info from the GPS reading. Note, this method of displaying new info is different from what one finds in the current Android 2.0 docs. The current Android 2.0 docs say that the onUpdate method will work but I've found that it does not work.
j. Download the application to the emulator and wait for the emulator to run the application.
k. When the application is running, run the ddms.
m. In the ddms gui, select the instance of the emulator.
n. In the upper right hand corner area of the ddms gui, click on the rh arrow until the 'Emulator Control' tab is selected.
o. Scroll down until you see the 'Location Controls' area in the 'Eumlator Control' area. The textboxes and send button should not be grayed out. If they are, go back to step m and make sure that the instance of the emulator is selected.
p. Change the longitude and/or latitude coordiantes.
q. Hit the send button.
r. When the send button is clicked, you should see the contents of the application on the Android emulator show the new longitude and/or latitude coordinates.
Saturday, December 26, 2009
How to get longitude and latitude from Google Maps
So, I have a new obsession. I've been toying around with Android and creating gps aware applications. I don't own my own Android phone yet. I'm having a hard time deciding if I want a Droid or an Eris. In the meantime, I've been hanging around the Android sites, learning as much as I can about writing Android apps. One of the areas I'm interested in is GPS aware apps, where apps change their behavior based upon the current GPS position.
The Android 2.0 SDK comes with its own Android device simulator. which can simulate an Android device that is changing its position in the real-world. One of the ways it can simulate this behavior is for a user to submit a longitude and latitude. Well, how do you get longitude and latitude coordinates if you don't own a GPS and/or the location you want to simulate is not accessible. Google Maps can be used to provide longitude and latitude coordinates.
First, go to Google Maps and enter the address of interest. The address you just entered will appear on the left-hand side. Move the mouse over the address which appears as a link. When you move your mouse over the link, the contents will appear in the bottom of your browser. In my case, I'm using Firefox. It's possible your browser may not do this. In the link that appears, look for the string that appears as follows:
ssl=X,Y
X will be the longitude. Y will be the latitude.
The Android 2.0 SDK comes with its own Android device simulator. which can simulate an Android device that is changing its position in the real-world. One of the ways it can simulate this behavior is for a user to submit a longitude and latitude. Well, how do you get longitude and latitude coordinates if you don't own a GPS and/or the location you want to simulate is not accessible. Google Maps can be used to provide longitude and latitude coordinates.
First, go to Google Maps and enter the address of interest. The address you just entered will appear on the left-hand side. Move the mouse over the address which appears as a link. When you move your mouse over the link, the contents will appear in the bottom of your browser. In my case, I'm using Firefox. It's possible your browser may not do this. In the link that appears, look for the string that appears as follows:
ssl=X,Y
X will be the longitude. Y will be the latitude.
Tuesday, November 10, 2009
1-liner for creating symbolic links in /usr/local/bin
If you have to create more symbolic links than you can create manually, this is a useful 1-liner. In this case, this 1-liner was used to install the binaries from Java 1.6 into /usr/local/bin:
find /usr/local/jdk1.6.0_17/bin|grep -vE "bin$|ControlPanel$"|perl -ne 'system "ln -s $_";'
This sort of 1-liner is useful when the number of symbolic links to create is greater than 1. It easily scales to 100's and even 100's of symbolic links. With the grep tool, one could even easily filter out items by name. Very useful!
find /usr/local/jdk1.6.0_17/bin|grep -vE "bin$|ControlPanel$"|perl -ne 'system "ln -s $_";'
This sort of 1-liner is useful when the number of symbolic links to create is greater than 1. It easily scales to 100's and even 100's of symbolic links. With the grep tool, one could even easily filter out items by name. Very useful!
Wednesday, October 14, 2009
New Machine Learning API's to Explore
Today on reddit, someone asked about freely available machine learning API's.
Before the list gets buried, I'm duplicating the contents of that thread here for future exploration:
Weka - Java based ML API
http://www.cs.waikato.ac.nz/ml/weka/
Toolkit for Advanced Disrimnative Modeling
http://tadm.sf.net/
Mallet - Java based ML API
http://mallet.cs.umass.edu/
WekaUT - An extension of Weka that adds clustering
http://www.cs.utexas.edu/users/ml/risc/code/
LibSVM - SVM API
http://www.csie.ntu.edu.tw/~cjlin/libsvm/
SVMlight - A C API for svm
http://svmlight.joachims.org/
C++ API for Neural Networks
http://github.com/bayerj/arac
Torch5 - A Matlab-like ML environment
http://torch5.sourceforge.net/
R - Open source statistical package that can be used for ML
http://cran.r-project.org/web/views/MachineLearning.html
pyML - Python API for ML
http://pyml.sourceforge.net/
Rapidminer - Open Source Data Mining Tool
http://rapid-i.com/wiki/index.php?title=Main_Page
Orange - An Open Source Data Mining Tool (Python and GUI based)
http://www.ailab.si/orange/
Glue - Open Source API for reinforcement learning (Can be used with multiple languages simultaneously)
http://glue.rl-community.org/wiki/Main_Page
Vowpal Rabiit - Learning API from Yahoo Research
http://hunch.net/~vw/
Before the list gets buried, I'm duplicating the contents of that thread here for future exploration:
Weka - Java based ML API
http://www.cs.waikato.ac.nz/ml/weka/
Toolkit for Advanced Disrimnative Modeling
http://tadm.sf.net/
Mallet - Java based ML API
http://mallet.cs.umass.edu/
WekaUT - An extension of Weka that adds clustering
http://www.cs.utexas.edu/users/ml/risc/code/
LibSVM - SVM API
http://www.csie.ntu.edu.tw/~cjlin/libsvm/
SVMlight - A C API for svm
http://svmlight.joachims.org/
C++ API for Neural Networks
http://github.com/bayerj/arac
Torch5 - A Matlab-like ML environment
http://torch5.sourceforge.net/
R - Open source statistical package that can be used for ML
http://cran.r-project.org/web/views/MachineLearning.html
pyML - Python API for ML
http://pyml.sourceforge.net/
Rapidminer - Open Source Data Mining Tool
http://rapid-i.com/wiki/index.php?title=Main_Page
Orange - An Open Source Data Mining Tool (Python and GUI based)
http://www.ailab.si/orange/
Glue - Open Source API for reinforcement learning (Can be used with multiple languages simultaneously)
http://glue.rl-community.org/wiki/Main_Page
Vowpal Rabiit - Learning API from Yahoo Research
http://hunch.net/~vw/
Tuesday, October 13, 2009
FC9 64-bit and VMware Workstation 6.5.3 issue with VMware Tools
I was working with a VMware appliance, which was configured to use the guest OS Fedora Core 9 64-bit.
I was using this guest OS with the latest vesion of VMware Workstation, v6.5.3. I downloaded the latest version of v6.5.3 today and I upgraded the VMware Tools of the FC9 64-bit guest.
It installed but had some kind of problem. After installing the VMware Tools that came with the latest version of VMware Workstation 6.5.3, yum and the 'software updater' were unable to upgrade, remove, and/or download RPM's.
I was using this guest OS with the latest vesion of VMware Workstation, v6.5.3. I downloaded the latest version of v6.5.3 today and I upgraded the VMware Tools of the FC9 64-bit guest.
It installed but had some kind of problem. After installing the VMware Tools that came with the latest version of VMware Workstation 6.5.3, yum and the 'software updater' were unable to upgrade, remove, and/or download RPM's.
Saturday, October 10, 2009
Unable to find a C or C++ NLG open source tool this week
So, I've been exploring the area of NLG, natural langugae generation. My personal goal was to develop an application that would read a corpus and respond with either a summary of the corpus, or a response to the categories found. In either case, I wanted the summary or response to not just be a template where the noun/verb/adjective/predicates were merely filled in. That's no better than using grep.
As of this week, I can only find API's written in Java, Python, Lisp, and Prolog. Many of the listed NLG API's or applications haven't been touched in years, or are no longer available. Much to my displeasure, nothing in C or C++. I want something that will run lean, mean, and can scale to datasets over a terabyte in size.
As of this week, I can only find API's written in Java, Python, Lisp, and Prolog. Many of the listed NLG API's or applications haven't been touched in years, or are no longer available. Much to my displeasure, nothing in C or C++. I want something that will run lean, mean, and can scale to datasets over a terabyte in size.
Tuesday, October 6, 2009
Natural Language Generation
While going over some nbc's, I stumbled across the AI area of NLP. But, while observing where the areas of nbc and NLP meet, I've found a new obsession: NLG. NLG is an acronym for natural language generation. Natural language generation is text created by a computer program that appears to be human-like in readability.
I first heard about this topic in detail in my AI class in grad school at University of San Francisco. My professor, Dr. Brooks, had mentioned that researchers had been trying for years to create programs that could generate narratives for computer games. I even recall seeing on some news aggregator that someone had successfully won a writing contest with a story written by a NLG system.
At the time I was taking my AI course, I remember working for a horrible boss. Who made all of us who he saw everyday and interacted with on a continuous basis, write weekly reports. I remember wanting to write a Perl or Python script that would do this for me. I made some attempts but it was hard to get any realistic variance. It was essentially an overglorified mad lib, where the program only filled in the blanks.
I was looking for something more natural and human like.
In NLG, one takes data and has generation rules that result in text that feels as if a human wrote it. Surprisingly, if one does a search on NLG, it is a relatively new area of research. Perhaps the best introduction to this topic is on Wikipedia. From the Wikipedia area, you will find yourself on the Bateman and Zock list of Natural Language Generators(http://www.fb10.uni-bremen.de/anglistik/langpro/NLG-table/NLG-table-root.htm)
At the moment, the state of the art appears to be based upon Java and Lisp languages. Since I work in embedded systems where speed and small footprint are key, I'm intersted in implementations that are in C and can scale. I've noticed that most of the NLP and NLG systems I found do not have a database backend. This surprises me since use of a database would allow for scaling and more consistant performacne as the dataset grows.
I think I'll be experimenting with NLG to see if I can make a program that will generate an email that asks a user for info based upon an email inquiry.
I first heard about this topic in detail in my AI class in grad school at University of San Francisco. My professor, Dr. Brooks, had mentioned that researchers had been trying for years to create programs that could generate narratives for computer games. I even recall seeing on some news aggregator that someone had successfully won a writing contest with a story written by a NLG system.
At the time I was taking my AI course, I remember working for a horrible boss. Who made all of us who he saw everyday and interacted with on a continuous basis, write weekly reports. I remember wanting to write a Perl or Python script that would do this for me. I made some attempts but it was hard to get any realistic variance. It was essentially an overglorified mad lib, where the program only filled in the blanks.
I was looking for something more natural and human like.
In NLG, one takes data and has generation rules that result in text that feels as if a human wrote it. Surprisingly, if one does a search on NLG, it is a relatively new area of research. Perhaps the best introduction to this topic is on Wikipedia. From the Wikipedia area, you will find yourself on the Bateman and Zock list of Natural Language Generators(http://www.fb10.uni-bremen.de/anglistik/langpro/NLG-table/NLG-table-root.htm)
At the moment, the state of the art appears to be based upon Java and Lisp languages. Since I work in embedded systems where speed and small footprint are key, I'm intersted in implementations that are in C and can scale. I've noticed that most of the NLP and NLG systems I found do not have a database backend. This surprises me since use of a database would allow for scaling and more consistant performacne as the dataset grows.
I think I'll be experimenting with NLG to see if I can make a program that will generate an email that asks a user for info based upon an email inquiry.
Friday, September 25, 2009
Grammars
The purpose of this entry is to describe the 4 type of grammars that can be used to classify a language, and the means used to classify a language as one of the four types of grammrs.
From a linguistics and NLP standpoint, languages can be classified by 4 possible grammar types. From the most expressive description to the least expressive description, a language can be described by a grammar known as type 0, type 1, type 2, or type 3. Each of the different grammars has a common name. A given grammar can sometimes describe other grammars. A type 0 grammar can describe type 1, type2, and type 3 grammars. A type 1 grammar can describe type 2 and type 3. A type 2 grammar can describe a type 3 grammar. A type 3 grammar cannot describe any other type of grammar.
For the four types of grammars, each are composed of rules known as productions, which have the general form of w1 -> w2 . Each production rule generates a sequence of terminal tokens and non-terminals. Non-terminals are production rules that go by the lhs symbol, w1 .
A recursively enumerable grammar is also known as a type 0 grammar. A type 0 grammar has no restrictions on its production rules. Context-sensitive grammar is a type 1 grammar. A type 1 grammar is restricted to productions where the number of symbols on the rhs is equal to or greater than the number of symbols on the lhs. Context-free grammar is a type 2 grammar. A non-terminal in a type 2 grammar can be replaced by its rhs. In comparison, a non-terminal in a type 1 grammar can only be replaced if there is a production that matches the symbols on the rhs with an equivalent lhs. A regular grammar is a type 3 grammar. A regular grammar is also known as a regular expression, which is used by Perl, Python, and grep when searching on strings. A production of a regular grammar has a restricted expression. The lhs is a non-terminal. The rhs is a terminal, which is optionally followed by a non-terminal.
Grammars are also more formally known as phrase structure grammars.
G = phrase structure grammar as a set
G = (V,T,S,P)
V is a vocabulary, a set of tokens and non-tokens(non-terminals)
T is a subset of V. T is the set of terminal tokens
S is a start symbol/token that is a member of V
P is a set of production rules
N is V - T, set of non-terminal symbols/tokens
Types of grammars and restrictions on their productions, w1 -> w2
0 no restrictions
1 length(w1) <= length(w2), w2=lambda
2 w1 = A, where A is non-terminal symbol
3 w1=A and w2=aB or w2=a, where A is an element of N, B is an element of N, and a is an element of T, or S->lambda
From a linguistics and NLP standpoint, languages can be classified by 4 possible grammar types. From the most expressive description to the least expressive description, a language can be described by a grammar known as type 0, type 1, type 2, or type 3. Each of the different grammars has a common name. A given grammar can sometimes describe other grammars. A type 0 grammar can describe type 1, type2, and type 3 grammars. A type 1 grammar can describe type 2 and type 3. A type 2 grammar can describe a type 3 grammar. A type 3 grammar cannot describe any other type of grammar.
For the four types of grammars, each are composed of rules known as productions, which have the general form of w1 -> w2 . Each production rule generates a sequence of terminal tokens and non-terminals. Non-terminals are production rules that go by the lhs symbol, w1 .
A recursively enumerable grammar is also known as a type 0 grammar. A type 0 grammar has no restrictions on its production rules. Context-sensitive grammar is a type 1 grammar. A type 1 grammar is restricted to productions where the number of symbols on the rhs is equal to or greater than the number of symbols on the lhs. Context-free grammar is a type 2 grammar. A non-terminal in a type 2 grammar can be replaced by its rhs. In comparison, a non-terminal in a type 1 grammar can only be replaced if there is a production that matches the symbols on the rhs with an equivalent lhs. A regular grammar is a type 3 grammar. A regular grammar is also known as a regular expression, which is used by Perl, Python, and grep when searching on strings. A production of a regular grammar has a restricted expression. The lhs is a non-terminal. The rhs is a terminal, which is optionally followed by a non-terminal.
Grammars are also more formally known as phrase structure grammars.
G = phrase structure grammar as a set
G = (V,T,S,P)
V is a vocabulary, a set of tokens and non-tokens(non-terminals)
T is a subset of V. T is the set of terminal tokens
S is a start symbol/token that is a member of V
P is a set of production rules
N is V - T, set of non-terminal symbols/tokens
Types of grammars and restrictions on their productions, w1 -> w2
0 no restrictions
1 length(w1) <= length(w2), w2=lambda
2 w1 = A, where A is non-terminal symbol
3 w1=A and w2=aB or w2=a, where A is an element of N, B is an element of N, and a is an element of T, or S->lambda
Sunday, September 20, 2009
Tracing the boot up sequence of TAEB part 2
This entry goes into detail of the top of the main loop of the taeb script, line 81-98.
taeb,lines 81-98 is the top-level of the taeb main loop. The main loop is composed of 2 main parts. The first item in the main loop is the actual operational statement. The later item, which is actually multiple statements, are only executed if taeb has been told via the command line option, --loop, to re-execute itself after it has completed playing a nethack session.
Let's review these 2 portions by first going over the later item, since it is only executed when specified via the command-line.
taeb, line88: only reinitialize/restart taeb if local variable $loop is not equal to 0. This will happen when --loop is specified via the command-line.
taeb, line90: reset all taeb variables and states
taeb, lines 92-96: Sleep for 5 seconds before starting a new nethack game
The eval statement, which is the first statement ecountered at the start of this loop, does all the work.
taeb, line 83: sets INT handler to print message to screen and prevent starting a new game by setting $loop to 0.
taeb, line 84: execute a taeb session
taeb, line 85: reports the results of a taeb session
taeb, line84, is TAEB->play;The method play is sent to the TAEB object, which is defined in TAEB.pm.
TAEB.pm, lines 742-749: Inside this loop, each iteration is a step. At the end of each step, results are store of the step. The last step of the taeb session will print its results to the screen.
Inside each step, the following methods are called in order:
redraw
display_topline
human_input
full_input
handle_XXXX called
redraw is invoked from TAEB::Display::Curses. redraw is used to repaint the entire nethack screen at the start of a step. display_topline is also invoked from TAEB::Display::Curses, too. display_topline displays any messages received from the last step in the current step. human_input is defined inside TAEB.pm. human_input is used to get keyboard input if ai allows human control and a key is pressed. Under normal operational circumstances, human_input will not capture anything.
full_input is a wraper method that is used to capture nethack screen data and load it into the taeb database. At the start of full_input's operation, the screen scraper is reset to take new info and the publisher is turned off. The publisher is resumed after scraping and processing of the scrape is finished. After the publisher is off, then next instruction performed is process_input, which reads any input from a previous action or user and sends it to the vt, virtual terminal. Afterwords, the screen is scraped and loaded into the Taeb database.
The next step performed is that dungeon and senses variables are updated. After the update of these items, the publisher is renabled. This completes the phase of a step where the percepts are captured.
taeb,lines 81-98 is the top-level of the taeb main loop. The main loop is composed of 2 main parts. The first item in the main loop is the actual operational statement. The later item, which is actually multiple statements, are only executed if taeb has been told via the command line option, --loop, to re-execute itself after it has completed playing a nethack session.
Let's review these 2 portions by first going over the later item, since it is only executed when specified via the command-line.
taeb, line88: only reinitialize/restart taeb if local variable $loop is not equal to 0. This will happen when --loop is specified via the command-line.
taeb, line90: reset all taeb variables and states
taeb, lines 92-96: Sleep for 5 seconds before starting a new nethack game
The eval statement, which is the first statement ecountered at the start of this loop, does all the work.
taeb, line 83: sets INT handler to print message to screen and prevent starting a new game by setting $loop to 0.
taeb, line 84: execute a taeb session
taeb, line 85: reports the results of a taeb session
taeb, line84, is TAEB->play;The method play is sent to the TAEB object, which is defined in TAEB.pm.
TAEB.pm, lines 742-749: Inside this loop, each iteration is a step. At the end of each step, results are store of the step. The last step of the taeb session will print its results to the screen.
Inside each step, the following methods are called in order:
redraw
display_topline
human_input
full_input
handle_XXXX called
redraw is invoked from TAEB::Display::Curses. redraw is used to repaint the entire nethack screen at the start of a step. display_topline is also invoked from TAEB::Display::Curses, too. display_topline displays any messages received from the last step in the current step. human_input is defined inside TAEB.pm. human_input is used to get keyboard input if ai allows human control and a key is pressed. Under normal operational circumstances, human_input will not capture anything.
full_input is a wraper method that is used to capture nethack screen data and load it into the taeb database. At the start of full_input's operation, the screen scraper is reset to take new info and the publisher is turned off. The publisher is resumed after scraping and processing of the scrape is finished. After the publisher is off, then next instruction performed is process_input, which reads any input from a previous action or user and sends it to the vt, virtual terminal. Afterwords, the screen is scraped and loaded into the Taeb database.
The next step performed is that dungeon and senses variables are updated. After the update of these items, the publisher is renabled. This completes the phase of a step where the percepts are captured.
Saturday, September 19, 2009
Tracing the boot up sequence of TAEB part 1
The purpose of this entry is to describe in plain talk how Taeb starts up and executes it 'main' loop. By understanding the 'main' loop of the taeb framework, this will enable creation of Taeb agents.
taeb, line1: enables text file to be interpreted as a Perl script
taeb, line2: no questionable Perl constructs allowed
taeb, line3: ? literally says to add to @INC the the library using the literal 'lib'
taeb, line4: Use Perl library Getopt::Long to process command-line options
taeb, lines 7-20: defintion of print_usage subroutine which shows the command-line options that can be used to configure Taeb operation
taeb, line22: local variable used to control whether or not taeb will just stop when it receives an interrupt or reset and begin a new execution. See while-loop at line 81.
taeb, line23: local list that stores command-line specified options for taeb. This local list is then transferred to Taeb's configureation. See lines 24, 28, 43.
taeb, line24: local hash that is initialzed to store the hard reference to the variable $loop and the list @config_overrides.
taeb, lines 25-39: Code used to alternate operation of Taeb via command-line options. Also, used to display the options that can be specified to Taeb.
taeb, line41: Specify that TAEB.pm must be used and found.
taeb, line43: Change Taeb configuration from specified command-line options
taeb, lines 45-47: Add to Taeb configruation that no ai should be used if command-line option specified.
taeb, lines 49-77: handlers assigned to signals TSTP, CONT, TERM, USR1, and USR2 signals.
taeb, line79: Flush after every write
taeb, lines 81-98: Top of the main loop of Taeb.
taeb, line1: enables text file to be interpreted as a Perl script
taeb, line2: no questionable Perl constructs allowed
taeb, line3: ? literally says to add to @INC the the library using the literal 'lib'
taeb, line4: Use Perl library Getopt::Long to process command-line options
taeb, lines 7-20: defintion of print_usage subroutine which shows the command-line options that can be used to configure Taeb operation
taeb, line22: local variable used to control whether or not taeb will just stop when it receives an interrupt or reset and begin a new execution. See while-loop at line 81.
taeb, line23: local list that stores command-line specified options for taeb. This local list is then transferred to Taeb's configureation. See lines 24, 28, 43.
taeb, line24: local hash that is initialzed to store the hard reference to the variable $loop and the list @config_overrides.
taeb, lines 25-39: Code used to alternate operation of Taeb via command-line options. Also, used to display the options that can be specified to Taeb.
taeb, line41: Specify that TAEB.pm must be used and found.
taeb, line43: Change Taeb configuration from specified command-line options
taeb, lines 45-47: Add to Taeb configruation that no ai should be used if command-line option specified.
taeb, lines 49-77: handlers assigned to signals TSTP, CONT, TERM, USR1, and USR2 signals.
taeb, line79: Flush after every write
taeb, lines 81-98: Top of the main loop of Taeb.
Saturday, September 12, 2009
Demo AI with TAEB and try_explore part 1
TAEB ships with an AI known as Demo. one can use it as a reference for creating your own AI with TAEB. At its most simplistic level, the creation of a TAEB AI invovles the following steps:
1. Create a Perl module that inherits from TAEB::AI
2. Create a method called next_action that returns a an object of type TAEB::Action
I will be describing how next_action in Demo moves around the the Nethack dungeon via next_action sending the try_explore method. In TAEB's Demo AI, one of the actions that it can execute is defined by the try_explore method. From the current position in the Nethack dungeon, TAEB will use try_explore to find the next best tile to reach amount it's 8 nearest neighbors.
try_explore itself is merely a wrapper. The work is done first_match, which takes as an argument a type of the destination tile. In this case, the destination tile type is 'unexplored'. Tile types are defined in lib/TAEB/Util.pm from lines 73-91. first_match is part of TAEB::World::Path package. The purpose of first_match is to identify the type of data structure that will be used to search for the next tile position. Typically, for the purposes to try_explore this will be undef. After determining the type of data structure for searching, first_match calls _dijskstra, which is an implementation of the Dijkstra path finding algorithm.
1. Create a Perl module that inherits from TAEB::AI
2. Create a method called next_action that returns a an object of type TAEB::Action
I will be describing how next_action in Demo moves around the the Nethack dungeon via next_action sending the try_explore method. In TAEB's Demo AI, one of the actions that it can execute is defined by the try_explore method. From the current position in the Nethack dungeon, TAEB will use try_explore to find the next best tile to reach amount it's 8 nearest neighbors.
try_explore itself is merely a wrapper. The work is done first_match, which takes as an argument a type of the destination tile. In this case, the destination tile type is 'unexplored'. Tile types are defined in lib/TAEB/Util.pm from lines 73-91. first_match is part of TAEB::World::Path package. The purpose of first_match is to identify the type of data structure that will be used to search for the next tile position. Typically, for the purposes to try_explore this will be undef. After determining the type of data structure for searching, first_match calls _dijskstra, which is an implementation of the Dijkstra path finding algorithm.
Saturday, September 5, 2009
Alternate means of running a Taeb AI agent
The easiest way to use an AI agent other than Demo in Taeb is to install the new agent into your Taeb installation. If you do this, then you only need to have a config.yml in your .taeb directory that specifies this new agent.
But, if for some reason, you don't want the agent's source code to be installed into your main installation, there is another way. As before, you will still need a config.yml in your .taeb file. If you have followed the software conventions for Taeb agents, cd into your agent's lib directory;The lib directory only contains the directory 'TAEB'. Inside that directory, lib, which is considered the 'top' of your agent's code, run 'taeb'. This will grab the agent defined under 'taeb' as the agent to run.
One can get the same results if one sets the full path of PERL5LIB to the 'lib' directory of your agent. This method has the advantage that only a config.yml is needed. No need to run taeb from the specific lib directory of your agent.
But, if for some reason, you don't want the agent's source code to be installed into your main installation, there is another way. As before, you will still need a config.yml in your .taeb file. If you have followed the software conventions for Taeb agents, cd into your agent's lib directory;The lib directory only contains the directory 'TAEB'. Inside that directory, lib, which is considered the 'top' of your agent's code, run 'taeb'. This will grab the agent defined under 'taeb' as the agent to run.
One can get the same results if one sets the full path of PERL5LIB to the 'lib' directory of your agent. This method has the advantage that only a config.yml is needed. No need to run taeb from the specific lib directory of your agent.
Friday, September 4, 2009
TAEB keyboard commands
The keyboard commands that can be used to interact with a TAEB-based agent are defined in TAEB/lib/TAEB.pm
p - pause agent
d - change draw mode
i - show inventory
\cP - show old message
\cX - Senses
e - equipment menu
I - item spoiler data
M - monster spoiler data
\e - user input
r - refresh screen
\cr - refresh screen
q - save and exit
Q - controlled quit and exit
p - pause agent
d - change draw mode
i - show inventory
\cP - show old message
\cX - Senses
e - equipment menu
I - item spoiler data
M - monster spoiler data
\e - user input
r - refresh screen
\cr - refresh screen
q - save and exit
Q - controlled quit and exit
Subscribe to:
Posts (Atom)