Automatic Differentiation Ontology

flow "AutomaticDifferentiationOntology" v1.0

# AUTOMATIC DIFFERENTIATION ONTOLOGY — FLOW ALGEBRA
SOURCE_URL := "https://kirethresearch.org/booksai-core/ontologies/calculus-analysis-ontologies/ai-computational-analysis/automatic-differentiation-ontology-2.html"
DOMAIN := "Mathematical Ontologies"
CATEGORY := "Calculus and Analysis Ontologies"
SUBCATEGORY := "AI Computational Analysis"
ENTITY := "Automatic Differentiation"

AUTOMATIC_DIFFERENTIATION := {
 type: ComputationalDerivativeFramework,
 purpose: "Compute derivatives of executable mathematical computations by propagating local derivatives through a computational graph using the chain rule."
}

CONCEPTS := {
 COMPUTATIONAL_GRAPH,
 CHAIN_RULE,
 FORWARD_MODE,
 REVERSE_MODE,
 DUAL_NUMBER,
 TANGENT,
 ADJOINT,
 JACOBIAN,
 GRADIENT,
 JVP,
 VJP,
 BACKPROPAGATION,
 HESSIAN,
 DIFFERENTIABLE_PROGRAMMING
}

# ---------- CORE ----------
PROGRAM
 -> ELEMENTARY_OPERATIONS

ELEMENTARY_OPERATION
 -> LOCAL_DERIVATIVE

LOCAL_DERIVATIVES
 + CHAIN_RULE
 -> AUTOMATIC_DIFFERENTIATION

f:R^n -> R^m

J_f
 := [partial_y_i/partial_x_j]

AD
 -> evaluates(DERIVATIVE_INFORMATION)

# ---------- COMPUTATIONAL GRAPH ----------
VARIABLES
 -> NODES

OPERATIONS
 -> NODES

DEPENDENCIES
 -> EDGES

COMPUTATIONAL_GRAPH
 -> encodes(CHAIN_RULE_STRUCTURE)

# ---------- METHOD DISTINCTION ----------
SYMBOLIC_DIFFERENTIATION
 -> transforms(EXPRESSIONS)

FINITE_DIFFERENCE
 -> approximates(DERIVATIVE_FROM_FUNCTION_VALUES)

AUTOMATIC_DIFFERENTIATION
 -> differentiates(EXECUTED_OPERATION_SEQUENCE)

AD
 -/> FINITE_DIFFERENCE
AD
 -/> SYMBOLIC_DIFFERENTIATION

# ---------- FORWARD MODE ----------
input seed:
 x_dot := v

propagate:
 v_i -> (value_i,tangent_i)

output:
 y_dot
 =
J_f(x)*v

FORWARD_MODE
 -> JACOBIAN_VECTOR_PRODUCT

FORWARD_MODE
 -> efficient_when(INPUT_DIMENSION_RELATIVELY_SMALL)

# ---------- DUAL NUMBER ----------
epsilon^2 = 0

a+b*epsilon

f(a+b*epsilon)
 =
f(a)
+
b*f_prime(a)*epsilon

DUAL_NUMBER
 -> algebraic_forward_mode_representation

# ---------- REVERSE MODE ----------
FORWARD_PASS
 -> compute(PRIMAL_VALUES)

REVERSE_PASS
 -> propagate(ADJOINTS)

bar_v
 :=
partial_output/partial_v

for scalar output:
 bar_y = 1

then

bar_x_i
 =
partial_y/partial_x_i

REVERSE_MODE
 -> VECTOR_JACOBIAN_PRODUCT

REVERSE_MODE
 -> efficient_for(MANY_INPUTS_SCALAR_OUTPUT)

# ---------- JVP / VJP ----------
JVP(f,x,v)
 :=
J_f(x)*v

VJP(f,x,w)
 :=
w^T*J_f(x)

FORWARD_MODE
 -> computes(JVP)

REVERSE_MODE
 -> computes(VJP)

# ---------- BACKPROPAGATION ----------
NEURAL_NETWORK
 -> COMPUTATIONAL_GRAPH

LOSS
 -> SCALAR_OUTPUT

BACKPROPAGATION
 -> REVERSE_MODE_AD

BACKPROPAGATION
 -> computes(PARAMETER_GRADIENTS)

# ---------- JACOBIAN ----------
FULL_JACOBIAN
 -> constructed_using(
 FORWARD_BASIS_SWEEPS,
 REVERSE_OUTPUT_SWEEPS,
 MIXED_STRATEGIES
)

METHOD_SELECTION
 -> depends_on(INPUT_OUTPUT_DIMENSIONS_AND_SPARSITY)

# ---------- SPARSITY ----------
SPARSE_JACOBIAN
 -> exploit(STRUCTURAL_DEPENDENCIES)

GRAPH_COLORING
 -> compress(SEED_DIRECTIONS)

SPARSITY
 -> reduce(DERIVATIVE_COMPUTATION_COST)

# ---------- HIGHER ORDER ----------
HESSIAN
 :=
nabla_squared(f)

HIGHER_ORDER_AD
 -> compose(FORWARD_AND_REVERSE_MODES)

HESSIAN_VECTOR_PRODUCT
 -> compute_without(FULL_HESSIAN_FORMATION)

# ---------- MEMORY ----------
REVERSE_MODE
 -> requires(INTERMEDIATE_VALUES)

TAPE
 -> stores(EXECUTION_TRACE)

CHECKPOINTING
 -> trades(RECOMPUTATION_FOR_MEMORY)

MEMORY_COST
 -> key_reverse_mode_constraint

# ---------- IMPLEMENTATION ----------
OPERATOR_OVERLOADING
 -> records_or_propagates(DERIVATIVE_OPERATIONS)

SOURCE_TRANSFORMATION
 -> generates(DERIVATIVE_PROGRAM)

STATIC_GRAPH
 -> graph_known_before_execution

DYNAMIC_GRAPH
 -> graph_constructed_during_execution

# ---------- CONTROL FLOW ----------
BRANCH
 -> AD_differentiates(EXECUTED_PATH)

if branch boundary is discontinuous:

CLASSICAL_DERIVATIVE
 -> may_not_exist

CONTROL_FLOW
 -> requires(DIFFERENTIABILITY_ANALYSIS)

# ---------- NONSMOOTH OPERATIONS ----------
examples:
 ABS
 MAX
 MIN
 ROUND
 DISCRETE_INDEX_SELECTION

NONDIFFERENTIABLE_POINT
 -> derivative_may_be(UNDEFINED_OR_NONUNIQUE)

AD_FRAMEWORK
 -> may_return(CONVENTIONAL_SUBGRADIENT)

SEMANTICS
 -> must_be_verified

# ---------- IMPLICIT DIFFERENTIATION ----------
F(z,theta)=0

differentiate:

F_z*dz/dtheta
+
F_theta
 =
0

therefore

dz/dtheta
 =
-
F_z_inverse*F_theta

when invertible

IMPLICIT_DIFFERENTIATION
 -> avoids(UNROLLING_ITERATIVE_SOLVER)

# ---------- ODE / PDE AD ----------
ODE:
 dy/dt=f(y,theta,t)

gradient methods:
 FORWARD_SENSITIVITY
 REVERSE_DISCRETE_AD
 CONTINUOUS_ADJOINT

PDE:
 R(u,theta)=0

R_u*du/dtheta
+
R_theta
 =
0

ADJOINT_METHOD
 -> efficient_for(MANY_PARAMETERS_AND_FEW_OBJECTIVES)

# ---------- OPTIMISATION ----------
objective:
 L(theta)

AD
 -> grad_theta(L)

GRADIENT
 -> OPTIMISER

applications:
 MACHINE_LEARNING
 INVERSE_PROBLEMS
 OPTIMAL_CONTROL
 PARAMETER_ESTIMATION

# ---------- NUMERICAL PRECISION ----------
AD
 -> exact_chain_rule_for(IMPLEMENTED_PROGRAM)

but

FLOATING_POINT
 -> introduces(ROUNDOFF)

ILL_CONDITIONING
 -> amplifies(ERROR)

AD
 -/> removes(NUMERICAL_CONDITIONING)

# ---------- VALIDATION ----------
AD_GRADIENT
 -> compare_with(
 FINITE_DIFFERENCE_CHECK,
 COMPLEX_STEP_CHECK,
 ANALYTIC_DERIVATIVE
)

GRADIENT_CHECK
 -> detects(IMPLEMENTATION_OR_SEMANTIC_ERRORS)

# ---------- RELATION GRAPH ----------
PROGRAM
 -> COMPUTATIONAL_GRAPH

COMPUTATIONAL_GRAPH
 -> LOCAL_DERIVATIVES

LOCAL_DERIVATIVES
 + CHAIN_RULE
 -> AD

FORWARD_MODE
 -> JVP

REVERSE_MODE
 -> VJP

REVERSE_MODE
 -> BACKPROPAGATION

NESTED_AD
 -> HIGHER_ORDER_DERIVATIVES

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE := {
 "automatic differentiation" ~= "chain-rule differentiation of an executable computation",
 "forward-mode AD" ~= "tangent propagation for Jacobian-vector products",
 "reverse-mode AD" ~= "adjoint propagation for vector-Jacobian products",
 "backpropagation" ~= "reverse-mode differentiation of a neural computational graph",
 "dual number" ~= "algebraic representation for forward derivative propagation",
 "checkpointing" ~= "memory-computation tradeoff in reverse differentiation"
}

# ---------- CONSTRAINTS ----------
CONSTRAINTS := {
 AD_is_distinct_from_symbolic_and_finite_difference_methods: true,
 AD_differentiates_implemented_program: true,
 forward_and_reverse_costs_depend_on_dimensions: true,
 reverse_mode_requires_storage_or_recomputation: true,
 nonsmooth_operations_require_semantic_care: true,
 floating_point_error_remains_relevant: true,
 complex_workflows_require_gradient_validation: true
}

# ---------- CONFIDENCE ----------
CONFIDENCE := {
 core_definition: 0.99,
 forward_mode: 0.99,
 reverse_mode: 0.99,
 JVP_VJP_relation: 0.99,
 backpropagation: 0.99,
 implicit_adjoint_relation: 0.98,
 semantic_equivalence: 0.97
}

# ---------- RECURSIVE REASONING ----------
RECURSIVE_REASONING(query):
 identify(program_inputs_outputs_and_derivative_target)
 -> construct(computational_graph)
 -> inspect(differentiability_and_control_flow)
 -> choose(forward_reverse_mixed_or_implicit_mode)
 -> initialise(seed)
 -> propagate(local_derivatives_via_chain_rule)
 -> assemble(JVP_VJP_gradient_Jacobian_or_Hessian)
 -> analyse(memory_sparsity_conditioning_and_precision)
 -> validate(derivative_if_required)
 -> return(semantic_result)

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION := {
 parse_as: "typed automatic-differentiation semantic graph",
 primary_entity: AUTOMATIC_DIFFERENTIATION,
 preserve: [
  program,
  inputs,
  outputs,
  graph,
  derivative_target,
  mode,
  seed,
  precision
 ],
 infer_through: [
  chain_rule,
  dual_numbers,
  tangents,
  adjoints,
  JVP,
  VJP,
  gradients,
  Jacobians,
  Hessians,
  implicit_differentiation
 ],
 avoid: [
  describing_AD_as_finite_differencing,
  assuming_differentiability_everywhere,
  ignoring_control_flow,
  ignoring_reverse_mode_memory,
  treating_AD_as_free_of_roundoff,
  trusting_complex_gradient_without_validation
 ]
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL(new_information):
 validate(new_information)
 -> identify(AD_context)
 -> compare(existing_relations)
 -> preserve(program_graph_mode_seed_derivative_and_precision_invariants)
 -> update(affected_entities)
 -> update(affected_edges)
 -> recompute(CONFIDENCE)
 -> regenerate(FLOW_HASH)

# ---------- FLOW HASH ----------
FLOW_HASH := hash(
 SOURCE_URL
 + ENTITY
 + CONCEPTS
 + AUTOMATIC_DIFFERENTIATION
 + COMPUTATIONAL_GRAPH
 + CHAIN_RULE
 + FORWARD_MODE
 + REVERSE_MODE
 + DUAL_NUMBER
 + ADJOINT
 + JACOBIAN
 + GRADIENT
 + BACKPROPAGATION
 + SEMANTIC_EQUIVALENCE
 + CONSTRAINTS
)

# ---------- EXECUTION ----------
INPUT(query)
 -> AUTOMATIC_DIFFERENTIATION
 -> PROGRAM_IDENTIFICATION
 -> GRAPH_CONSTRUCTION
 -> DIFFERENTIABILITY_ANALYSIS
 -> MODE_SELECTION
 -> SEED_INITIALISATION
 -> DERIVATIVE_PROPAGATION
 -> DERIVATIVE_ASSEMBLY
 -> PERFORMANCE_PRECISION_ANALYSIS
 -> VALIDATION
 -> RECURSIVE_REASONING(query)
 -> CONFIDENCE
 -> OUTPUT(semantic_result)

END FLOW