Wednesday, May 23, 2018

Real-time Clustering

Clustering algorithms can be conceptualized as a technique for reducing input data in a high-dimensional space into a lower-dimensional space. From the viewpoint of robot programming, clustering is useful for transforming sensor data with a wide range into a small number of categories, each of which can be associated with a suitable action.

In my research over the last several years, I have explored numerous variations of this approach. I have experimented with several different clustering algorithms as well as several different techniques for action selection. The goal of this research agenda is to make it easier to program a robot to exhibit a desired behavior given complex sensor inputs.

My first work in this area was to apply clustering as a technique for enabling sonar values to be used as state indices for a robot employing the popular reinforcement learning algorithm Q-Learning. In the research I did on this subject, I employed the Kohonen Self-Organizing Map (SOM) as the clustering algorithm that performed that transformation.

Part of the appeal of the SOM was its ability to learn and adapt the clusters on every cycle as new sonar data arrived. I became intrigued by the possible applicability of this idea to images. To that end, I stopped investigating the Q-Learning context and pursued the idea of enabling a user to directly specify actions for each cluster. I employed the Growing Neural Gas algorithm in that work, as I was intrigued by its potential to adaptively determine an appropriate number of clusters. I followed up by replacing the manual action-selection GUI I built with an imitation learner.

In continuing to work with GNG, I became frustrated with its large number of hyperparameters. I found it tedious and frustrating to try to figure out appropriate values. Furthermore, although I had initially been intrigued by its flexibility in terms of the total number of clusters, I was starting to find this to be a liability. With a variable number of clusters, the cycle time becomes unpredictable. I concluded it was preferable to be able to bound the cycle time based on knowing ahead of time the total number of clusters.

To address these concerns, I invented my own clustering algorithm, Bounded Self-Organizing Clusters (BSOC), and benchmarked its performance against the SOM. The key ideas of BSOC are as follows:

  • There is a fixed number of clusters. 
    • This is the only hyperparameter.
  • Each input is added to the set of clusters as it arrives.
    • If the maximum number of clusters is exceeded, the two clusters closest to each other according to the distance metric are merged. 
    • Both the distance and the merge are weighted by the number of "ancestors" that the clusters have.
My student Eric Huynh and I then employed BSOC to implement an imitation learner, which we assessed with a large number of volunteers.

Motivated by the need to get a better understanding of the dynamics of the BSOC clustering process, I decided to benchmark it against the well-known k-means clustering algorithm. To simplify the analysis, instead of the complete image clustering I had been doing in previous work, I focused instead on the problem of color quantization. I created two videos with my Android phone as test cases for the benchmarking process. As the phone's resolution is 1920x1080, clustering every pixel over 10 frames of video (spaced 4.5 seconds apart) results in over 20 million values to cluster. That proved to be about as much as my k-means implementation could handle before running out of heap space. (Maybe Java wasn't the best language in which to program this.)

Wanting to process more frames, I concluded I needed another benchmark algorithm. I quickly implemented an algorithm I called Random Incremental Clustering (RIC). The concept is very simple:

  • Specify a maximum number of clusters k.
  • Initialize the number of attempts a to zero.
  • As each new input arrives:
    • Increase a by one. 
    • If fewer than the maximum number of clusters is in place, add it to the clusters.
    • Otherwise, with probability k/a, replace at random one of the existing clusters with the newly received input.
As the number of inputs received increases, it becomes increasingly rare for a new input to replace one of the veteran cluster centers. But it still happens occasionally. This has the effect of creating a uniform statistical sample of the inputs.

Creating this algorithm enabled me to benchmark BSOC with close to 200 million pixel inputs. The surprising result was that as the number of clusters increased to 8, the performance of RIC began to closely approximate both BSOC and k-means. (With 2 clusters, RIC performed very poorly.)

I would not want to conclude too much from this result as of yet. This convergence of performance occurred with an extremely large number of inputs for the very simple RGB representation of a pixel's color. This result might not hold when clustering entire images, as I had been doing in prior work. The result might also improve with an approach to randomized clustering that does non-uniform sampling.

I am looking forward to the next stages of this research project, in which I plan to explore further the questions that arose from this latest study. I continue to be fascinated by the possibilities that real-time clustering enables, and I plan to investigate both the techniques for clustering and its applications. If anyone reading this is interested in collaborating or comparing results, definitely let me know!

Here is a summary of the papers and posters I have written on the topic of this post:
  • Gabriel J. Ferrer. "Performance Evaluation of a Real-Time Clustering Algorithm." In FLAIRS-31 (Melbourne, FL, May 21-23, 2018) (Poster PDF)
  • Gabriel J. Ferrer and Eric Huynh. "Real-Time Imitation Learning of Visual Behavior by a Mobile Robot." In Proceedings of the Thirtieth International Florida Artificial Intelligence Research Society Conference (Marco Island, FL, May 22-24, 2017) (PDF, implementation)
  • Gabriel J. Ferrer. "Real-Time Unsupervised Clustering." In 27th Modern Artificial Intelligence and Cognitive Science Conference (MAICS-2016) (Dayton, OH, April 22-23, 2016) (PDF, implementation)
  • Gabriel J. Ferrer. “Towards Human-Induced Vision-Guided Robot Behavior.” In Proceedings of the 2014 AAAI Fall Symposium: Knowledge, Skill, and Behavior Transfer in Autonomous Robots (Arlington, VA, November 13-15, 2014). (PDF)
  • Gabriel J. Ferrer, "Creating Visual Reactive Robot Behaviors Using Growing Neural Gas," 25th Modern Artificial Intelligence and Cognitive Science Conference (MAICS2014) (Spokane, WA, April 26, 2014) (PDF)
  • Gabriel J. Ferrer, "Encoding Robotic Sensor States for Q-Learning Using the Self-Organizing Map," Journal of Computing Sciences in Colleges 25:5 (May 2010) 133-139. (PDF)

Tuesday, March 13, 2018

Loading image files in JavaFX

Loading image files into JavaFX applications is not too difficult, but there is a lot of confusing and contradictory advice out there. Even worse, SceneBuilder encodes the files in a manner that is incompatible with how they will be loaded in the Java code. So I would recommend making direct references in the Controller to the files that one is loading.

Image files are easy to load if you place them in the same package as your code. Given that, an example like the following will do the trick:

import javafx.fxml.FXML;
import javafx.scene.image.Image;
import javafx.scene.image.ImageView;
import javafx.scene.layout.Pane;

public class Controller {
 
 @FXML
 private Pane pane;
 
 private ImageView img;

 @FXML
 void initialize() {
  img = new ImageView(new Image(Controller.class.getResourceAsStream("Screen.png")));
  pane.getChildren().add(img);
 }
}

Handling Key Events in JavaFX

Handling keyboard events is typically a tricky issue in any GUI environment, because it is not always clear which component is supposed to receive those events. This is typically handled by the concept of focus. That is, a component with the focus is the component that receives those events.

I have put together a short example as to how to make this work well in JavaFX. In this example, when the mouse hovers over a component, that component receives the focus. It retains the focus until another component requests it.

The two Circle objects change their color when they have the focus and an appropriate key is pressed. The Pane responds to keystrokes by printing them out on the console.

Although it is not part of this example, it is worth mentioning that clicking on a TextField or TextArea will always give that component the focus.

The below example is a Controller. I leave the main() and FXML file as exercises for the reader.


import javafx.fxml.FXML;
import javafx.scene.input.KeyCode;
import javafx.scene.input.KeyEvent;
import javafx.scene.layout.Pane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Circle;

public class Controller {
 
  @FXML
  Pane pane;

  @FXML
  Circle one;
 
  @FXML
  Circle two;
 
  @FXML
  void initialize() {
    one.setOnMouseEntered(event -> one.requestFocus());
    two.setOnMouseEntered(event -> two.requestFocus());
  
    one.setOnKeyPressed(event -> decodeColor(event, one));
    two.setOnKeyPressed(event -> decodeColor(event, two));

    pane.setOnMouseEntered(event -> pane.requestFocus());
    pane.setOnKeyPressed(event -> System.out.println("typed " + event.getText()));
  }
 
  void decodeColor(KeyEvent key, Circle obj) {
    if (key.getCode() == KeyCode.R) {
      obj.setFill(Color.RED);
    }
    if (key.getCode() == KeyCode.B) {
      obj.setFill(Color.BLUE);
    }
    if (key.getCode() == KeyCode.G) {
      obj.setFill(Color.GREEN);
    }
  }
}


Tuesday, February 20, 2018

The JavaFX canvas and mouse clicks

The Canvas class in JavaFX is a very flexible platform for drawing whatever one would like. It is not that difficult to use, but there are a few elements that are a bit confusing.

To take advantage of this example, start by creating an FXML file containing a Canvas and a Button. Then connect it to the CanvasDemoController class below:

package canvas;

import javafx.fxml.FXML;
import javafx.scene.canvas.Canvas;

public class CanvasDemoController {
  @FXML
  Canvas canvas;
 
  @FXML
  void move() {
    d.move(10, 10);
    refresh();
  }
 
  void refresh() {
    canvas.getGraphicsContext2D()
          .clearRect(0, 0, canvas.getWidth(), canvas.getHeight());
    d.draw(canvas);
  }
 
  Drawing d = new Drawing();
 
  @FXML
  void initialize() {
    canvas.setOnMouseClicked(event -> {
      d.teleport(event.getX(), event.getY());
      refresh();
    });
  }
}

The class above references the Drawing class, shown below:

package canvas;

import javafx.scene.canvas.Canvas;

public class Drawing {
  private double x, y, radius;
 
  public Drawing() {
    x = y = 0.0;
    radius = 10.0;
  }
 
  public void move(double dx, double dy) {
    x += dx;
    y += dy;
  }
 
  public void teleport(double x, double y) {
    this.x = x;
    this.y = y;
  }
 
  public void draw(Canvas canvas) {
    canvas.getGraphicsContext2D()
          .fillOval(x - radius, y - radius, radius*2, radius*2);
  }
}


The combined example illustrates several useful ideas:
  • Creating graphics on a Canvas is not that difficult, but the Graphics2DContext object must be acquired from it in order to draw anything. 
  • Drawings on a Canvas persist until erased. Erase and redraw as necessary to animate.
  • Mouse click events are pretty easy to handle, as the coordinates of the mouse click are easily obtained from the event parameter. However, we need to code the event handler explicitly in the controller class.

Thursday, February 1, 2018

JavaFX and TableView

The TableView control in JavaFX is a flexible and powerful interface. Every TableView object is parameterized by a data type that represents a row of the table. The documentation encourages developers to create row objects that represent each column using ObservableValue types. Following the documentation, it is necessary to create three methods (a setter and two different getters) for each of these values.

I find this approach exceedingly verbose, and in this blog post I will demonstrate an alternative that is hinted at in the documentation. I will assume that the reader is comfortable creating a JavaFX interface using SceneBuilder. I will just present the controller to which the FXML file can be attached.

This is a simple application that lets the user enter names and ages, which are then displayed in the table. The table is not editable. First, we define a data type for the table rows:

public class NameAgeRow {
  private String name;
  private int age;
 
  public NameAgeRow(String name, int age) {
    this.name = name;
    this.age = age;
  }
 
  public NameAgeRow(String name, String age) {
    this(name, Integer.parseInt(age));
  }
 
  public String getName() {return name;}
  public int getAge() {return age;}
}

Next, we define the Controller for the application:

import javafx.beans.property.SimpleIntegerProperty;
import javafx.beans.property.SimpleStringProperty;
import javafx.fxml.FXML;
import javafx.scene.control.Button;
import javafx.scene.control.TableColumn;
import javafx.scene.control.TableView;
import javafx.scene.control.TextField;

public class Controller {
  @FXML
  TableView<NameAgeRow> table;
  @FXML
  TableColumn<NameAgeRow,String> names;
  @FXML
  TableColumn<NameAgeRow,Integer> ages;
 
  @FXML
  TextField name;
  @FXML
  TextField age;
  @FXML
  Button add;
 
  @FXML
  void initialize() {
    add.setOnAction(e -> {
      table.getItems().add(new NameAgeRow(name.getText(), 
                                          age.getText()));
      name.setText("");
      age.setText("");
    });
  
    names.setCellValueFactory(cdf -> 
      new SimpleStringProperty(cdf.getValue().getName()));
    ages.setCellValueFactory(cdf -> 
      new SimpleIntegerProperty(cdf.getValue().getAge()).asObject());
  }
}

The overall structure is straightforward. For each column, we define a lambda that obtains the value from the NameAgeRow object for the current table row. A real convenience of this approach is that it can be made to work with any user-defined class that represents the row data. I find this more convenient and flexible than what is described in the documentation.

Sunday, December 31, 2017

On Academic Integrity and Being a Good Person


I recently had a conversation with a person who teaches 8th-grade English. She related to me an incident in which she discovered that a student had plagiarized an essay. After confronting (and penalizing) the student for the offense, she asked the student if she had learned anything. The reply was, "I learned that I should not plagiarize in your class." Upon discerning that her teacher did not find her reply to be satisfactory, she added, "Do you think this makes me a bad person?"

As an educator concerned with the integrity of the educational process, it seems easy to say "yes", because honesty is "good" and cheating is "bad". But if cheating makes a student successful at the cost of acquiring an unwanted label of "bad", then what is the real cost? In fact, an excuse for cheating I have heard before from a guilty party is "everyone else is doing it, so I have to cheat to keep up."

Given this mindset, I propose that any argument against cheating intended to persuade a perpetrator to stop has to demonstrate direct damage to the cheating student. 

Implicit in the act of submitting a solution to an assignment is to claim that the submitter created the solution in accordance with the instructions. Students cheat when it is easier to submit someone else's solution to an assignment than it is to create their own solution. To cheat, then, is to lie. 

What makes this lie so pernicious? When I, as an educator, create an assignment, I design the assignment so that correct solutions demonstrate that the student has acquired an ability. When a student cheats, the student falsely claims to have acquired that ability.

Any reflective person is aware of the power of habitual behavior. When we repeatedly select an action in response to a condition, the selection of that action becomes an unconscious response. One need only reflect on how quickly we respond to boredom by reaching for our smartphones to visualize the truth of this claim.

A student who cheats one time without being caught has already begun the process of forming the habit of cheating. The habit of cheating is equivalent to the habit of falsely claiming abilities. So what does it mean to have acquired this habit?

It means that, down the line, one's school transcript, in which grades correspond to false claims about acquired abilities, based on that transcript one can be hired for jobs for which one is not actually qualified. Such a job may be appealing for a good salary, but they will have hired a person who can't actually do the work. And the truth has a way of catching up with us, in time. An employer who hires someone who can't do the work will eventually figure this out and fire the person. Why will they figure it out? Nobody likes wasting money.

So, does cheating make a student a "bad person"? Yes. To be more precise, cheating makes a student a person with a habit that damages both the student and everyone around the student, as a result of claiming abilities that are not consistent with reality. 

But it is important to emphasize that a growth mindset applies to our moral habits just as much as it does to our abilities. If we have acquired bad moral habits (and most of us have), we have the freedom to choose actions that help us alter our habits, to transform the bad habits into good habits. So I would hate to close this essay without emphasizing the fact that the only thing stopping a person with bad habits from becoming a person with good habits is that the person with good habits has made a concrete decision to change for the better.

Another implication of this argument is that educators can do tremendous good for students who cheat by catching and punishing them as early as possible. This gives the student a chance to break the bad habit of cheating before it becomes too ingrained. It is a false mercy to go easy on a cheating student! 

Tractability and learning programming


My oldest son, currently in 3rd grade, is enthusiastically learning programming from Code.org. He has completed Courses 2 and 3 and is currently working on Course 4.

I was having a conversation with my colleague Brent Yorgey about the sudden increase in difficulty in the introductory CS class when we get to while loops. We spent some time discussing the fact that there is no getting around it being hard. He then pointed out that this is the concept that causes the difficulty of algorithm analysis to transition from completely tractable to undecidable. 

Interestingly, so far in Code.org every problem my son has had to solve has been in the logically-tractable category.

Related to this, I saw this interesting answer by Barry Roundtree to a question on Quora about what it takes to become a programmer:
In my experience, good programmers don’t bother asking if they can do something or not, and they don’t spend a lot of thought on whether or not they’re wasting time.
There are a lot of professions out there where learning skill x is expected to take yhours and lead to salary z. Music, math and chess are not those kind of professions, and programming is more like those than dentistry, auto body repair or being a CPA.
As to brain wiring: if you have an unusually high level of curiosity and (for tasks that interest you) an exceptional capacity to tolerate failure, you’re good to go. Curious people don’t tend to be overly concerned with wasting time, and people who tolerate failure well don’t spent a lot of effort wondering if they can do something. They just start, and if they fail (and fail repeatedly), no big deal.
It seems, then, that succeeding in programming is about having the right attitude. This attitude of curiosity and willingness to fail enable us to persevere in finding heuristic solutions forward even to logically intractable problems. 

Interestingly, many useful applications (e.g. spreadsheets, computer animation software) all enable users to do things that once required programming in the full sense. What they represent are domain-specific languages with a tractable logic. This enables them to be used by a wide audience of non-programmers.