TREND HIGHLIGHTING

A method for generating hints for math problems is provided. In response to a request for a hint from a student in a unit of instruction with a scatter plot, shapes are generated based on points in the scatter plot. A convex hull is generated based on the generated shapes.

DETAILED DESCRIPTION

General Overview

In an embodiment, a set of points is provided. For example, a graph may be provided to a student via an intelligent tutor computer program such as a cognitive tutoring system. The points on the graph may be a scatter plot, and the student may be required to identify the best fit line that identifies the trend associated with the points.

In an embodiment, a computer application such as a cognitive tutor application may detect the need to highlight a set of points on a graph, such as those in the scatter plot described earlier. Hints may be triggered when the student answers a question incorrectly. In addition, students may ask for hints.

In an embodiment, the student does not know what to do with the scatter plot, and needs a hint to help him determine where to draw the best-fit line. One way to give the student a hint without giving the answer away is to draw a convex hull around the dots and suggest that the student bisect the circle. The convex hull of a set of points or shapes is the smallest convex set (a set that doesn't curve inwards or have any dents) containing those points or shapes. This is a good approximation for a best-fit line. If the student does not understand what to do after the hint, the best fit line may then be drawn for the student.

Although the line drawn by the student may not be exactly correct, a reasonable variation may be acceptable. The goal of a best fit line is to minimize the least squares error. This means that the sum of the vertical distances between the line and the points should be minimized as much as possible. In order to provide for a reasonable opportunity for the student to get the answer correct, this sum may be multiplied by a variability metric such as 150%.

This can be used for describing scatter plots in general. In addition, this technique well when used with linear data. Techniques described herein may also be used for scatter plots that have other trends, such as parabolic structures. This method can be used to identify patterns by drawing a convex hull around multiple smaller groups of points.

In an embodiment, given a set of points, circles are drawn around those points to create a more useful convex hull. While a convex hull may be drawn in an traditional manner (based on the points alone), such a structure would look rigid and would not draw as much attention to the trend as it would to the points on the outside of the convex hull.

In an embodiment, circles are generated from points and then a convex hull algorithm is applied. In an embodiment, the size of the circles may vary based on distance from other circles, the number of circles in a particular area of the graph, or other metrics. In an embodiment, the size of the circles are the same, and are determined as a function of the average distance between the points.

In an embodiment, given a set of points, a good size for circles associated with the points is determined. Using a convex hull algorithm, lines are drawn around the outside circles. If the circles are the wrong size, they are not useful. Circles that are too big are not representative of a trend, and circles that are too small are too chunky to show a trend.

In the example shown inFIG. 1, the student positions the line of best fit (blue line) by dragging the blue squares (i.e., the point controls) until the line approximates the trend of the black dots. In this picture, the line would be accepted as a correct answer.

FIG. 2shows the plot shown inFIG. 1, but the convex hull has been added. In addition, the actual line of best fit shown in yellow. The convex hull appears when the student requests the second level of the hint sequence:

This method could be used to give a sense of the trend of a data set in other applications. Note that this process is completely geometric, and isn't strongly tied to the statistical properties of the set of points. However, points that are generated linearly with low variance tend to create long, cigar-like shapes while sets that are not linear tend to create rounder, more circular shapes. These later ones don't have a clear directionality to them.

Convex Hull

A convex set is a set that doesn't curve inwards or have any dents. For any two points in the set, every point on the line segment between them will also be in the set. For example, a convex set contains a line segment for any two points in the set:

The convex hull of a set of points or shapes is the smallest convex set containing those points or shapes.

The convex hull of a finite set of points is a polygon with vertices as those points. This representation is ugly and distracting. To work around this, a circle is drawn around each point and the convex hull is calculated around those circles. Each circle is like a peg in a board; the convex hull is the result of stretching a rope or rubber band around the pegs. In an embodiment, the radius of each circle may be a multiple (e.g., 0.4) of the average distance between the points, but said radius could be calculated some other way. There is no reason that they all have to be the same radius, but some method is used to determine a radius for each circle in an embodiment. To calculate the convex hull of those circles, a modified version of the algorithm described in Devillers's and Golin's “Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas” may be used. Their algorithm uses a balanced tree structure. The embodiment described below uses a circular list.

EXAMPLE EMBODIMENT

In an embodiment, a user of an adaptive learning system is presented with a set of points. For example, the points could be in the form of a scatterplot based on Cartesian coordinates, and may be presented on a plane. The user may be asked to draw or position a “best-fit” line through the points. For example,FIG. 1illustrates a user interface that instructs the user to position a best-fit line through a scatterplot.

In an embodiment, a user may be presented with a hint to assist the user with the task of positioning the line correctly. For example, the user may incorrectly position the line, resulting in the automatic presentation of a hint. Or the user may request a hint. In response to receiving a request for a hint related to the drawing or positioning of a best-fit line, a convex hull is generated. In an embodiment, the convex hull encompasses all of the points displayed. In another embodiment, one or more points may be excluded from the convex hull generating process.

In an embodiment, the convex hull is created to encompass circles that are generated based at least in part on the included points. For example, a circle (visible or not) is created around each point. Then, after creating the circles around each point, a convex hull is generated around the circles. This has the effect of creating an attractive shape with soft edges that lends itself to dissection with a best-fit line.

In an embodiment, the convex hull of the circles is generated using a conventional algorithm for convex hull generation that uses a balanced tree structure, such as the one described in Devillers's and Golin's “Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas.” In another embodiment, the convex hull of the circles may be generated by an algorithm that uses a circular list instead of a balanced tree structure.

FIG. 2illustrates an embodiment of a user interface that includes the convex hull hint. When a user views the convex hull, they are more easily able to determine the appropriate location of the best-fit line by dissecting the convex hull with the line. In an embodiment, the user may reposition a line provided by the user interface. In another embodiment, the user may draw the best-fit line.

Hardware Overview

For example,FIG. 3is a block diagram that illustrates a computer system300upon which an embodiment of the invention may be implemented. Computer system300includes a bus302or other communication mechanism for communicating information, and a hardware processor304coupled with bus302for processing information. Hardware processor304may be, for example, a general purpose microprocessor.

Computer system300further includes a read only memory (ROM)308or other static storage device coupled to bus302for storing static information and instructions for processor304. A storage device310, such as a magnetic disk or optical disk, is provided and coupled to bus302for storing information and instructions.

Computer system300may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system300to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system300in response to processor304executing one or more sequences of one or more instructions contained in main memory306. Such instructions may be read into main memory306from another storage medium, such as storage device310. Execution of the sequences of instructions contained in main memory306causes processor304to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The received code may be executed by processor304as it is received, and/or stored in storage device310, or other non-volatile storage for later execution.