title: Can any machine learning algorithm find this pattern: x1 < x2 without generating a new feature (e.g. x1-x2) first?
body: <p>If I had 2 features x1 and x2 where I know that the pattern is: </p>
  
  <pre><code>if x1 &lt; x2 then 
      class1 
  else 
      class2
  </code></pre>
  
  <p>Can any machine learning algorithm find such a pattern? What algorithm would that be?</p>
  
  <p>I know that I could create a third feature x3 = x1-x2. Then feature x3 can easily be used by some machine learning algorithms. For example a decision tree can solve the problem 100% using x3 and just 3 nodes (1 decision and 2 leaf nodes). </p>
  
  <p>But, is it possible to solve this without creating new features? This seems like a problem that should be easily solved 100% if a machine learning algorithm could only find such a pattern.</p>
  
  <p>I tried MLP and SVM with different kernels, including svg kernel and the results are not great. As an example of what I tried, here is the scikit-learn code where the SVM could only get a score of 0.992:</p>
  
  <pre><code>import numpy as np
  from sklearn.svm import SVC
  
  # Generate 1000 samples with 2 features with random values
  X_train = np.random.rand(1000,2)
  
  # Label each sample. If feature "x1" is less than feature "x2" then label as 1, otherwise label is 0.
  y_train = X_train[:,0] &lt; X_train[:,1]
  y_train = y_train.astype(int) # convert boolean to 0 and 1
  
  svc = SVC(kernel = "rbf", C = 0.9) # tried all kernels and C values from 0.1 to 1.0
  
  svc.fit(X_train, y_train)
  print("SVC score: %f" % svc.score(X_train, y_train))
  </code></pre>
  
  <p>Output running the code:</p>
  
  <pre><code>SVC score: 0.992000
  </code></pre>
  
  <p>This is an oversimplification of my problem. The real problem may have hundreds of features and different patterns, not just x1 &lt; x2. However, to start with it would help a lot to know how to solve for this simple pattern.</p>