Skip to content

Instantly share code, notes, and snippets.

@madhavajay

madhavajay/native-swiftdp.ipynb Secret

Created May 20, 2020 04:36
Show Gist options
  • Save madhavajay/8f78995abd7b8578d4b4c5b283bd0b1e to your computer and use it in GitHub Desktop.
Save madhavajay/8f78995abd7b8578d4b4c5b283bd0b1e to your computer and use it in GitHub Desktop.
Download ZIP
Native SwiftDP
Display the source blob
Display the rendered blob
Raw
native-swiftdp.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Native SwiftDP",
"provenance": [],
"authorship_tag": "ABX9TyPcPkfOvXiUWci0zqL/+y+m",
"include_colab_link": true
},
"kernelspec": {
"name": "swift",
"display_name": "Swift"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/madhavajay/8f78995abd7b8578d4b4c5b283bd0b1e/native-swiftdp.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "code",
"metadata": {
"id": "5JiyG3NNXSBh",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 204
},
"outputId": "9ffdee09-bd35-4664-9d51-1c68cfc519a6"
},
"source": [
"//\n",
"// SwiftDP\n",
"//\n",
"// Created by Madhava Jay on 20/5/20.\n",
"//\n",
"\n",
"import Foundation\n",
"\n",
"// SWIFT FOO\n",
"\n",
"typealias DPType = BinaryFloatingPoint & ExpressibleByFloatLiteral\n",
"\n",
"func pow<T>(_ base: T, _ power: T) -> T\n",
"where T:DPType {\n",
" return pow(base as! Double, power as! Double) as! T\n",
"}\n",
"\n",
"func exp<T>(_ base: T) -> T\n",
" where T:DPType {\n",
" return exp(base as! Double) as! T\n",
"}\n",
"\n",
"func log2<T>(_ base: T) -> T\n",
" where T: DPType {\n",
" return log2(base as! Double) as! T\n",
"}\n",
"\n",
"infix operator %\n",
"public func %<T> (left:T, right:T) -> T\n",
"where T:FloatingPoint {\n",
" return left.truncatingRemainder(dividingBy: right)\n",
"}\n",
"\n",
"extension BinaryFloatingPoint {\n",
" func convert<T>() -> T {\n",
" switch T.self {\n",
" case is Int8.Type:\n",
" return Int8(self) as! T\n",
" case is Int16.Type:\n",
" return Int16(self) as! T\n",
" case is Int32.Type:\n",
" return Int32(self) as! T\n",
" case is Int64.Type:\n",
" return Int64(self) as! T\n",
" case is UInt8.Type:\n",
" return UInt8(self) as! T\n",
" case is UInt16.Type:\n",
" return UInt16(self) as! T\n",
" case is UInt32.Type:\n",
" return UInt32(self) as! T\n",
" case is UInt64.Type:\n",
" return UInt64(self) as! T\n",
" case is Int.Type:\n",
" return Int(self) as! T\n",
" case is Float.Type:\n",
" return Float(self) as! T\n",
" case is Double.Type:\n",
" return Double(self) as! T\n",
" case is Float80.Type:\n",
" return Float80(self) as! T\n",
" default:\n",
" return self as! T\n",
" }\n",
" }\n",
"}\n",
"\n",
"extension DPType {\n",
" func getSign<T>() -> T {\n",
" switch self {\n",
" case let x where x == 0:\n",
" return 0.0 as! T\n",
" case let x where x < 0:\n",
" return -1.0 as! T\n",
" case let x where x > 0:\n",
" return 1.0 as! T\n",
" default:\n",
" return 0.0 as! T\n",
" }\n",
" }\n",
"}\n",
"\n",
"\n",
"// TypeScript Port to Swift\n",
"\n",
"/**\n",
" * Status code for results returns by pertubation addNoise method\n",
" */\n",
"enum StatusCode: Error {\n",
" //case successfullyPerturbed // Noise added successfully\n",
" case privacyBudgetExceeded // Privacy budget exceeded\n",
" case outOfRange // exceeded bounds\n",
" case noiseOverflow // generated noise is likely to overflow\n",
" case error // unknown error occurred\n",
"}\n",
"\n",
"// Common public interface for perturbation mechanisms\n",
"// note that delta is not included as it is typically private\n",
"protocol PerturbationMechanism {\n",
" associatedtype T: DPType\n",
" associatedtype G: Numeric\n",
"\n",
" var epsilon: T { get }\n",
" var delta: T { get }\n",
"// var _currentStatus: StatusCode? { get }\n",
"\n",
" func addNoise(sensitivity: T, queryResult: T) -> Result<G, StatusCode>\n",
" func getLowerBounds() -> T\n",
" func getUpperBounds() -> T\n",
"}\n",
"\n",
"struct LaplaceMechanism<T, G>: PerturbationMechanism\n",
"where T: DPType,\n",
" G: Numeric {\n",
" let _delta: T\n",
" let _epsilon: T\n",
" let _privacyBudget: T\n",
" let _kMaxOverflowProbability: T\n",
" let _kClampFactor: T\n",
"\n",
" init() {\n",
" self._delta = 0.0\n",
" self._epsilon = 0.3 // Kritika to very this\n",
" self._privacyBudget = 1.0\n",
" self._kMaxOverflowProbability = pow(2.0, -64)\n",
" self._kClampFactor = pow(2.0, 39)\n",
" }\n",
"\n",
" var delta: T {\n",
" return _delta\n",
" }\n",
"\n",
" var epsilon: T {\n",
" return _epsilon\n",
" }\n",
"\n",
" private func exponentialSample(mean: T) -> T {\n",
" let random = Double.random(in: 0 ..< 1)\n",
" let exp = (mean * -1) * (log(random) as! T)\n",
" return exp\n",
" }\n",
"\n",
" private func cdf(scale: T, point: T) -> T {\n",
" if (point > 0) {\n",
" return 1 - 0.5 * exp(-point / scale)\n",
" }\n",
" else {\n",
" return 0.5 * exp(point / scale)\n",
" }\n",
" }\n",
"\n",
" private func clamp(lower: T, upper: T, value: T) -> T {\n",
" if (value > upper) {\n",
" return upper\n",
" }\n",
" if (value < lower) {\n",
" return lower\n",
" }\n",
" return value\n",
" }\n",
"\n",
" // Returns the smallest power of 2 greater than or equal to n. n must be > 0\n",
" // Includes negative powers.\n",
" private func nextPowerOfTwo(value: T) -> T {\n",
" return pow(2.0, ceil(log2(value)))\n",
" }\n",
"\n",
" // Rounds n to the nearest multiple of base. Ties are broken towards +inf.\n",
" // If base is 0, returns n.\n",
" private func roundToNearestMultiple(value: T, base: T) -> T {\n",
" guard !base.isZero else {\n",
" return value\n",
" }\n",
"\n",
" let remainder: T = value % base\n",
" if (abs(remainder) > base / 2) {\n",
" let sign: T = remainder.getSign()\n",
" return value - remainder + (sign * base)\n",
" }\n",
" if (abs(remainder) == base / 2) {\n",
" return value + base / 2\n",
" }\n",
" return value - remainder\n",
" }\n",
"\n",
" func getLowerBounds() -> T {\n",
" if (-T.greatestFiniteMagnitude < -self._kClampFactor) {\n",
" return -self._kClampFactor\n",
" }\n",
" return -T.greatestFiniteMagnitude\n",
" }\n",
"\n",
" func getUpperBounds() -> T {\n",
" if (self._kClampFactor < T.greatestFiniteMagnitude) {\n",
" return self._kClampFactor\n",
" }\n",
" return T.greatestFiniteMagnitude\n",
" }\n",
"\n",
" func addNoise(sensitivity: T, queryResult: T) -> Result<G, StatusCode> {\n",
" //return .success(1.0 as! T)\n",
" // 1) sample from laplace distribution\n",
" let noise = self.exponentialSample(mean: sensitivity / self._epsilon)\n",
" // 2) calculate overflowProbability to ensure noise does not overflow\n",
" // assumption: sensitivity is L1 sensitivity\n",
" let diversity = sensitivity / self._epsilon\n",
" let one = 1 - self.cdf(scale: diversity, point: T.greatestFiniteMagnitude)\n",
" // least floating point is (minus) -T.greatestFiniteMagnitude\n",
" let two = self.cdf(scale: diversity, point: -T.greatestFiniteMagnitude)\n",
" let overflowProbability = one + two\n",
" // 3) check if overflowProbability exceeded. if overflowProbability\n",
" // is exceeded return StatusCode.noiseOverflow\n",
" if (overflowProbability >= self._kMaxOverflowProbability) {\n",
" return .failure(.noiseOverflow)\n",
" }\n",
" // 4) if bounds not exceeded:\n",
" // 5.1) add noise to the query result, and clamp the result\n",
" let initialResult = self.clamp(\n",
" lower: self.getLowerBounds(),\n",
" upper: self.getUpperBounds(),\n",
" value: queryResult\n",
" ) + noise\n",
"\n",
" let nearestPower = self.nextPowerOfTwo(\n",
" value: diversity / self._privacyBudget\n",
" )\n",
"\n",
" let roundedResult = self.roundToNearestMultiple(\n",
" value: initialResult,\n",
" base: nearestPower\n",
" )\n",
"\n",
" let finalNoisedResult = self.clamp(\n",
" lower: self.getLowerBounds(),\n",
" upper: self.getUpperBounds(),\n",
" value: roundedResult\n",
" )\n",
" //TODO: When to return StatusCode.outOfRange\n",
" // 5.3) set currentStatus to .successfullyPerturbed\n",
" // unused .successfullyPerturbed\n",
" // 5.4) update privacy budget\n",
" // 5.5) if privacy budget exceeded set currentStatus to\n",
" // runOutOfBudget and return that value\n",
" // 5.6) return result\n",
" return .success(finalNoisedResult.convert())\n",
" }\n",
"}\n",
"\n",
"\n",
"// TESTS\n",
"\n",
"// test all the ints\n",
"\n",
"let int8: LaplaceMechanism<Double, Int8> = LaplaceMechanism()\n",
"let int8r = int8.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: int8), int8r)\n",
"\n",
"let int16: LaplaceMechanism<Double, Int16> = LaplaceMechanism()\n",
"let int16r = int16.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: int16), int16r)\n",
"\n",
"let int32: LaplaceMechanism<Double, Int32> = LaplaceMechanism()\n",
"let int32r = int32.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: int32), int32r)\n",
"\n",
"let int64: LaplaceMechanism<Double, Int64> = LaplaceMechanism()\n",
"let int64r = int64.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: int64), int64r)\n",
"\n",
"let uint8: LaplaceMechanism<Double, UInt8> = LaplaceMechanism()\n",
"let uint8r = uint8.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: uint8), uint8r)\n",
"\n",
"let uint16: LaplaceMechanism<Double, UInt16> = LaplaceMechanism()\n",
"let uint16r = uint16.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: uint16), uint16r)\n",
"\n",
"let uint32: LaplaceMechanism<Double, UInt32> = LaplaceMechanism()\n",
"let uint32r = uint32.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: uint32), uint32r)\n",
"\n",
"let uint64: LaplaceMechanism<Double, UInt64> = LaplaceMechanism()\n",
"let uint64r = uint64.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: uint64), uint64r)\n",
"\n",
"\n",
"// test all the floats\n",
"let float: LaplaceMechanism<Double, Float> = LaplaceMechanism()\n",
"let floatr = float.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: float), floatr)\n",
"\n",
"let double: LaplaceMechanism<Double, Double> = LaplaceMechanism()\n",
"let doubler = double.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: double), doubler)\n",
"\n",
"let float80: LaplaceMechanism<Double, Float80> = LaplaceMechanism()\n",
"let float80r = float80.addNoise(sensitivity: 1, queryResult: 2)\n",
"print(type(of: float80), float80r)\n"
],
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": [
"LaplaceMechanism<Double, Int8> success(4)\r\n",
"LaplaceMechanism<Double, Int16> success(8)\r\n",
"LaplaceMechanism<Double, Int32> success(4)\r\n",
"LaplaceMechanism<Double, Int64> success(4)\r\n",
"LaplaceMechanism<Double, UInt8> success(4)\r\n",
"LaplaceMechanism<Double, UInt16> success(4)\r\n",
"LaplaceMechanism<Double, UInt32> success(4)\r\n",
"LaplaceMechanism<Double, UInt64> success(8)\r\n",
"LaplaceMechanism<Double, Float> success(20.0)\r\n",
"LaplaceMechanism<Double, Double> success(4.0)\r\n",
"LaplaceMechanism<Double, Float80> success(4.0)\r\n"
],
"name": "stdout"
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "XfwRnI6hXdsc",
"colab_type": "code",
"colab": {}
},
"source": [
""
],
"execution_count": 0,
"outputs": []
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment