tf_privacy.tree_aggregation.EfficientTreeAggregator
Stay organized with collections
Save and categorize content based on your preferences.
Efficient tree aggregator to compute accumulated noise.
tf_privacy.tree_aggregation.EfficientTreeAggregator(
value_generator: Union[tf_privacy.tree_aggregation.ValueGenerator, Callable[[], Any]]
)
This class implements the efficient tree aggregation algorithm based on
Honaker 2015 "Efficient Use of Differentially Private Binary Trees".
The noise standard deviation for a node at depth d is roughly
sigma * sqrt(2^{d-1}/(2^d-1)). which becomes sigma / sqrt(2) when
the tree is very tall.
Example usage |
|---|
|
random_generator = GaussianNoiseGenerator(...)
tree_aggregator = EfficientTreeAggregator(random_generator)
state = tree_aggregator.init_state()
for leaf_node_idx in range(total_steps):
assert leaf_node_idx == get_step_idx(state))
noise, state = tree_aggregator.get_cumsum_and_update(state)
|
Args |
|---|
value_generator
|
A ValueGenerator or a no-arg function to generate a
noise value for each tree node.
|
Attributes |
|---|
value_generator
|
A ValueGenerator or a no-arg function to generate a noise
value for each tree node.
|
Methods
get_cumsum_and_update
View source
@tf.function
get_cumsum_and_update(
state: tf_privacy.tree_aggregation.TreeState
) -> Tuple[tf.Tensor, tf_privacy.tree_aggregation.TreeState]
Returns tree aggregated noise and updates TreeState for the next step.
TreeState is updated to prepare for accepting the next leaf node. Note
that get_step_idx can be called to get the current index of the leaf node
before calling this function. This function accept state for the current
leaf node and prepare for the next leaf node because TFF prefers to know
the types of state at initialization. Note that the value of new node in
TreeState.level_buffer will depend on its two children, and is updated
from bottom up for the right child.
| Returns |
|---|
Tuple of (noise, state) where noise is generated by tree aggregated
protocol for the cumulative sum of streaming data, and state is the
updated TreeState..
|
init_state
View source
init_state() -> tf_privacy.tree_aggregation.TreeState
Returns initial TreeState.
Initializes TreeState for a tree of a single leaf node: the respective
initial node value in TreeState.level_buffer is generated by the value
generator function, and the node index is 0.
| Returns |
|---|
An initialized TreeState.
|
reset_state
View source
reset_state(
state: tf_privacy.tree_aggregation.TreeState
) -> tf_privacy.tree_aggregation.TreeState
Returns reset TreeState after restarting a new tree.
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-02-16 UTC.
[null,null,["Last updated 2024-02-16 UTC."],[],[],null,["# tf_privacy.tree_aggregation.EfficientTreeAggregator\n\n\u003cbr /\u003e\n\n|-----------------------------------------------------------------------------------------------------------------------------------|\n| [View source on GitHub](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L355-L522) |\n\nEfficient tree aggregator to compute accumulated noise. \n\n tf_privacy.tree_aggregation.EfficientTreeAggregator(\n value_generator: Union[../../tf_privacy/tree_aggregation/ValueGenerator, Callable[[], Any]]\n )\n\nThis class implements the efficient tree aggregation algorithm based on\nHonaker 2015 \"Efficient Use of Differentially Private Binary Trees\".\nThe noise standard deviation for a node at depth d is roughly\n`sigma * sqrt(2^{d-1}/(2^d-1))`. which becomes `sigma / sqrt(2)` when\nthe tree is very tall.\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Example usage ------------- ||\n|---|---|\n| random_generator = GaussianNoiseGenerator(...) tree_aggregator = EfficientTreeAggregator(random_generator) state = tree_aggregator.init_state() for leaf_node_idx in range(total_steps): assert leaf_node_idx == get_step_idx(state)) noise, state = tree_aggregator.get_cumsum_and_update(state) ||\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Args ---- ||\n|-------------------|---------------------------------------------------------------------------------------|\n| `value_generator` | A `ValueGenerator` or a no-arg function to generate a noise value for each tree node. |\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Attributes ---------- ||\n|-------------------|---------------------------------------------------------------------------------------|\n| `value_generator` | A `ValueGenerator` or a no-arg function to generate a noise value for each tree node. |\n\n\u003cbr /\u003e\n\nMethods\n-------\n\n### `get_cumsum_and_update`\n\n[View source](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L442-L522) \n\n @tf.function\n get_cumsum_and_update(\n state: ../../tf_privacy/tree_aggregation/TreeState\n ) -\u003e Tuple[tf.Tensor, ../../tf_privacy/tree_aggregation/TreeState]\n\nReturns tree aggregated noise and updates `TreeState` for the next step.\n\n`TreeState` is updated to prepare for accepting the *next* leaf node. Note\nthat `get_step_idx` can be called to get the current index of the leaf node\nbefore calling this function. This function accept state for the current\nleaf node and prepare for the next leaf node because TFF prefers to know\nthe types of state at initialization. Note that the value of new node in\n[`TreeState.level_buffer`](../../tf_privacy/tree_aggregation/TreeState#level_buffer) will depend on its two children, and is updated\nfrom bottom up for the right child.\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Args ||\n|---------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| `state` | `TreeState` for the current leaf node, index can be queried by [`tree_aggregation.get_step_idx(state.level_buffer_idx)`](../../tf_privacy/tree_aggregation/get_step_idx). |\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Returns ||\n|---|---|\n| Tuple of (noise, state) where `noise` is generated by tree aggregated protocol for the cumulative sum of streaming data, and `state` is the updated `TreeState`.. ||\n\n\u003cbr /\u003e\n\n### `init_state`\n\n[View source](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L407-L418) \n\n init_state() -\u003e ../../tf_privacy/tree_aggregation/TreeState\n\nReturns initial `TreeState`.\n\nInitializes `TreeState` for a tree of a single leaf node: the respective\ninitial node value in [`TreeState.level_buffer`](../../tf_privacy/tree_aggregation/TreeState#level_buffer) is generated by the value\ngenerator function, and the node index is 0.\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Returns ||\n|---|---|\n| An initialized `TreeState`. ||\n\n\u003cbr /\u003e\n\n### `reset_state`\n\n[View source](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/dp_query/tree_aggregation.py#L420-L422) \n\n reset_state(\n state: ../../tf_privacy/tree_aggregation/TreeState\n ) -\u003e ../../tf_privacy/tree_aggregation/TreeState\n\nReturns reset `TreeState` after restarting a new tree."]]
View source on GitHub