1
$\begingroup$

I generate some simple graphs based on usage stats of a website, and they may look like these:

converge diverge

I call the 'pattern' on the left 'convergence', and the 'pattern' on the right 'divergence'. The terms 'convergence' and 'divergence' are loosely and visually defined, and they simply means that the two curves either become closer and intersected (decreasing difference in Y while increasing in X) or become apart (increasing difference in Y while increasing in X)

Of course, the curves may neither converge nor diverge. An extreme case of such case is they may evolve more or less parallel to each other.

My problem is to recognize the convergence and the divergence patterns. This may be trivial as done visually by human, but I want to automate the task using an algorithm, and likely a ML algorithm. "Pattern recognition' comes to mind as a (broad) area relating to this kind of problem.

I have some very high-level idea about a possible approach: first manually label some existing graphs as 'convergence', 'divergence', or 'other', and then use a set of these categorized graphs/images to 'train' the ML algorithm in the hope that the algorithm can recognize the patterns on its own after proper training.

My specific questions are:

  1. What are the recommended ML algorithm(s) for this problem? And any pointer to the theory and implementation of such algorithm(s) is appreciated.

  2. I may be terribly ignorant, but: does such a ML algorithm operate on the graph/image directly or does it operate on the underlying data points that make up the graph? In other words, what would be the input to the algorithm? A series of images or a bunch of numbers?

$\endgroup$
  • 3
    $\begingroup$ Why would you use the images if you have the raw data? $\endgroup$ – Raphael Jun 13 '15 at 15:11
  • $\begingroup$ @Raphael, that's my intuition as well, but I don't know enough about ML to decide which input is better. For example, I know there are ML algorithms for detecting patterns in medical images for which you probably don't have raw data. $\endgroup$ – skyork Jun 13 '15 at 19:29
  • 1
    $\begingroup$ aa youve stated the problem, it does not really sound that hard & that mere math/ calculation metrics might succeed (eg linear regression on both curves, compare slopes/ intercepts/ intersects etc, although technically linear regression is considered a basic ML technique). if you described what the graphs are for (yes it would probably help) & what you are attempting to measure overall, ie more bkg it would be better. and yeah, creating good inputs into the ML is a large part of the science/ art, there are no totally std ways to do it, although each field has established "design patterns"... $\endgroup$ – vzn Jun 14 '15 at 1:24
5
$\begingroup$

I suspect machine learning is the wrong approach. Instead, I suspect you will do better to define a metric and measure the metric, or define a hypothesis and use hypothesis testing. You are not trying to predict the future evolution of these values; that's something that ML might be suitable for, but that's not what you're trying to do, so ML doesn't seem like the right tool for the job.

Let me suggest an approach. If $f(t),g(t)$ are the values of the measurements at time $t$, define $D(t) = |f(t)-g(t)|$ (the absolute value of the difference). $D(t)$ measures how close they are. Then, you want to test whether $D(t)$ is increasing or decreasing. If $D(t)$ is decreasing, then you have a situation of "convergence"; if $D(t)$ is increasing, then you have a situation of "divergence".

How can you test whether $D(t)$ is increasing vs decreasing, over some time period? Here's one simple approach. You could separate your time window into two halves, the first half and the second half. Calculate the average value of $D(t)$ over the first half, say $\mu_0$, and the average value of $D(t)$ over the second half, say $\mu_1$. Now you can compare $\mu_0$ to $\mu_1$, to determine whether it is increasing or decreasing.

Alternatively, another approach would be to use simple linear regression on $D(t)$ to fit a linear model $D(t) \sim \alpha t + \beta$, and then test whether the slope $\alpha$ is greater than zero or smaller than zero.

However, one problem with this is that your conclusion might be confounded by noise: it might be that $D(t)$ is neither increasing nor decreasing, but all you're seeing is statistical noise. So can you separate out the case where $D(t)$ is increasing from the case where $D(t)$ is decreasing?

The answer is yes: you can test for statistical significance using hypothesis testing. If you observe $\mu_0 > \mu_1$, you can use a hypothesis test to test whether this difference is statistically significant (e.g., using a permutation test). Or, if you fit a linear model and find $\alpha > 0$, you can use a hypothesis test to test whether the difference from zero is statistically significant (this is covered under standard textbooks on linear regression).

There's lots more one can say about hypothesis testing, but this should give you the general approach. The short version is: don't use machine learning; using an appropriately chosen statistical measure or statistical hypothesis test.

$\endgroup$
3
$\begingroup$

I think the key is to abstract your problem by finding appropriate features. For example a feature could be the minimal distance between the two curves. Or how many times do they cross over. Or how many steps do they stay less than K units away from each other. Think about features that will capture convergence and divergence. Once you have the right features you can throw them into your favourite machine learning algorithm like a Support Vector Machine, Neural Network or Decision Tree. I would give the learning algorithm a set of numbers, because it will make the learning much easier than giving it the whole image.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.