low_degree.py 文件源码

def get_training_set_size(n, degree, epsilon, delta):
        """
        This function calculates the training set size that is needed to satisfy the theoretical requirements of the
        Low Degree Algorithm such that the compliance of the epsilon and delta parameters is guaranteed.
        :param n: int
                  Input length
        :param degree: int
                       The degree up to which the Fourier coefficients are approximated
        :param epsilon: float
                        The maximum error rate of the model
        :param delta: float
                      The maximum failure rate of the algorithm, where epsilon is not satisfied
        :return:
        """
        monomial_count = 0
        for k in range(degree + 1):
            monomial_count += ncr(n, k)
        return int(4 * monomial_count * np.log(2 * monomial_count / delta) / epsilon)