sequence_test.cc

//
// Copyright 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

#include "testing/sequence.h"

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/memory/memory.h"
#include "algorithms/util.h"

namespace differential_privacy {
namespace testing {
namespace {

const int64_t kDimensions = 10;
constexpr int64_t kNumSamples = 5000;
constexpr double kUnitUniformMean = 0.5;
constexpr double kUnitUniformVariance = 1.0 / 12;

std::vector<std::vector<double>> GenerateSamplesFromSequence(
    Sequence<double>* sequence, int64_t num_samples) {
  std::vector<std::vector<double>> samples(num_samples);
  std::generate(samples.begin(), samples.end(),
                [&sequence] { return sequence->GetSample(); });
  return samples;
}

TEST(StoredSequenceTest, CheckStoredSequenceReturnsExpectedOutput) {
  std::vector<std::vector<double>> stored_sequence(
      {{1.0}, {1.0, 2.0}, {1.0, 2.0, 3.0}});
  StoredSequence<double> sequence(stored_sequence);
  // Using 2 * the test vector's size + 1 for the number of samples allows us to
  // exercise the repeating behavior while also ending out of period.
  std::vector<std::vector<double>> samples(
      GenerateSamplesFromSequence(&sequence, 2 * stored_sequence.size() + 1));
  std::vector<std::vector<double>> expected_samples({{1.0},
                                                     {1.0, 2.0},
                                                     {1.0, 2.0, 3.0},
                                                     {1.0},
                                                     {1.0, 2.0},
                                                     {1.0, 2.0, 3.0},
                                                     {1.0}});
  EXPECT_EQ(samples, expected_samples);
}

TEST(StoredSequenceTest, NextNDimensions) {
  StoredSequence<double> sequence({{1.0}, {1.0, 2.0}, {1.0, 2.0, 3.0}});
  const std::vector<int64_t> expected = {1, 2, 3, 1};
  const std::vector<int64_t> dimensions =
      sequence.NextNDimensions(expected.size());
  for (int i = 0; i < expected.size(); ++i) {
    EXPECT_EQ(dimensions[i], expected[i]);
  }
}

void CheckUniformStatistics(const std::vector<std::vector<double>>& samples) {
  for (int i = 0; i < kDimensions; ++i) {
    // Generate vector of values on the k^th dimension.
    std::vector<double> column(samples.size());
    std::transform(samples.begin(), samples.end(), column.begin(),
                   [i](const std::vector<double>& v) { return v[i]; });

    EXPECT_NEAR(Mean(column), kUnitUniformMean, 0.01);
    EXPECT_NEAR(Variance(column), kUnitUniformVariance, 0.01);
    EXPECT_GE(*std::min_element(column.begin(), column.end()), 0.0);
    EXPECT_LE(*std::max_element(column.begin(), column.end()), 1.0);
  }
}

TEST(HaltonSequenceTest, CheckHaltonSequenceStatisticsForUnitValues) {
  HaltonSequence<double> sequence(kDimensions);
  std::vector<std::vector<double>> samples(
      GenerateSamplesFromSequence(&sequence, kNumSamples));
  CheckUniformStatistics(samples);
}

// Check whether the samples have a correlation within 0.05 of 0 between each
// pair of dimensions.
void CheckLowCorrelation(const std::vector<std::vector<double>>& samples) {
  for (int i = 0; i < kDimensions; ++i) {
    std::vector<double> column_first(samples.size());
    std::transform(samples.begin(), samples.end(), column_first.begin(),
                   [i](const std::vector<double>& v) { return v[i]; });
    for (int j = i + 1; j < kDimensions; ++j) {
      std::vector<double> column_second(samples.size());
      std::transform(samples.begin(), samples.end(), column_second.begin(),
                     [j](const std::vector<double>& v) { return v[j]; });
      EXPECT_NEAR(0.0, Correlation(column_first, column_second), 0.05);
    }
  }
}

TEST(HaltonSequenceTest, CheckHaltonSequenceForLowCorrelation) {
  HaltonSequence<double> sequence(kDimensions);
  std::vector<std::vector<double>> samples(
      GenerateSamplesFromSequence(&sequence, kNumSamples));
  CheckLowCorrelation(samples);
}

TEST(HaltonSequenceTest, NextNDimensions) {
  HaltonSequence<double> sequence(kDimensions);
  const std::vector<int64_t> dimensions = sequence.NextNDimensions(4);
  for (int i = 0; i < dimensions.size(); ++i) {
    EXPECT_EQ(dimensions[i], kDimensions);
  }
}

TEST(HaltonTest, Base2) {
  Halton h(2);
  std::vector<double> seq = {0,         1.0 / 2.0, 1.0 / 4.0, 3.0 / 4.0,
                             1.0 / 8.0, 5.0 / 8.0, 3.0 / 8.0, 7.0 / 8.0};
  for (int i = 1; i < seq.size(); ++i) {
    EXPECT_EQ(h.Get(i), seq[i]);
  }
}

}  // namespace
}  // namespace testing
}  // namespace differential_privacy