Every few months, I revisit one of my many neural network implementations. Because neural networks are so complicated, there are dozens of ideas to explore. I always find something new and interesting.

My latest exploration was looking at a program to find anomalous data items using a neural network autoencoder and reconstruction error. The basic idea is to create a model that predicts its input. Data items that aren’t predicted well don’t fit the model well and are therefore anomalous.

I used one of my standard synthetic datasets. Each item represents a persons. The raw data looks like:

F   24   michigan   29500.00   liberal
M   39   oklahoma   51200.00   moderate
F   63   nebraska   75800.00   conservative
M   36   michigan   44500.00   moderate
F   27   nebraska   28600.00   liberal
. . .

The fields are sex, age, State of residence, annual income, and political leaning. The normalized and encoded data is:

 1, 0.24, 1, 0, 0, 0.2950, 0, 0, 1
 0, 0.39, 0, 0, 1, 0.5120, 0, 1, 0
 1, 0.63, 0, 1, 0, 0.7580, 1, 0, 0
 0, 0.36, 1, 0, 0, 0.4450, 0, 1, 0
 1, 0.27, 0, 1, 0, 0.2860, 0, 0, 1
. . .

Sex is encoded as M = 0, F = 1. Age is normalized by dividing by 100. State is one-hot encoded as Michigan = 100, Nebraska = 010, Oklahoma = 001. Income is normalized by dividing by 100,000. Political leaning is one-hot encoded as conservative = 100, moderate = 010, liberal = 001. There are 240 items.

Implementing a neural network from scratch is complicated, but I’ve been studying NNs for years and I’ve implemented them many times. The complexity of NNs means that there are dozens of design alternatives.

The normalized data is loaded into memory like so:

import numpy as np

def main():
  print("Begin autoencoder anomaly detection ")
  # 0. misc
  np.random.seed(0)
  np.set_printoptions(precision=4, suppress=True,
    floatmode='fixed')

  # 1. load data like:
  #  1, 0.24, 1, 0, 0, 0.2950, 0, 0, 1
  #  0, 0.39, 0, 0, 1, 0.5120, 0, 1, 0

  print("Loading data into memory ")
  data_file = ".\\Data\\people_all.txt"
  data_x = np.loadtxt(data_file, usecols=[0,1,2,3,4,5,6,7,8],
    delimiter=",", comments="#", dtype=np.float32)
  print("Done ")

  print("\nFirst three data items: ")
  for i in range(3):
    print(data_x[i])
. . .

There are no library dependencies except for NumPy. The neural network autoencoder is created using these statements:

  # 2. create network
  print("Creating 9-6-9 tanh, identity MSE autoencoder ")
  nn = NeuralNetwork(9, 6, 9, seed=0)
. . .

The number of input nodes (9) is determined by the data. For an autoencoder, the number of output nodes (1) is the same as the number of input nodes. The number of hidden nodes (6) must be determined by trial and error, but it should be roughly half the number of input/output nodes. If the number of hidden nodes is too large the model will overfit and all items will have tiny reconstruction error. If the number of hidden nodes is too small, the model will underfit and all reconstruction errors will be very large.

The seed value is used for a random number generator that is used for weight and bias initialization and to scramble the order in which data items are processed during training. The neural network uses tanh() activation on the hidden nodes and identity() activation on the output nodes. The training algorithm uses mean squared error.

The neural network is trained like so:

  # 3. train network
  lrn_rate = 0.01
  max_epochs = 1000
  print("Setting learn rate = 0.01 ")
  print("Setting batch size = 10 ")
  print("Setting max epochs = 100 ")
  print("Starting training ")
  nn.train(train_x, train_x, lrn_rate, 10, max_epochs)
  print("Training complete ")
. . .

Notice that train() accepts data_x as both the input and target output. The learning rate, batch size, and number of training epochs were determined by trial and error. The progress messages look like:

Starting training
epoch:     0   MSE =   1.6192
epoch:    10   MSE =   0.0621
epoch:    20   MSE =   0.0459
epoch:    30   MSE =   0.0400
epoch:    40   MSE =   0.0283
epoch:    50   MSE =   0.0130
epoch:    60   MSE =   0.0055
epoch:    70   MSE =   0.0039
epoch:    80   MSE =   0.0035
epoch:    90   MSE =   0.0031
Training complete

The demo program evaluates the trained model using these statements:

  # 5. analyze reconstruction error
  print("Analyzing top 3 reconstruction error ")
  nn.analyze(data_x, 3)
. . .

The output is:

Analyzing top 3 reconstruction error

item idx:   170
actual:
[0.0000 0.6500 0.0000 0.0000 1.0000 0.8180 1.0000
 0.0000 0.0000]
predicted:
[0.1088 0.6610 0.0366 0.0104 0.9532 0.7872 0.9339
 0.0079 0.0582]
reconstruction  error: 0.1561

item idx:   169
actual:
[0.0000 0.4400 0.0000 0.0000 1.0000 0.6300 1.0000
 0.0000 0.0000]
predicted:
[ 0.0745  0.4544  0.0263  0.0066  0.9672  0.5798  0.9547
 -0.0067  0.0520]
reconstruction  error: 0.1221

item idx:   160
actual:
[0.0000 0.2900 0.0000 1.0000 0.0000 0.4000 1.0000
 0.0000 0.0000]
predicted:
[-0.0226  0.3076  0.0554  0.9487 -0.0042  0.4567  1.0035
  0.0106 -0.0140]
reconstruction  error: 0.1004

The most anomalous item is [170] which is (M, 65, Oklahoma, $81,800, conservative). The source data doesn’t have any deliberately anomalous items. I speculate the anomaly is high age (65) combined with high income ($81,800). In a non-demo scenario, data items flagged as anomalous should be examined more closely.

The demo program concludes by saving the trained model weights and biases to file using these statements:

  # 5. save trained model
  print("Saving trained weights to file ")
  nn.save_weights(".\\Models\\people_anomaly.txt")

  # nn2 = NeuralNetwork(9, 6, 9, seed=0)
  # nn2.load_weights(".\\Models\\people_anomaly.txt")
  print("End demo ")
. . .

Another fun and interesting exploration.

The world’s most powerful navies have traditional surface ship and submarine fleets that number in the hundreds. Each ship costs hundreds of millions, or in the case of aircraft carriers and nuclear submarines, billions, of dollars to build and operate. Traditional ships are increasingly vulnerable to increasingly sophisticated inexpensive weapon systems. Unmanned ships are currently anomalies, but the future of naval power will almost certainly be dominated by thousands of unmanned, mostly autonomous, ships.

Modern warfare is becoming increasingly terrifying. But “Si vis pacem, para bellum” (“If you want peace, prepare for war”) as the saying goes.

Demo code. Replace “lt” (less than), “gt”, “lte”, “gte” with Boolean operator symbols.

# people_anomaly.py
# neural network, scratch Python
# autoencoder anomaly detection

import numpy as np

class NeuralNetwork:

  def __init__(self, num_in, num_hid, num_out, seed):
    self.ni = num_in
    self.nh = num_hid
    self.no = num_out
	
    self.i_nodes = np.zeros(shape=self.ni, dtype=np.float32)
    self.h_nodes = np.zeros(shape=self.nh, dtype=np.float32)
    self.o_nodes = np.zeros(shape=self.no, dtype=np.float32)
	
    self.ih_weights = np.zeros(shape=(self.ni,self.nh),
      dtype=np.float32)
    self.ho_weights = np.zeros(shape=(self.nh,self.no),
      dtype=np.float32)
	
    self.h_biases = np.zeros(shape=self.nh, dtype=np.float32)
    self.o_biases = np.zeros(shape=self.no, dtype=np.float32)

    self.ih_grads = np.zeros((self.ni, self.nh),
      dtype=np.float32)
    self.hb_grads = np.zeros(self.nh, dtype=np.float32)
    self.ho_grads = np.zeros((self.nh, self.no),
      dtype=np.float32)
    self.ob_grads = np.zeros(self.no, dtype=np.float32)
	
    self.rnd = np.random.RandomState(seed)
    self.init_weights()

# -----------------------------------------------------------

  def init_weights(self):
    # small random for weights and biases
    num_wts = (self.ni * self.nh) + self.nh + \
      (self.nh * self.no) + self.no
    wts = np.zeros(shape=num_wts, dtype=np.float32)
    lo = -0.01; hi = 0.01
    for i in range(len(wts)):
      wts[i] = (hi - lo) * self.rnd.random() + lo
    self.set_weights(wts)

# -----------------------------------------------------------

  def set_weights(self, weights):
    idx = 0
    for i in range(self.ni):
      for j in range(self.nh):
        self.ih_weights[i][j] = weights[idx]
        idx += 1
    for j in range(self.nh):
      self.h_biases[j] = weights[idx]
      idx += 1
    for j in range(self.nh):
      for k in range(self.no):
        self.ho_weights[j][k] = weights[idx]
        idx += 1
    for k in range(self.no):
      self.o_biases[k] = weights[idx]
      idx += 1

# -----------------------------------------------------------

  def get_weights(self):
    # order: ih_wts, h_biases, ho_wts, o_biases
    num_wts = (self.ni * self.nh) + self.nh + \
      (self.nh * self.no) + self.no
    result = np.zeros(num_wts, dtype=np.float32)
    p = 0
    for i in range(self.ni):
      for j in range(self.nh):
        result[p] = self.ih_weights[i][j]
        p += 1
    for j in range(self.nh):
      result[p] = self.h_biases[j]
      p += 1
    for j in range(self.nh):
      for k in range(self.no):
        result[p] = self.ho_weights[j][k]
        p += 1
    for k in range(self.no):
      result[p] = self.o_biases[k]
      p += 1
    return result

# -----------------------------------------------------------

  def compute_outputs(self, x):
    h_sums = np.zeros(self.nh, dtype=np.float32)
    o_sums = np.zeros(self.no, dtype=np.float32)

    # copy x into i_nodes to avoid by-ref errors
    for i in range(len(x)):
      self.i_nodes[i] = x[i]

    for j in range(self.nh):
      for i in range(self.ni):
        h_sums[j] += self.i_nodes[i] * self.ih_weights[i][j]
      h_sums[j] += self.h_biases[j]
      self.h_nodes[j] = self.hypertan(h_sums[j])  # special

    for k in range(self.no):
      for j in range(self.nh):
        o_sums[k] += self.h_nodes[j] * self.ho_weights[j][k]
      o_sums[k] += self.o_biases[k]

    # use identity activation (derivative = 1)
    for k in range(self.no):  # a single node
      self.o_nodes[k] = o_sums[k]  # identity activation

    # copy o_nodes into an explicit result
    result = np.zeros(self.no, dtype=np.float32)
    for k in range(self.no):
      result[k] = self.o_nodes[k]
	  
    return result

# -----------------------------------------------------------

  @staticmethod
  def hypertan(x):
    if x "lt" -10.0: return -1.0
    elif x "gt" 10.0: return 1.0
    else: return np.tanh(x)

# -----------------------------------------------------------

  # possible output activation
  @staticmethod
  def log_sigmoid(x):
    if x "lt" -10.0: return 0.0
    elif x "gt" 10.0: return 1.0
    else: return 1.0 / (1.0 + np.exp(-x))

# -----------------------------------------------------------

  def zero_out_grads(self):
    for i in range(self.ni):
      for j in range(self.nh):
        self.ih_grads[i][j] = 0.0
    for j in range(self.nh):  
      self.hb_grads[j] = 0.0
    for j in range(self.nh):
      for k in range(self.no):
        self.ho_grads[j][k] = 0.0
    for k in range(self.no):
      self.ob_grads[k] = 0.0

# -----------------------------------------------------------

  def accum_grads(self, y):
    # y is target scalar
    o_signals = np.zeros(self.no, dtype=np.float32)
    h_signals = np.zeros(self.nh, dtype=np.float32)

    # 1. compute output node scratch signals 
    derivative = 1.0        # MSE with identity activation
    for k in range(self.no):
      o_signals[k] = derivative * (self.o_nodes[k] - y[k]) 

    # 2. accum hidden-to-output gradients 
    for j in range(self.nh):
      for k in range(self.no):
        self.ho_grads[j][k] += o_signals[k] * \
          self.h_nodes[j]

    # 3. accum output node bias gradients
    for k in range(self.no):
      self.ob_grads[k] += o_signals[k] * 1.0 

    # 4. compute hidden node signals
    for j in range(self.nh):
      sum = 0.0
      for k in range(self.no):
        sum += o_signals[k] * self.ho_weights[j][k]

      derivative = \
        (1 - self.h_nodes[j]) * \
        (1 + self.h_nodes[j])  # assumes tanh
      h_signals[j] = derivative * sum

    # 5. accum input-to-hidden gradients
    for i in range(self.ni):
      for j in range(self.nh):
        self.ih_grads[i][j] += \
          h_signals[j] * self.i_nodes[i]

    # 6. accum hidden node bias gradients
    for j in range(self.nh):
      self.hb_grads[j] += h_signals[j] * 1.0

    # 7. clip gradients
    # self.clip_gradients(-0.0001, 0.0001)

# -----------------------------------------------------------

  def update_weights(self, lrn_rate):
    # assumes all gradients computed
    # 1. update input-to-hidden weights
    for i in range(self.ni):
      for j in range(self.nh):
        delta = -1.0 * lrn_rate * self.ih_grads[i][j]
        self.ih_weights[i][j] += delta

    # 2. update hidden node biases
    for j in range(self.nh):
      delta = -1.0 * lrn_rate * self.hb_grads[j]
      self.h_biases[j] += delta

    # 3. update hidden-to-output weights
    for j in range(self.nh):
      for k in range(self.no):
        delta = -1.0 * lrn_rate * self.ho_grads[j][k]
        self.ho_weights[j][k] += delta

    # 4. update output node biases
    for k in range(self.no):
      delta = -1.0 * lrn_rate * self.ob_grads[k]
      self.o_biases[k] += delta

    # 5. clip weights
    # self.clip_weights(-1.0e-8, 1.0e8)

    # 5b. decay
    # self.decay_weights(0.005)

# -----------------------------------------------------------

  def train(self, train_x, train_y, lrn_rate, bat_size,
    max_epochs):
    n = len(train_x)                  # like 200
    batches_per_epoch = n // bat_size # like 20
    freq = max_epochs / 10            # progress
    indices = np.arange(n)

    for epoch in range(max_epochs): 
      self.rnd.shuffle(indices)
      ptr = 0   # points into indices
      for bat_idx in range(batches_per_epoch): # 0, 1, .. 19
        for i in range(bat_size):  # 0 . . 9
          ii = indices[ptr]; ptr += 1
          x = train_x[ii]
          y = train_y[ii]
          self.compute_outputs(x)  # into self.o_nodes
          self.accum_grads(y)

        self.update_weights(lrn_rate)
        self.zero_out_grads()  # prep for next batch
 
      if epoch % freq == 0:
        mse = self.mean_sq_err(train_x, train_y)
        s1 = "epoch: %5d" % epoch
        s2 = "   MSE = %8.4f" % mse
        print(s1 + s2)

# -----------------------------------------------------------

  def mean_sq_err(self, data_x, data_y):
    sum_se = 0.0
    for i in range(len(data_x)):
      x = data_x[i]
      y = data_y[i]   # target vector = inpt vector
      oupt = self.compute_outputs(x)  # 0.1234
      for k in range(self.no):
        sum_se += (y[k] - oupt[k]) * (y[k] - oupt[k])

    return sum_se / len(data_x)   # consider Root MSE

# -----------------------------------------------------------

  def analyze(self, data_x, top_n):
    # display top_n most anomalous
    n = len(data_x)
    result_errs = np.zeros(n, dtype=np.float32)
    for i in range(n):
      x = data_x[i]
      pred = self.compute_outputs(x)
      err = 0.0
      for j in range(self.ni):
        err += (x[j] - pred[j]) * (x[j] - pred[j])
      err = np.sqrt(err)
      result_errs[i] = err

    idxs = np.argsort(result_errs)  # smallest err to high
    idxs = np.flip(idxs)  # highest err  to small

    for i in range(top_n):
      print("\nitem idx: %5d" % idxs[i])
      print("actual: "); print(data_x[idxs[i]])
      pred = self.compute_outputs(data_x[idxs[i]])
      print("predicted: "); print(pred)
      print("reconstruction  error: %0.4f" % \
        result_errs[idxs[i]])

# -----------------------------------------------------------

  def save_weights(self, fn):
    # write weights as single comma-delimied line
    wts = self.get_weights()
    n = len(wts)
    ofs = open(fn, "w")
    for i in range(n):
      w = wts[i]
      ofs.write("%0.4f" % w)
      if i != n-1:
        ofs.write(",")
    ofs.write("\n")
    ofs.close()

# -----------------------------------------------------------

  def load_weights(self, fn):
    ifs = open(fn, "r")
    s = ifs.readline()
    tokens = s.split(",")
    wts = np.zeros(len(tokens), dtype=np.float32)
    for i in range(len(wts)):
      wts[i] = float(tokens[i])
    ifs.close()
    self.set_weights(wts)

# -----------------------------------------------------------
# -----------------------------------------------------------

def main():
  print("\nBegin autoencoder anomaly detection ")
  # 0. misc
  np.random.seed(0)
  np.set_printoptions(precision=4, suppress=True,
    floatmode='fixed')

  # 1. load data like:
  #  1, 0.24, 1, 0, 0, 0.2950, 0, 0, 1
  #  0, 0.39, 0, 0, 1, 0.5120, 0, 1, 0

  print("\nLoading data into memory ")
  data_file = ".\\Data\\people_all.txt"
  data_x = np.loadtxt(data_file, usecols=[0,1,2,3,4,5,6,7,8],
    delimiter=",", comments="#", dtype=np.float32)
  print("Done ")

  print("\nFirst three data items: ")
  for i in range(3):
    print(data_x[i])

  # 2. create network
  print("\nCreating 9-6-9 tanh, identity MSE autoencoder ")
  nn = NeuralNetwork(9, 6, 9, seed=0)

  # 3. train network
  lrn_rate = 0.01
  max_epochs = 100
  print("\nSetting learn rate = 0.01 ")
  print("Setting batch size = 10 ")
  print("Setting max epochs = 100 ")

  print("\nStarting training ")
  nn.train(data_x, data_x, lrn_rate, 10, max_epochs)
  print("Training complete ")

  # 4. sanity check
  # print("\nPredict M 46 Oklahoma $66,400 moderate ")
  # x = np.array([0, 0.46, 0,0,1, 0.6640, 0,1,0],
  #   dtype=np.float32)
  # predicted = nn.compute_outputs(x)
  # print(predicted)

  # 5. analyze reconstruction error
  print("\nAnalyzing top 3 reconstruction error ")
  nn.analyze(data_x, 3)

  # 5. save trained model
  print("\nSaving trained weights to file ")
  nn.save_weights(".\\Models\\people_anomaly.txt")

  # nn2 = NeuralNetwork(9, 6, 9, seed=0)
  # nn2.load_weights(".\\Models\\people_anomaly.txt")

  print("\nEnd demo ")

if __name__ == "__main__":
  main()

Normalized and encoded data:

# people_all.txt
#
# sex (0 = male, 1 = female), age / 100,
# state (michigan = 100, nebraska = 010,
# oklahoma = 001),
# income / 100_000,
# politics (conservative = 100, moderate = 010,
# liberal = 001)
#
1, 0.24, 1, 0, 0, 0.2950, 0, 0, 1
0, 0.39, 0, 0, 1, 0.5120, 0, 1, 0
1, 0.63, 0, 1, 0, 0.7580, 1, 0, 0
0, 0.36, 1, 0, 0, 0.4450, 0, 1, 0
1, 0.27, 0, 1, 0, 0.2860, 0, 0, 1
1, 0.50, 0, 1, 0, 0.5650, 0, 1, 0
1, 0.50, 0, 0, 1, 0.5500, 0, 1, 0
0, 0.19, 0, 0, 1, 0.3270, 1, 0, 0
1, 0.22, 0, 1, 0, 0.2770, 0, 1, 0
0, 0.39, 0, 0, 1, 0.4710, 0, 0, 1
1, 0.34, 1, 0, 0, 0.3940, 0, 1, 0
0, 0.22, 1, 0, 0, 0.3350, 1, 0, 0
1, 0.35, 0, 0, 1, 0.3520, 0, 0, 1
0, 0.33, 0, 1, 0, 0.4640, 0, 1, 0
1, 0.45, 0, 1, 0, 0.5410, 0, 1, 0
1, 0.42, 0, 1, 0, 0.5070, 0, 1, 0
0, 0.33, 0, 1, 0, 0.4680, 0, 1, 0
1, 0.25, 0, 0, 1, 0.3000, 0, 1, 0
0, 0.31, 0, 1, 0, 0.4640, 1, 0, 0
1, 0.27, 1, 0, 0, 0.3250, 0, 0, 1
1, 0.48, 1, 0, 0, 0.5400, 0, 1, 0
0, 0.64, 0, 1, 0, 0.7130, 0, 0, 1
1, 0.61, 0, 1, 0, 0.7240, 1, 0, 0
1, 0.54, 0, 0, 1, 0.6100, 1, 0, 0
1, 0.29, 1, 0, 0, 0.3630, 1, 0, 0
1, 0.50, 0, 0, 1, 0.5500, 0, 1, 0
1, 0.55, 0, 0, 1, 0.6250, 1, 0, 0
1, 0.40, 1, 0, 0, 0.5240, 1, 0, 0
1, 0.22, 1, 0, 0, 0.2360, 0, 0, 1
1, 0.68, 0, 1, 0, 0.7840, 1, 0, 0
0, 0.60, 1, 0, 0, 0.7170, 0, 0, 1
0, 0.34, 0, 0, 1, 0.4650, 0, 1, 0
0, 0.25, 0, 0, 1, 0.3710, 1, 0, 0
0, 0.31, 0, 1, 0, 0.4890, 0, 1, 0
1, 0.43, 0, 0, 1, 0.4800, 0, 1, 0
1, 0.58, 0, 1, 0, 0.6540, 0, 0, 1
0, 0.55, 0, 1, 0, 0.6070, 0, 0, 1
0, 0.43, 0, 1, 0, 0.5110, 0, 1, 0
0, 0.43, 0, 0, 1, 0.5320, 0, 1, 0
0, 0.21, 1, 0, 0, 0.3720, 1, 0, 0
1, 0.55, 0, 0, 1, 0.6460, 1, 0, 0
1, 0.64, 0, 1, 0, 0.7480, 1, 0, 0
0, 0.41, 1, 0, 0, 0.5880, 0, 1, 0
1, 0.64, 0, 0, 1, 0.7270, 1, 0, 0
0, 0.56, 0, 0, 1, 0.6660, 0, 0, 1
1, 0.31, 0, 0, 1, 0.3600, 0, 1, 0
0, 0.65, 0, 0, 1, 0.7010, 0, 0, 1
1, 0.55, 0, 0, 1, 0.6430, 1, 0, 0
0, 0.25, 1, 0, 0, 0.4030, 1, 0, 0
1, 0.46, 0, 0, 1, 0.5100, 0, 1, 0
0, 0.36, 1, 0, 0, 0.5350, 1, 0, 0
1, 0.52, 0, 1, 0, 0.5810, 0, 1, 0
1, 0.61, 0, 0, 1, 0.6790, 1, 0, 0
1, 0.57, 0, 0, 1, 0.6570, 1, 0, 0
0, 0.46, 0, 1, 0, 0.5260, 0, 1, 0
0, 0.62, 1, 0, 0, 0.6680, 0, 0, 1
1, 0.55, 0, 0, 1, 0.6270, 1, 0, 0
0, 0.22, 0, 0, 1, 0.2770, 0, 1, 0
0, 0.50, 1, 0, 0, 0.6290, 1, 0, 0
0, 0.32, 0, 1, 0, 0.4180, 0, 1, 0
0, 0.21, 0, 0, 1, 0.3560, 1, 0, 0
1, 0.44, 0, 1, 0, 0.5200, 0, 1, 0
1, 0.46, 0, 1, 0, 0.5170, 0, 1, 0
1, 0.62, 0, 1, 0, 0.6970, 1, 0, 0
1, 0.57, 0, 1, 0, 0.6640, 1, 0, 0
0, 0.67, 0, 0, 1, 0.7580, 0, 0, 1
1, 0.29, 1, 0, 0, 0.3430, 0, 0, 1
1, 0.53, 1, 0, 0, 0.6010, 1, 0, 0
0, 0.44, 1, 0, 0, 0.5480, 0, 1, 0
1, 0.46, 0, 1, 0, 0.5230, 0, 1, 0
0, 0.20, 0, 1, 0, 0.3010, 0, 1, 0
0, 0.38, 1, 0, 0, 0.5350, 0, 1, 0
1, 0.50, 0, 1, 0, 0.5860, 0, 1, 0
1, 0.33, 0, 1, 0, 0.4250, 0, 1, 0
0, 0.33, 0, 1, 0, 0.3930, 0, 1, 0
1, 0.26, 0, 1, 0, 0.4040, 1, 0, 0
1, 0.58, 1, 0, 0, 0.7070, 1, 0, 0
1, 0.43, 0, 0, 1, 0.4800, 0, 1, 0
0, 0.46, 1, 0, 0, 0.6440, 1, 0, 0
1, 0.60, 1, 0, 0, 0.7170, 1, 0, 0
0, 0.42, 1, 0, 0, 0.4890, 0, 1, 0
0, 0.56, 0, 0, 1, 0.5640, 0, 0, 1
0, 0.62, 0, 1, 0, 0.6630, 0, 0, 1
0, 0.50, 1, 0, 0, 0.6480, 0, 1, 0
1, 0.47, 0, 0, 1, 0.5200, 0, 1, 0
0, 0.67, 0, 1, 0, 0.8040, 0, 0, 1
0, 0.40, 0, 0, 1, 0.5040, 0, 1, 0
1, 0.42, 0, 1, 0, 0.4840, 0, 1, 0
1, 0.64, 1, 0, 0, 0.7200, 1, 0, 0
0, 0.47, 1, 0, 0, 0.5870, 0, 0, 1
1, 0.45, 0, 1, 0, 0.5280, 0, 1, 0
0, 0.25, 0, 0, 1, 0.4090, 1, 0, 0
1, 0.38, 1, 0, 0, 0.4840, 1, 0, 0
1, 0.55, 0, 0, 1, 0.6000, 0, 1, 0
0, 0.44, 1, 0, 0, 0.6060, 0, 1, 0
1, 0.33, 1, 0, 0, 0.4100, 0, 1, 0
1, 0.34, 0, 0, 1, 0.3900, 0, 1, 0
1, 0.27, 0, 1, 0, 0.3370, 0, 0, 1
1, 0.32, 0, 1, 0, 0.4070, 0, 1, 0
1, 0.42, 0, 0, 1, 0.4700, 0, 1, 0
0, 0.24, 0, 0, 1, 0.4030, 1, 0, 0
1, 0.42, 0, 1, 0, 0.5030, 0, 1, 0
1, 0.25, 0, 0, 1, 0.2800, 0, 0, 1
1, 0.51, 0, 1, 0, 0.5800, 0, 1, 0
0, 0.55, 0, 1, 0, 0.6350, 0, 0, 1
1, 0.44, 1, 0, 0, 0.4780, 0, 0, 1
0, 0.18, 1, 0, 0, 0.3980, 1, 0, 0
0, 0.67, 0, 1, 0, 0.7160, 0, 0, 1
1, 0.45, 0, 0, 1, 0.5000, 0, 1, 0
1, 0.48, 1, 0, 0, 0.5580, 0, 1, 0
0, 0.25, 0, 1, 0, 0.3900, 0, 1, 0
0, 0.67, 1, 0, 0, 0.7830, 0, 1, 0
1, 0.37, 0, 0, 1, 0.4200, 0, 1, 0
0, 0.32, 1, 0, 0, 0.4270, 0, 1, 0
1, 0.48, 1, 0, 0, 0.5700, 0, 1, 0
0, 0.66, 0, 0, 1, 0.7500, 0, 0, 1
1, 0.61, 1, 0, 0, 0.7000, 1, 0, 0
0, 0.58, 0, 0, 1, 0.6890, 0, 1, 0
1, 0.19, 1, 0, 0, 0.2400, 0, 0, 1
1, 0.38, 0, 0, 1, 0.4300, 0, 1, 0
0, 0.27, 1, 0, 0, 0.3640, 0, 1, 0
1, 0.42, 1, 0, 0, 0.4800, 0, 1, 0
1, 0.60, 1, 0, 0, 0.7130, 1, 0, 0
0, 0.27, 0, 0, 1, 0.3480, 1, 0, 0
1, 0.29, 0, 1, 0, 0.3710, 1, 0, 0
0, 0.43, 1, 0, 0, 0.5670, 0, 1, 0
1, 0.48, 1, 0, 0, 0.5670, 0, 1, 0
1, 0.27, 0, 0, 1, 0.2940, 0, 0, 1
0, 0.44, 1, 0, 0, 0.5520, 1, 0, 0
1, 0.23, 0, 1, 0, 0.2630, 0, 0, 1
0, 0.36, 0, 1, 0, 0.5300, 0, 0, 1
1, 0.64, 0, 0, 1, 0.7250, 1, 0, 0
1, 0.29, 0, 0, 1, 0.3000, 0, 0, 1
0, 0.33, 1, 0, 0, 0.4930, 0, 1, 0
0, 0.66, 0, 1, 0, 0.7500, 0, 0, 1
0, 0.21, 0, 0, 1, 0.3430, 1, 0, 0
1, 0.27, 1, 0, 0, 0.3270, 0, 0, 1
1, 0.29, 1, 0, 0, 0.3180, 0, 0, 1
0, 0.31, 1, 0, 0, 0.4860, 0, 1, 0
1, 0.36, 0, 0, 1, 0.4100, 0, 1, 0
1, 0.49, 0, 1, 0, 0.5570, 0, 1, 0
0, 0.28, 1, 0, 0, 0.3840, 1, 0, 0
0, 0.43, 0, 0, 1, 0.5660, 0, 1, 0
0, 0.46, 0, 1, 0, 0.5880, 0, 1, 0
1, 0.57, 1, 0, 0, 0.6980, 1, 0, 0
0, 0.52, 0, 0, 1, 0.5940, 0, 1, 0
0, 0.31, 0, 0, 1, 0.4350, 0, 1, 0
0, 0.55, 1, 0, 0, 0.6200, 0, 0, 1
1, 0.50, 1, 0, 0, 0.5640, 0, 1, 0
1, 0.48, 0, 1, 0, 0.5590, 0, 1, 0
0, 0.22, 0, 0, 1, 0.3450, 1, 0, 0
1, 0.59, 0, 0, 1, 0.6670, 1, 0, 0
1, 0.34, 1, 0, 0, 0.4280, 0, 0, 1
0, 0.64, 1, 0, 0, 0.7720, 0, 0, 1
1, 0.29, 0, 0, 1, 0.3350, 0, 0, 1
0, 0.34, 0, 1, 0, 0.4320, 0, 1, 0
0, 0.61, 1, 0, 0, 0.7500, 0, 0, 1
1, 0.64, 0, 0, 1, 0.7110, 1, 0, 0
0, 0.29, 1, 0, 0, 0.4130, 1, 0, 0
1, 0.63, 0, 1, 0, 0.7060, 1, 0, 0
0, 0.29, 0, 1, 0, 0.4000, 1, 0, 0
0, 0.51, 1, 0, 0, 0.6270, 0, 1, 0
0, 0.24, 0, 0, 1, 0.3770, 1, 0, 0
1, 0.48, 0, 1, 0, 0.5750, 0, 1, 0
1, 0.18, 1, 0, 0, 0.2740, 1, 0, 0
1, 0.18, 1, 0, 0, 0.2030, 0, 0, 1
1, 0.33, 0, 1, 0, 0.3820, 0, 0, 1
0, 0.20, 0, 0, 1, 0.3480, 1, 0, 0
1, 0.29, 0, 0, 1, 0.3300, 0, 0, 1
0, 0.44, 0, 0, 1, 0.6300, 1, 0, 0
0, 0.65, 0, 0, 1, 0.8180, 1, 0, 0
0, 0.56, 1, 0, 0, 0.6370, 0, 0, 1
0, 0.52, 0, 0, 1, 0.5840, 0, 1, 0
0, 0.29, 0, 1, 0, 0.4860, 1, 0, 0
0, 0.47, 0, 1, 0, 0.5890, 0, 1, 0
1, 0.68, 1, 0, 0, 0.7260, 0, 0, 1
1, 0.31, 0, 0, 1, 0.3600, 0, 1, 0
1, 0.61, 0, 1, 0, 0.6250, 0, 0, 1
1, 0.19, 0, 1, 0, 0.2150, 0, 0, 1
1, 0.38, 0, 0, 1, 0.4300, 0, 1, 0
0, 0.26, 1, 0, 0, 0.4230, 1, 0, 0
1, 0.61, 0, 1, 0, 0.6740, 1, 0, 0
1, 0.40, 1, 0, 0, 0.4650, 0, 1, 0
0, 0.49, 1, 0, 0, 0.6520, 0, 1, 0
1, 0.56, 1, 0, 0, 0.6750, 1, 0, 0
0, 0.48, 0, 1, 0, 0.6600, 0, 1, 0
1, 0.52, 1, 0, 0, 0.5630, 0, 0, 1
0, 0.18, 1, 0, 0, 0.2980, 1, 0, 0
0, 0.56, 0, 0, 1, 0.5930, 0, 0, 1
0, 0.52, 0, 1, 0, 0.6440, 0, 1, 0
0, 0.18, 0, 1, 0, 0.2860, 0, 1, 0
0, 0.58, 1, 0, 0, 0.6620, 0, 0, 1
0, 0.39, 0, 1, 0, 0.5510, 0, 1, 0
0, 0.46, 1, 0, 0, 0.6290, 0, 1, 0
0, 0.40, 0, 1, 0, 0.4620, 0, 1, 0
0, 0.60, 1, 0, 0, 0.7270, 0, 0, 1
1, 0.36, 0, 1, 0, 0.4070, 0, 0, 1
1, 0.44, 1, 0, 0, 0.5230, 0, 1, 0
1, 0.28, 1, 0, 0, 0.3130, 0, 0, 1
1, 0.54, 0, 0, 1, 0.6260, 1, 0, 0
#
0, 0.51, 1, 0, 0, 0.6120, 0, 1, 0
0, 0.32, 0, 1, 0, 0.4610, 0, 1, 0
1, 0.55, 1, 0, 0, 0.6270, 1, 0, 0
1, 0.25, 0, 0, 1, 0.2620, 0, 0, 1
1, 0.33, 0, 0, 1, 0.3730, 0, 0, 1
0, 0.29, 0, 1, 0, 0.4620, 1, 0, 0
1, 0.65, 1, 0, 0, 0.7270, 1, 0, 0
0, 0.43, 0, 1, 0, 0.5140, 0, 1, 0
0, 0.54, 0, 1, 0, 0.6480, 0, 0, 1
1, 0.61, 0, 1, 0, 0.7270, 1, 0, 0
1, 0.52, 0, 1, 0, 0.6360, 1, 0, 0
1, 0.30, 0, 1, 0, 0.3350, 0, 0, 1
1, 0.29, 1, 0, 0, 0.3140, 0, 0, 1
0, 0.47, 0, 0, 1, 0.5940, 0, 1, 0
1, 0.39, 0, 1, 0, 0.4780, 0, 1, 0
1, 0.47, 0, 0, 1, 0.5200, 0, 1, 0
0, 0.49, 1, 0, 0, 0.5860, 0, 1, 0
0, 0.63, 0, 0, 1, 0.6740, 0, 0, 1
0, 0.30, 1, 0, 0, 0.3920, 1, 0, 0
0, 0.61, 0, 0, 1, 0.6960, 0, 0, 1
0, 0.47, 0, 0, 1, 0.5870, 0, 1, 0
1, 0.30, 0, 0, 1, 0.3450, 0, 0, 1
0, 0.51, 0, 0, 1, 0.5800, 0, 1, 0
0, 0.24, 1, 0, 0, 0.3880, 0, 1, 0
0, 0.49, 1, 0, 0, 0.6450, 0, 1, 0
1, 0.66, 0, 0, 1, 0.7450, 1, 0, 0
0, 0.65, 1, 0, 0, 0.7690, 1, 0, 0
0, 0.46, 0, 1, 0, 0.5800, 1, 0, 0
0, 0.45, 0, 0, 1, 0.5180, 0, 1, 0
0, 0.47, 1, 0, 0, 0.6360, 1, 0, 0
0, 0.29, 1, 0, 0, 0.4480, 1, 0, 0
0, 0.57, 0, 0, 1, 0.6930, 0, 0, 1
0, 0.20, 1, 0, 0, 0.2870, 0, 0, 1
0, 0.35, 1, 0, 0, 0.4340, 0, 1, 0
0, 0.61, 0, 0, 1, 0.6700, 0, 0, 1
0, 0.31, 0, 0, 1, 0.3730, 0, 1, 0
1, 0.18, 1, 0, 0, 0.2080, 0, 0, 1
1, 0.26, 0, 0, 1, 0.2920, 0, 0, 1
0, 0.28, 1, 0, 0, 0.3640, 0, 0, 1
0, 0.59, 0, 0, 1, 0.6940, 0, 0, 1