🏛️ Atlas✒️Isabelle.TransformerAttentionPartI.TAF_Softmax view on GitHub ↗6 theorems
(* Title: Oscillation bound for the finite softmax   Author: Carles Marín (with Codex as formalization assistant)   Copyright (c) 2026 Carles Marín. License: Apache-2.0 *)theory TAF_Softmax  imports TAF_Tilt TAF_Exponential_Familybegin definition finite_softmax :: "'a set \<Rightarrow> ('a \<Rightarrow> real) \<Rightarrow> 'a \<Rightarrow> real" where  "finite_softmax S s i = exp (s i)/(\<Sum>j\<in>S. exp (s j))" lemma exponential_sum_positive:  fixes s :: "'a \<Rightarrow> real"  assumes "finite S" "S\<noteq>{}"  shows "0 < (\<Sum>i\<in>S. exp (s i))"  using sum_strict_mono[OF assms, where f="\<lambda>_. 0" and g="\<lambda>i. exp (s i)"] by simp lemma softmax_probability:  assumes "finite S" "S\<noteq>{}"  shows "finite_probability S (finite_softmax S s)"proof  show "finite S" by (rule assms(1))  show "0 \<le> finite_softmax S s i" if "i\<in>S" for i    using exponential_sum_positive[OF assms, where s=s]    by (simp add: finite_softmax_def)  show "sum (finite_softmax S s) S = 1"    using exponential_sum_positive[OF assms, where s=s]    by (simp add: finite_softmax_def sum_divide_distrib[symmetric])qed lemma softmax_shift:  "finite_softmax S (\<lambda>i. s i+c) = finite_softmax S s"  by (rule ext; simp add: finite_softmax_def exp_add sum_distrib_right[symmetric]) lemma softmax_as_tilt:  assumes fin: "finite S" and ne: "S\<noteq>{}"  shows "finite_softmax S (\<lambda>i. s i+r i) =    finite_tilt S (finite_softmax S s) (\<lambda>i. exp (r i-l))"proof -  let ?Z = "\<Sum>i\<in>S. exp (s i)"  let ?Zr = "\<Sum>i\<in>S. exp (s i+r i)"  have Z: "?Z\<noteq>0"    using exponential_sum_positive[OF fin ne, where s=s] by linarith  have Zr: "?Zr\<noteq>0"    using exponential_sum_positive[OF fin ne, where s="\<lambda>i. s i+r i"] by linarith  have point_eq: "finite_softmax S s i*exp (r i-l) = exp (s i+r i)/(exp l*?Z)" for i    by (simp add: finite_softmax_def exp_add exp_diff algebra_simps)  have m: "fw_mean S (finite_softmax S s) (\<lambda>i. exp (r i-l)) = ?Zr/(exp l*?Z)"    by (simp add: fw_mean_def point_eq sum_divide_distrib[symmetric])  have tiltpoint: "finite_tilt S (finite_softmax S s) (\<lambda>i. exp (r i-l)) i =    exp (s i+r i)/?Zr" for i    unfolding finite_tilt_def    by (simp only: m point_eq; use Z Zr in simp)  show ?thesis by (rule ext; simp only: tiltpoint finite_softmax_def)qed lemma tanh_half_exp:  fixes x :: real  shows "tanh (x/2) = (exp x-1)/(exp x+1)"proof -  have e: "exp x\<noteq>0" by simp  have dp: "0<exp x+1" by (rule add_pos_pos; simp)  have den: "exp x+1\<noteq>0" using dp by linarith  have exponent: "-2*(x/2)=-x" by simp  have ei: "exp (-2*(x/2))=1/exp x" by (simp only: exponent exp_minus')  have num: "1-1/exp x=(exp x-1)/exp x" using e by (simp add: diff_divide_distrib)  have denom: "1+1/exp x=(exp x+1)/exp x" using e by (simp add: add_divide_distrib)  show ?thesis    by (simp only: tanh_real_altdef ei num denom; simp)qed lemma softmax_oscillation_bound:  assumes fin: "finite S" and ne: "S\<noteq>{}"    and lo: "\<And>i. i\<in>S \<Longrightarrow> l \<le> r i"    and hi: "\<And>i. i\<in>S \<Longrightarrow> r i \<le> u"  shows "tv_distance S (finite_softmax S s) (finite_softmax S (\<lambda>i. s i+r i))    \<le> tanh ((u-l)/4)"proof -  interpret p: finite_probability S "finite_softmax S s"    by (rule softmax_probability[OF fin ne])  obtain i where "i\<in>S" using ne by blast  then have lu: "l\<le>u" using lo hi by force  show ?thesis  proof (cases "l=u")    case True    have pt: "finite_softmax S (\<lambda>i. s i+r i) j = finite_softmax S s j" if "j\<in>S" for j    proof -      have eq: "r i=l" if "i\<in>S" for i using lo[OF that] hi[OF that] True by linarith      have denom: "(\<Sum>i\<in>S. exp (s i+r i)) = (\<Sum>i\<in>S. exp (s i+l))"        by (rule sum.cong[OF refl]; simp add: eq)      show ?thesis using eq[OF that]        by (simp only: finite_softmax_def denom; simp add: exp_add sum_distrib_right[symmetric])    qed    show ?thesis using True by (simp add: tv_distance_def pt)  next    case False    have lt: "l<u" using lu False by auto    have ul: "0 < (u-l)/2" using lt by simp    let ?t = "exp ((u-l)/2)"    have t: "1 < ?t" using ul by simp    have square: "?t^2 = exp (u-l)"      by (simp add: power2_eq_square exp_add[symmetric])    have yl: "1 \<le> exp (r i-l)" if "i\<in>S" for i using lo[OF that] by simp    have yh: "exp (r i-l) \<le> ?t^2" if "i\<in>S" for i using hi[OF that] by (simp add: square)    have bound: "tv_distance S (finite_softmax S s)      (finite_tilt S (finite_softmax S s) (\<lambda>i. exp (r i-l))) \<le> (?t-1)/(?t+1)"      by (rule p.tilt_tv_bound[where t="?t" and Y="\<lambda>i. exp (r i-l)", OF t yl yh])    have eq: "(?t-1)/(?t+1) = tanh ((u-l)/4)"      using tanh_half_exp[where x="(u-l)/2"] by simp    show ?thesis using bound eq softmax_as_tilt[OF fin ne, where s=s and r=r and l=l] by simp  qedqed end