Assignment 2: Reducing the Parameters of the World
This homework is to be done in groups of two. Each member of each group must
attempt at least one problem from part A and one problem from part B. Each
group will submit a SINGLE HTML page
hw2/index.html
, which may
link to different user areas under each userid.
In this work, you will explore the processes by which an agent, encountering
the world repeatedly with its sensors and actuators, may create a
"representation"- i.e. a model of an environment and a "decision space" in
which it can search.
For example, for the continuum world agent C, the environment was the grid
(partially known), and the decision space was either to SUCK, or to move UP,
DOWN, LEFT, or RIGHT. But how did it arrive at this representation?
Another important issue is whether the representation is the best one to use.
In fact, is there only one representation, or should there be differing
representations for different types of tasks? In humans, clearly,
representations for the same environment are different for differing tasks,
and this may make for considerable efficiency.
So, how should an AI agent determine its representation based on its task
experience? Is there some representation that is "natural" for a given
domain + objective?
Human specified representations are often not very easy to achieve for the
machine. For example, in the continuum world agent subproblem E we saw that the
robot would have a lot of difficulty constructing a cartesian grid space from
its sensory input.
We will consider dimensionality reduction techniques for discovering
representations in two different domains, one involving constructing models
for written numerals, and the other for robot motions. Both of these will
be based on the Isomap algorithm.
Resources for Isomap
-
Information on the algorithm:
Joshua B. Tenenbaum and Vin de Silva and John C. Langford,
A Global Geometric Framework for Nonlinear Dimensionality Reduction
, Science, v. 290, pp. 2319--2323, 2001.
-
You may wish to use the widely used Matlab implementation of
Isomap by Tenenbaum et al.
You will need just two files from this package:
Isomap.m and L2_distance.m,
and you can ignore the other files. See the Readme page
to understand how to use these files.
However, you may also use any C or Java code. If you adapt code from others, please give the link in your webpage.
Submission
As mentioned above, each group will need to create a SINGLE webpage
hw2/index.html
, and BOTH persons' areas should link to the same page.
The links should work from each area. In this file, you need to write your
answers for all parts A1-A3 and B1-B4, and give links to resources (code etc)
as appropriate for each part.
Note that A3 and B3 are non-implementational. The others involve discovering
the non-linear dimensionality in different datasets using Isomap.
Evaluation: If you do everything stated in the assignment, you get 80%
marks. The other 20% is reserved for particularly excellent
explorations of any of the questions.
Due date: Thursday 26 Jan, 9:00 PM.
A. Hand-written Numerals: MNIST Database
Some 4's and 9's from the MNIST database.
(Click the images to expand.)
In this work, we consider how an imaging system may construct models for
handwritten numerals. We will use 2000 images from the MNIST database, each
of size 28x28 pixels. The images have labels indicating which digit it is.
You will now consider whether these images lie along some lower dimensional
manifold in the 784-dimensional image space. The objective of this exercise
is to learn the importance of a distance metric; we shall be considering both
the plain euclidean distance, and the tangent distance metric.
-
Construct the 2-D Isomap model for the first 2000 samples of the MNIST
training set using Euclidean distance. Show the clusters of the following
groups:
- Digits 1 and 7
- Digits 4 and 9
- All the digits
- EXTRA CREDIT: Show some of the digits on the maps, as in the Tenenbaum's paper.
-
Construct the 2-D Isomap model using tangent-distance. Show the same
clusters as above.
-
HINDI NUMERAL DATA COLLECTION
Have 20 (or more) of your Hindi speaking friends, write the
following information along a line on a single sheet of paper:
- Roll number
- Date of birth in DD - MM - YYYY format
- The time when they are writing in HHMM in 24-hr format (so 3:30 pm is 1530)
- The value of pi to ten decimals.
Please scan each page using a high-quality scanner and submit both the
hand-writing page and the scanned copy as an image. Some of you may
wish to use this data in a possible project in this course.
Please take 3 print outs of this PDF file on 3
different A4 sheets horizontally. Please use clean sheets of paper and DO NOT use both the
sides - use just one side of each paper. If you want to collect more data, you can print and use more sheets.
The deadline for this task is 1st Feb (Wednesday). You will have to submit the sheets
in the class on that day. You also need to upload the scanned copies of these sheets before the
class.
Resources
-
Source code in C [td.c] for computing tangent-distance.
You will NOT have to use this file directly. Once it has been compiled using mex,
you can use this Matlab code [tangent_d.m] to invoke it.
The td.c file is a modified version of Daniel Keysers'
tangent distance implementation to allow it to be invoked from Matlab.
In case you want to implement the whole work in C, you can use the original
pure C implementation by
Daniel Keysers.
-
MNIST Database: Download the gz files and unzip them into
'./data'
in your working directory.
-
Matlab code [loadDigits.m] to read the digit
data from the MNIST database. See the comments at the beginning of the code for
details on how to use this file. Digits in the MNIST are randomly distributed.
So it is just sufficient to read the first 2000 samples using loadDigits.m.
B. Discovering Robot Motion DOFs
In part B of this homework, you are to take a set of high-dimensional robot
images and discover the underlying regularity, if any.
-
In this set of 200 images [nao200.zip in Resources below], you see a humanoid robot, the
Aldebaran Nao, moving its left arm. Take these images and apply Isomap
on these. Report the most likely dimensionality of the manifold embedded
in these high-dimensional images, as you observe it from the residual
error curve. Explain the dimensionality that you observe.
Images 001, 075, 130 and 200
|
|
|
|
-
Consider two robotic agents, each with two arms. Both arms have two
links that move on a single plane. So, together they occupy a 4-DOF
space: theta1, theta2 for the arm on the left, and theta3, theta4 for the
arm on the right. Each link of each arm is of length L units, and their
centers are apart by D units.
Now consider the entire set of images in [2arms-random in Resources below].
Apply Isomap on this data and report the most likely dimensionality of the
data as you observe it from the residual error curve. Explain the dimensionality
you observe.
-
Consider the robots with L=15 and base distance D=20. Now suppose the
two arms of the above robot are working together to hold
a box of dimension 5x5. Two robots can hold the box horizontally along its
midline. Assume the links are pure lines (no thickness), consider
the box whose center is at a location (5,12) w.r.t. the base of the arm
on the left.
Solve for theta1,theta2 and theta3,theta4 so that the two arm tips are
holding the box along its horizontal midline. Submit a diagram showing
the arm and the angles theta1 to theta4, and check your answers using a
protractor.
-
Consider now the set of images in which the two-arms are working together
to move a box horizontally [2arms-box-horiz in Resources below]. Apply
Isomap and report the best dimensionality of the resulting data. Compare with your answer
in B2 and explain your result.
Resources
-
[nao200.zip] (200 images, 1Mpix each)
-
[2arms-random.rar] (500 images) 800x800
[2arms-random-angles.txt]
-
[2arms-box-horiz.rar] (200 images) 800x800
[2arms-box-horiz-angles.txt]
-
Matlab code [loadImageData.m] to load these images;
this is similar to loadDigits.m. Please see the comments at the beginning of the file
to understand how to use it.
Homework 2 Groups
Roll No Name Dept User ID
--------------------------------------------------------
Y9086 ANIRUDDH VYAS CSE vyasani
10807 VINIT KATARIA CSE vinitk
Y9094 ANKIT BHUTANI EE ankitbhu
10705 SHUBHDEEP KOCHHAR CSE shubkoch
Y9113 ANUJA RANJAN CSE anuja
10682 SHIKHAR SHARMA CSE shikhars
Y9156 AVINASH PREM K KOYYA CSE avinashk
10598 RISHABH NIGAM CSE rishabhn
Y9195 DESAI ADITYA PRADIP CSE adityapd
10555 RAHUL ARORA CSE arorar
Y9197 DEVVARAT MEENA CSE devvarat
10551 RABI SHANKER GUHA CSE rabisg
Y9201 DIPENDRA KUMAR MISRA CSE dkmisra
10511 PRANJAL SINGH CSE spranjal
Y9203 DIWAKAR CHAUHAN CSE diwakarc
10498 PRABHAT PANDEY CSE prabhatp
Y9209 ERA JAIN CSE eraj
10479 PANKAJ P KEWALRAMANI CSE pratikkr
Y9215 GAURAV ARYA CSE aryag
Y9224 GAURAV KRISHNA CSE gkrishna
10415 MRIDUL VERMA CSE mridulv
Y9259 JAYANT SHARMA CSE jaysha
10404 MOHD DAWOOD CSE mdawood
Y9271 KANISH MANUJA CSE kanish
10379 MANAV GARG CSE mgarg
Y9288 KRITIKA SINGH CSE skritika
10351 KHUSHDEEP SINGH SANDHU CSE khushd
Y9345 MONIT KANWAT CSE monit
10346 KAUSTUBH TAPI CSE ktapi
Y9350 MUKUL SINGH CSE smukul
10314 JEETESH MANGWANI CSE jeeteshm
Y9385 NITESH VIJAYVARGIYA CSE nvijay
10290 HARSHIT MAHESHWARI CSE harshitm
Y9399 PANKAJ JINDAL CSE pankajj
10259 GANGAPRASAD KOTURWAR CSE koturwar
10002 AAKASH VERMA CSE aakashv
10250 DIVYANSHU BHARTIYA CSE divbhar
Y9418 PRAKHAR BANGA CSE prakban
10222 DEEPAK PATHAK CSE deepakp
Y9468 RAJESH DHANIA CSE rjdhania
10169 ATIQUE FIROZ CSE atiquef
Y9488 ROHAN JINGAR CSE rohanj
10161 ASHU GUPTA CSE ashug
Y9496 ROMIL GADIA CSE romilg
10133 ANURAG GAUTAM CSE ganurag
Y9518 SARANSH SRIVASTAVA CSE saranshs
10092 ANIRUDDHA KUMAR SAHU CSE anirkus
Y9545 SHASHANK SONKAR CSE ssonkar
10060 AKSHAY KUMAR CSE kakshay
Y9615 SUTANU GAYEN CSE sutanug
10050 AKARSHAN SARKAR CSE aksarkar
Y9645 VEMPATI ANURAG SAI EE vanurag
10039 ADITI KRISHN CSE aditik
Y9651 VIMAL SHARMA CSE svimal
10007 ABHIJIT SHARANG CSE abhisg
Y9654 VINEET HINGORANI CSE viner
10466 NITTALA V SUBBA RAO CSE subbarao
Page was created by Sadbodh Sharma, M S Ram and Amit Mukerjee (Jan 19 2012)