5
$\begingroup$

I am taking part in a classification challenge (classes are 0 and 1) where the inputs are encrypted (because these are expensive financial data). As the encryption is order-preserving I can only use the fact that e.g. $$ x_1 > x_2 $$ but not $$ d = x_1-x_2 $$

Besides trees, which machine learning algorithms give sound models under these circumstances?

EDIT: I assume that neural nets, SVM or logistic regression are not appropriate in this setting as they use linear transformations $b \cdot x$ which I can not apply as I don't have the "numerical structure" for this.

EDIT 2: I am given data of the following form: $$ (0.2,0.1,0.5,0); (0.1,0.2,0.3,1); (0.02,0.7,0.33,1) $$ and thousands of rows of them (and in my application more columns). In this example the first 3 entries are inputs and the 4th one is the target. All clumns consist of 1001 unique values in the range [0,1]. So I really think that only comparisons are possible.

I am sorry if my question was not formulated precisely enough ... I hope now the problem is clearer!

$\endgroup$
19
  • 2
    $\begingroup$ I don't know of any algorithms specifically designed to handle ranked inputs like this, but something like a decision tree would probably work well - for continuous input it basically selects a threshold to branch on which is essentially the same as selecting which rank to branch on. $\endgroup$ Aug 3, 2016 at 15:30
  • 2
    $\begingroup$ It looks like I need to repeat the point in a previous comment: of course you can apply linear transformations--and any other numerical procedure you like--to these data. Ranks are numbers! $\endgroup$
    – whuber
    Aug 3, 2016 at 15:41
  • 1
    $\begingroup$ Please explain what you mean by "addition is not supported." If you are suggesting that operations like sums, means, etc. on these numbers is meaningless, then that's just not correct--and might lie at the heart of your question. You might enjoy reading FM Lord's On the Statistical Treatment of Football Numbers. $\endgroup$
    – whuber
    Aug 4, 2016 at 13:07
  • 1
    $\begingroup$ Since I don't have the data, I cannot honestly give an opinion on whether any particular procedure will work--but I can say that the nature of these data does not appear to rule out any procedures from consideration. Yes, the answer should be clear in that paper (which is very accessible and non-mathematical, by the way). $\endgroup$
    – whuber
    Aug 4, 2016 at 14:34
  • 2
    $\begingroup$ See Velleman and Wilkinson (1993), Nominal, Ordinal, Interval, and Ratio Typologies are Misleading. $\endgroup$
    – whuber
    Aug 4, 2016 at 15:31

2 Answers 2

1
+50
$\begingroup$

In order to better understand the problem I think it is worth explaining the main idea of how order-preserving cryptography works.

Imagine that we have column vector $\mathbf{x}$ than we want to encrypt. The encryption function is $f(\cdot)$ and it is monotonically increasing, and potentially with varying slope.

The cipher text of $\mathbf{x}$ is $\mathbf{y}=f(\mathbf{x})$, and has the following properties

  • if $x_1 \geq x_2$ then $y_1 \geq y_2$
  • if $x_2 = x_2$ then $y_2 = y_2$ (this is usually prevented)
  • $d(x_1,x_2) \neq d(y_1,y_2)$
  • if $d(x_1,x_2) \geq d(x_3,x_4)$ does not give information about $d(y_1,y_2)$, and $d(y_3,y_4)$

The second property can be prevented by adding noise to $\mathbf{x}$. For example if $x_i$ is an integer between $[0,9]$. Then, $\hat{\mathbf{x}}=10\times\mathbf{x}+\mathbf{n}$, where $\mathbf{n}$ is vector a of random integer between $[0,9]$. This transformation preserves the ordering in $\hat{\mathbf{y}}=f(\hat{\mathbf{x}})$, but removes the identification of attributes with the same value.

Given that I think you should stick to tree based classifiers such as random forest.

$\endgroup$
1
  • $\begingroup$ It must be the noise term that makes some approaches harder than without encryption. Is there are chance to get rid of the noise? Aren't there approeaches in deep learning (DL) to get rid of noise? I am not familiar enough with DL ... RBMs? Autoencoding? Do you have any idea? $\endgroup$
    – Richi W
    Aug 9, 2016 at 6:34
0
$\begingroup$

I don't think you should use order to predict the binary outcome since if a model trained on your data is applied to totally unseen data which was collected in a slightly different way (not sure how that data was collected) then it's going to perform very badly.

Moreover, such "golden features" based on data ordering are sometimes a result of data leaks and you do not want to train your model on such data for the reason given above.

$\endgroup$
4
  • 1
    $\begingroup$ If the relative position of future or test data can be seen relative to the training data ordering, this might be less of an issue $\endgroup$
    – Henry
    Aug 3, 2016 at 15:35
  • 1
    $\begingroup$ Could you elaborate on the reasons why "it's going to perform very badly"? I see no basis for such a pessimistic conclusion in general. Moreover, in this situation raw performance may be irrelevant: one only has to outperform the competition. $\endgroup$
    – whuber
    Aug 3, 2016 at 15:43
  • $\begingroup$ OK, perhaps I worded my answer in a wrong way. I recently took part in a ML competition where 3 teams significantly outperformed the rest. As it turned out, there was a data leak present and the teams - not knowingly - exploited it. It was a data ordering issue. After the competition finished the issue became clear and we had a discussion about it. Now, I think that it would perform badly (provided it is indeed data leak) because it is fit to a feature which would not exist in real-world data it would be used on, hence its predictive power would be low. I fully agree with your last statement. $\endgroup$
    – slazien
    Aug 3, 2016 at 21:24
  • $\begingroup$ I have 90K training data and 30K test data. The ordering on training will not work for test I assume. Just comparisons can be applied. And yes: it is good to be better than others but parts of the predictions are used to invest so the predictions should be accurate by themselves. $\endgroup$
    – Richi W
    Aug 4, 2016 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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