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

  1. 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.
  2. 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.

  1. 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:
    1. Digits 1 and 7
    2. Digits 4 and 9
    3. All the digits
    4. EXTRA CREDIT: Show some of the digits on the maps, as in the Tenenbaum's paper.
  2. Construct the 2-D Isomap model using tangent-distance. Show the same clusters as above.
  3. 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:

    1. Roll number
    2. Date of birth in DD - MM - YYYY format
    3. The time when they are writing in HHMM in 24-hr format (so 3:30 pm is 1530)
    4. 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

  1. 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.

  2. MNIST Database: Download the gz files and unzip them into './data' in your working directory.
  3. 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.

  1. 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

  2. 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.

  3. 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.

         

  4. 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

  1. [nao200.zip] (200 images, 1Mpix each)
  2. [2arms-random.rar] (500 images) 800x800   [2arms-random-angles.txt]
  3. [2arms-box-horiz.rar] (200 images) 800x800   [2arms-box-horiz-angles.txt]
  4. 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)