Soundness of symbolic reduction #
The symbolic semantics preserves typing and operation-domain safety while
replacing E samples by their means. Operational trace soundness builds on these
invariants in CompactFiberSoundness.
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.convex_integral_mem_real
{α : Type u_1}
[MeasurableSpace α]
{μ : MeasureTheory.Measure α}
[MeasureTheory.IsProbabilityMeasure μ]
{set : Set ℝ}
{value : α → ℝ}
(hConvex : Convex ℝ set)
(hMem : ∀ᵐ (x : α) ∂μ, value x ∈ set)
(hIntegrable : MeasureTheory.Integrable value μ)
:
noncomputable def
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.Affine.substituteHeadMean
{n : ℕ}
(expression : Symbolic.Affine (n + 1))
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
:
Equations
- One or more equations did not get rendered due to their size.
Instances For
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.Affine.eval_cons_convexCombination
{n : ℕ}
(expression : Symbolic.Affine (n + 1))
(environment : Env n)
(left right a b : ℝ)
(hSum : a + b = 1)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.Affine.eval_substituteHeadMean
{n : ℕ}
(expression : Symbolic.Affine (n + 1))
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
(environment : Env n)
:
(substituteHeadMean expression op affineArgs generalArgs).eval environment = expression.tail.eval environment + expression.2 0 * Spec.Paper.meanValue op
(fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs)
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.inDomain_valueSet_convex
{n : ℕ}
(queryOp : Spec.Paper.Op)
(queryAffineArgs : Fin (Spec.Paper.affineArity queryOp) → Symbolic.Affine (n + 1))
(queryGeneralArgs : Fin (Spec.Paper.generalArity queryOp) → ℝ)
(environment : Env n)
:
noncomputable def
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.transitionPack
{n : ℕ}
(laws : PrimitiveLaws)
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
:
SFiniteKernel (Env n) (Env (n + 1))
Equations
- One or more equations did not get rendered due to their size.
Instances For
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.transitionPack_apply
{n : ℕ}
(laws : PrimitiveLaws)
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
(environment : Env n)
:
(transitionPack laws op affineArgs generalArgs).kernel environment = MeasureTheory.Measure.map (fun (value : ℝ) => Env.cons value environment)
((laws.kernel op) (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs))
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.actualMeasure_univ_eq_one
{n : ℕ}
(laws : PrimitiveLaws)
(history : Symbolic.SampleEnv laws n)
(safe : Symbolic.SampleEnv.DomainSafe laws history)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.actualMeasure_snoc_eq_comp
{n : ℕ}
(laws : PrimitiveLaws)
(history : Symbolic.SampleEnv laws n)
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
:
Symbolic.SampleEnv.actualMeasure laws (history.snoc op affineArgs generalArgs) = (Symbolic.SampleEnv.actualMeasure laws history).bind ⇑(transitionPack laws op affineArgs generalArgs).kernel
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.integrable_eval_transition
{n : ℕ}
(laws : PrimitiveLaws)
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
(expression : Symbolic.Affine (n + 1))
(environment : Env n)
(InDomain :
Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs))
:
MeasureTheory.Integrable (fun (nextEnvironment : Env (n + 1)) => expression.eval nextEnvironment)
((transitionPack laws op affineArgs generalArgs).kernel environment)
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.integral_eval_transition
{n : ℕ}
(laws : PrimitiveLaws)
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
(expression : Symbolic.Affine (n + 1))
(environment : Env n)
(InDomain :
Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs))
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.SampleEnv.inDomain_meanEnvironment
{n : ℕ}
(laws : PrimitiveLaws)
(history : Symbolic.SampleEnv laws n)
(safe : Symbolic.SampleEnv.DomainSafe laws history)
(op : Spec.Paper.Op)
(affineArgs : Fin (Spec.Paper.affineArity op) → Symbolic.Affine n)
(generalArgs : Fin (Spec.Paper.generalArity op) → ℝ)
(domainAE :
∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.InDomain op (fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval environment, generalArgs))
:
Spec.Paper.InDomain op
(fun (i : Fin (Spec.Paper.affineArity op)) => (affineArgs i).eval (Symbolic.SampleEnv.meanEnvironment laws history), generalArgs)
def
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.SafeConfigAt
{n : ℕ}
(laws : PrimitiveLaws)
(fuel : ℕ)
(history : Symbolic.SampleEnv laws n)
(expression : Symbolic.AffineExpr n)
:
The source-side invariant used while replacing the recorded E draws by their sequential conditional means.
Equations
- One or more equations did not get rendered due to their size.
Instances For
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.inDomain_of_stochastic_mass_one
(laws : PrimitiveLaws)
(op : Spec.Paper.Op)
(params : Spec.Paper.Params op)
(mass : ((laws.kernel op) params) Set.univ = 1)
:
Spec.Paper.InDomain op params
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_mass_le_one
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Spec.Paper.Expr)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.ae_eq_one_of_lintegral_eq_one
{α : Type u_1}
[MeasurableSpace α]
(μ : MeasureTheory.Measure α)
(mass : μ Set.univ = 1)
(f : α → ENNReal)
(measurableF : Measurable f)
(bounded : ∀ (x : α), f x ≤ 1)
(integral : ∫⁻ (x : α), f x ∂μ = 1)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_univ_eq_one_of_value
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Spec.Paper.Expr)
(value : expression.isValue = true)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_succ_eq_firstStep
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Spec.Paper.Expr)
:
nStepMeasure stepKernel (fuel + 1) expression = (stepKernel.kernel expression).bind (nStepMeasure stepKernel fuel)
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_succ_sample_univ
{site : Spec.Paper.DistributionAction × Spec.Paper.Op}
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Spec.Paper.Expr)
(fiber : MeasureTheory.Measure ℝ)
(continuation : ℝ → Spec.Paper.Expr)
(reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample site fiber continuation)
:
(nStepMeasure stepKernel (fuel + 1) expression) Set.univ = ∫⁻ (value : ℝ), (nStepMeasure stepKernel fuel (continuation value)) Set.univ ∂fiber
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.nStepMeasure_succ_next_univ
(stepKernel : StepKernel)
(fuel : ℕ)
(expression next : Spec.Paper.Expr)
(reduction : Spec.Paper.reduce expression = Spec.Paper.Action.next next)
:
(nStepMeasure stepKernel (fuel + 1) expression) Set.univ = (nStepMeasure stepKernel fuel next) Set.univ
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.domainSafeAt_iff_nStepMeasure_univ_eq_one
{ty : Spec.Paper.Ty}
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Spec.Paper.Expr)
(typed : Spec.Paper.Typed [] expression ty)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.measurable_nStepMass_realize
{n : ℕ}
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Symbolic.AffineExpr n)
:
Measurable fun (environment : Env n) =>
(nStepMeasure stepKernel fuel (Symbolic.AffineExpr.realize environment expression)) Set.univ
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.measurableSet_domainSafeAt_realize
{n : ℕ}
{ty : Spec.Paper.Ty}
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Symbolic.AffineExpr n)
(typed : Symbolic.AffineExpr.WellTyped [] expression ty)
:
MeasurableSet {environment : Env n | Spec.Paper.DomainSafeAt fuel (Symbolic.AffineExpr.realize environment expression)}
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.exists_jointContinuation
{site : Spec.Paper.DistributionAction × Spec.Paper.Op}
{α : Type u_1}
[MeasurableSpace α]
{action : α → Spec.Paper.Action}
(family : MeasurableActionFamily α action)
:
∃ (joint : α × ℝ → Spec.Paper.Expr),
Measurable joint ∧ ∀ (parameter : α) (fiber : MeasureTheory.Measure ℝ) (continuation : ℝ → Spec.Paper.Expr),
action parameter = Spec.Paper.Action.sample site fiber continuation →
∀ (value : ℝ), joint (parameter, value) = continuation value
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.measurable_sampleG_joint_nStepMass
{n : ℕ}
{ty : Spec.Paper.Ty}
{site : Spec.Paper.DistributionAction × Spec.Paper.Op}
(laws : PrimitiveLaws)
(stepKernel : StepKernel)
(fuel : ℕ)
(expression : Symbolic.AffineExpr n)
(typed : Symbolic.AffineExpr.WellTyped [] expression ty)
(fiber : MeasureTheory.Measure ℝ)
(continuation : ℝ → Symbolic.AffineExpr n)
(reduction : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.sampleG site fiber continuation)
:
Measurable fun (pair : Env n × ℝ) =>
(nStepMeasure stepKernel fuel (Symbolic.AffineExpr.realize pair.1 (continuation pair.2))) Set.univ
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.not_value_of_reduce_sample
{site : Spec.Paper.DistributionAction × Spec.Paper.Op}
(expression : Spec.Paper.Expr)
(fiber : MeasureTheory.Measure ℝ)
(continuation : ℝ → Spec.Paper.Expr)
(reduction : Spec.Paper.reduce expression = Spec.Paper.Action.sample site fiber continuation)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.source_sampleG_safe_swap
{laws : PrimitiveLaws}
{n : ℕ}
{ty : Spec.Paper.Ty}
{site : Spec.Paper.DistributionAction × Spec.Paper.Op}
(stepKernel : StepKernel)
(fuel : ℕ)
(history : Symbolic.SampleEnv laws n)
(historySafe : Symbolic.SampleEnv.DomainSafe laws history)
(expression : Symbolic.AffineExpr n)
(typed : Symbolic.AffineExpr.WellTyped [] expression ty)
(sourceSafe :
∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.DomainSafeAt (fuel + 1) (Symbolic.AffineExpr.realize environment expression))
(fiber : MeasureTheory.Measure ℝ)
(continuation : ℝ → Symbolic.AffineExpr n)
(reduction : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.sampleG site fiber continuation)
:
fiber Set.univ = 1 ∧ ∀ᵐ (value : ℝ) ∂fiber, ∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.DomainSafeAt fuel (Symbolic.AffineExpr.realize environment (continuation value))
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.source_sampleE_safe_extension
{laws : PrimitiveLaws}
{n : ℕ}
{ty : Spec.Paper.Ty}
(stepKernel : StepKernel)
(fuel : ℕ)
(history : Symbolic.SampleEnv laws n)
(historySafe : Symbolic.SampleEnv.DomainSafe laws history)
(expression : Symbolic.AffineExpr n)
(typed : Symbolic.AffineExpr.WellTyped [] expression ty)
(sourceSafe :
∀ᵐ (environment : Env n) ∂Symbolic.SampleEnv.actualMeasure laws history, Spec.Paper.DomainSafeAt (fuel + 1) (Symbolic.AffineExpr.realize environment expression))
(op : Spec.Paper.Op)
(affine : List (Symbolic.Affine n))
(general : List ℝ)
(continuation : Symbolic.AffineExpr (n + 1))
(reduction : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.sampleE op affine general continuation)
:
have affineArgs := fun (index : Fin (Spec.Paper.affineArity op)) => affine.getD ↑index (0, fun (x : Fin n) => 0);
have generalArgs := fun (index : Fin (Spec.Paper.generalArity op)) => general.getD (↑index) 0;
have extended := history.snoc op affineArgs generalArgs;
Symbolic.SampleEnv.DomainSafe laws extended ∧ Symbolic.AffineExpr.WellTyped [] continuation ty ∧ ∀ᵐ (environment : Env (n + 1)) ∂Symbolic.SampleEnv.actualMeasure laws extended, Spec.Paper.DomainSafeAt fuel (Symbolic.AffineExpr.realize environment continuation)
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.determinize_isValue
(expression : Spec.Paper.Expr)
:
noncomputable def
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.targetRealize
{n : ℕ}
(environment : Env n)
:
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.targetRealize environment Determinize.Proof.Paper.Symbolic.AffineExpr.SymbolicAction.stuck = Determinize.Spec.Paper.Action.stuck
Instances For
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.determinize_shift
(amount cutoff : ℕ)
(expression : Spec.Paper.Expr)
:
(Spec.Paper.Expr.shift amount cutoff expression).determinize = Spec.Paper.Expr.shift amount cutoff expression.determinize
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.determinize_substAt
(depth : ℕ)
(replacement expression : Spec.Paper.Expr)
:
(Spec.Paper.Expr.substAt depth replacement expression).determinize = Spec.Paper.Expr.substAt depth replacement.determinize expression.determinize
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.determinize_substHead
(body replacement : Spec.Paper.Expr)
:
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.determinize_substTwo
(body argument function : Spec.Paper.Expr)
:
(body.substTwo argument function).determinize = body.determinize.substTwo argument.determinize function.determinize
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.targetRealize_wrap
{n : ℕ}
{ExprContext : Spec.Paper.Expr → Spec.Paper.Expr}
(action : Symbolic.AffineExpr.SymbolicAction n)
(environment : Env n)
(context : Symbolic.AffineExpr n → Symbolic.AffineExpr n)
(liftedContext : Symbolic.AffineExpr (n + 1) → Symbolic.AffineExpr (n + 1))
(context_realize :
∀ (expression : Symbolic.AffineExpr n),
(Symbolic.AffineExpr.realize environment (context expression)).determinize = ExprContext (Symbolic.AffineExpr.realize environment expression).determinize)
(lifted_realize :
∀ (expression : Symbolic.AffineExpr (n + 1)) (value : ℝ),
(Symbolic.AffineExpr.realize (Env.cons value environment) (liftedContext expression)).determinize = ExprContext (Symbolic.AffineExpr.realize (Env.cons value environment) expression).determinize)
:
targetRealize environment (Symbolic.AffineExpr.SymbolicAction.wrap context liftedContext action) = Spec.Paper.Action.wrap ExprContext (targetRealize environment action)
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.symbolicReduce_targetRealize
{n : ℕ}
{context : List Spec.Paper.Ty}
{ty : Spec.Paper.Ty}
{expression : Symbolic.AffineExpr n}
(typed : Symbolic.AffineExpr.WellTyped context expression ty)
(environment : Env n)
:
targetRealize environment expression.symbolicReduce = Spec.Paper.reduce (Symbolic.AffineExpr.realize environment expression).determinize
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.safeConfigAt_not_stuck
{laws : PrimitiveLaws}
{fuel a✝ : ℕ}
{history : Symbolic.SampleEnv laws a✝}
{expression : Symbolic.AffineExpr a✝}
(safe : SafeConfigAt laws (fuel + 1) history expression)
(notValue : expression.isValue ≠ true)
:
A valid mean call takes one deterministic step, using no additional sample coordinate.
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.source_mean_safe_step
{n : ℕ}
{ty : Spec.Paper.Ty}
{op : Spec.Paper.Op}
{affine : List (Symbolic.Affine n)}
{general : List ℝ}
{continuation : Symbolic.Affine n → Symbolic.AffineExpr n}
{fuel : ℕ}
(expression : Symbolic.AffineExpr n)
(typed : Symbolic.AffineExpr.WellTyped [] expression ty)
(actionEq : expression.symbolicReduce = Symbolic.AffineExpr.SymbolicAction.mean op affine general continuation)
(environment : Env n)
(safe : Spec.Paper.DomainSafeAt (fuel + 1) (Symbolic.AffineExpr.realize environment expression))
:
Spec.Paper.InDomain op (Symbolic.AffineExpr.meanParams op affine general environment) ∧ Spec.Paper.DomainSafeAt fuel
(Symbolic.AffineExpr.realize environment (continuation (Symbolic.AffineExpr.meanAffine op affine general)))
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.safeConfigAt_target
{laws : PrimitiveLaws}
{n : ℕ}
(stepKernel : StepKernel)
(fuel : ℕ)
(history : Symbolic.SampleEnv laws n)
(expression : Symbolic.AffineExpr n)
(safe : SafeConfigAt laws fuel history expression)
:
Spec.Paper.DomainSafeAt fuel
(Symbolic.AffineExpr.realize (Symbolic.SampleEnv.meanEnvironment laws history) expression).determinize
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.determinize_domainSafe_of_typed_source
(laws : PrimitiveLaws)
(stepKernel : StepKernel)
(program : Spec.Paper.Expr)
(typed : Spec.Paper.Typed [] program (Spec.Paper.Ty.float Spec.Paper.Affinity.E))
(sourceSafe : Spec.Paper.DomainSafe program)
:
Spec.Paper.DomainSafe program.determinize
theorem
Determinize.Proof.Paper.SymbolicSoundness.TargetSafety.bind_bind_const_swap
{alpha : Type u_1}
{beta : Type u_2}
{gamma : Type u_3}
[MeasurableSpace alpha]
[MeasurableSpace beta]
[MeasurableSpace gamma]
(left : MeasureTheory.Measure alpha)
(right : MeasureTheory.Measure beta)
[MeasureTheory.SFinite left]
[MeasureTheory.SFinite right]
(kernel : ProbabilityTheory.Kernel (alpha × beta) gamma)
: