SYSTEMS AND METHODS FOR SECURELY TRAINING A DECISION TREE

1 . A method comprising:

publishing, by a first party, a first set of nominated cut-off values at a current node of a decision tree to be trained;

computing a first respective impurity distribution value for the first set of nominated cut-off values at the current node;

creating first respective n shares of the first respective impurity distribution value;

transmitting, from the first party and so a second party, one of the first respective n shares of the first respective impurity distribution value;

receiving from the second party one of a second respective n shares of the second respective impurity distribution value;

using a secure multi-party computation, adding a group of impurity distribution values to yield a combined impurity value based on the one of the first respective n shares of the first respective impurity distribution value and the one of the second respective n shares of the second respective impurity distribution value; and

determining, based on the combined impurity value, a best threshold for the current node.

2 . The method of claim 1 , wherein the first party and the second party split respective data based on the best threshold at the current node.

3 . The method of claim 2 , further comprising:

repeating the method of claim 1 for each additional node in the decision tree until the decision tree is trained.

4 . The method of claim 3 , wherein the decision tree is determined to be trained based on a criteria.

5 . The method of claim 4 , wherein the criteria comprises one or more of a decision tree depth or an impurity threshold.

6 . The method of claim 1 , wherein using the secure multi-party computation further comprises including a trusted party to accelerate computations.

7 . The method of claim 6 , wherein the trusted party does not learn any significant data from the first party or the second party.

8 . The method of claim 1 , wherein the first respective impurity distribution value and the second respective impurity distribution value identify how good a respective proposed threshold impacts a respective feature at the current node and how perfect the respective proposed threshold results in a proper prediction outcome for the decision tree.

9 . The method of claim 8 , wherein the first respective impurity distribution value and the second respective impurity distribution value identify each include a first value of a first number of first prediction outcomes for the decision tree and a second value of a second number of second prediction outputs from the decision tree.

10 . The method of claim 9 , wherein the first value is a “1” and the second value is a “0”.

11 . A system comprising:

at least one processor; and

a computer-readable storage device storing instructions which, when executed by the at least one processor, cause the at least one processor to perform operations comprising:

publishing, by a first party, a first set of nominated cut-off values at a current node of a decision tree to be trained;

computing a first respective impurity distribution value for the first set of nominated cut-off values at the current node;

creating first respective n shares of the first respective impurity distribution value;

transmitting, from the first party and so a second party, one of the first respective n shares of the first respective impurity distribution value;

receiving from the second party one of a second respective n shares of the second respective impurity distribution value;

using a secure multi-party computation, adding a group of impurity values to yield a combined impurity value based on the one of the first respective n shares of the first respective impurity distribution value and the one of the second respective n shares of the second respective impurity distribution value; and

determining, based on the combined impurity value, a best threshold for the current node.

12 . The system of claim 11 , wherein the first party and the second party split respective data based on the best threshold at the current node.

13 . The system of claim 12 , further comprising:

repeating the method of claim 1 for each additional node in the decision tree until the decision tree is trained.

14 . The system of claim 13 , wherein the decision tree is determined to be trained based on a criteria.

15 . The system of claim 14 , wherein the criteria comprises one or more of a decision tree depth or an impurity threshold.

16 . The system of claim 11 , wherein using the secure multi-party computation further comprises including a trusted party to accelerate computations.

17 . The system of claim 16 , wherein the trusted party does not learn any significant data from the first party or the second party.

18 . The system of claim 11 , wherein the first respective impurity distribution value and the second respective impurity distribution value identify how good a respective proposed threshold impacts a respective feature at the current node and how perfect the respective proposed threshold results in a proper prediction outcome for the decision tree.

19 . The system of claim 18 , wherein the first respective impurity distribution value and the second respective impurity distribution value identify each include a first value of a first number of first prediction outcomes for the decision tree and a second value of a second number of second prediction outputs from the decision tree.

20 . The system of claim 19 , wherein the first value is a “1” and the second value is a “0”.