Image moment

In image processing, computer vision and related fields, an image moment is a certain particular weighted average (moment) of the image pixels' intensities, or a function of such moments, usually chosen to have some attractive property or interpretation. Image moments are useful to describe objects after segmentation. Simple properties of the image which are found via image moments include area (or total intensity), its centroid, and information about its orientation. == Raw moments == For a 2D continuous function f(x,y) the moment (sometimes called "raw moment") of order (p + q) is defined as M p q = ∫ − ∞ ∞ ∫ − ∞ ∞ x p y q f ( x , y ) d x d y {\displaystyle M_{pq}=\int \limits _{-\infty }^{\infty }\int \limits _{-\infty }^{\infty }x^{p}y^{q}f(x,y)\,dx\,dy} for p,q = 0,1,2,... Adapting this to scalar (grayscale) image with pixel intensities I(x,y), raw image moments Mij are calculated by M i j = ∑ x ∑ y x i y j I ( x , y ) {\displaystyle M_{ij}=\sum _{x}\sum _{y}x^{i}y^{j}I(x,y)\,\!} In some cases, this may be calculated by considering the image as a probability density function, i.e., by dividing the above by ∑ x ∑ y I ( x , y ) {\displaystyle \sum _{x}\sum _{y}I(x,y)\,\!} A uniqueness theorem states that if f(x,y) is piecewise continuous and has nonzero values only in a finite part of the xy plane, moments of all orders exist, and the moment sequence (Mpq) is uniquely determined by f(x,y). Conversely, (Mpq) uniquely determines f(x,y). In practice, the image is summarized with functions of a few lower order moments. === Examples === Simple image properties derived via raw moments include: Area (for binary images) or sum of grey level (for greytone images): M 00 {\displaystyle M_{00}} Centroid: { x ¯ , y ¯ } = { M 10 M 00 , M 01 M 00 } {\displaystyle \{{\bar {x}},\ {\bar {y}}\}=\left\{{\frac {M_{10}}{M_{00}}},{\frac {M_{01}}{M_{00}}}\right\}} == Central moments == Central moments are defined as μ p q = ∫ − ∞ ∞ ∫ − ∞ ∞ ( x − x ¯ ) p ( y − y ¯ ) q f ( x , y ) d x d y {\displaystyle \mu _{pq}=\int \limits _{-\infty }^{\infty }\int \limits _{-\infty }^{\infty }(x-{\bar {x}})^{p}(y-{\bar {y}})^{q}f(x,y)\,dx\,dy} where x ¯ = M 10 M 00 {\displaystyle {\bar {x}}={\frac {M_{10}}{M_{00}}}} and y ¯ = M 01 M 00 {\displaystyle {\bar {y}}={\frac {M_{01}}{M_{00}}}} are the components of the centroid. If ƒ(x, y) is a digital image, then the previous equation becomes μ p q = ∑ x ∑ y ( x − x ¯ ) p ( y − y ¯ ) q f ( x , y ) {\displaystyle \mu _{pq}=\sum _{x}\sum _{y}(x-{\bar {x}})^{p}(y-{\bar {y}})^{q}f(x,y)} The central moments of order up to 3 are: μ 00 = M 00 , μ 01 = 0 , μ 10 = 0 , μ 11 = M 11 − x ¯ M 01 = M 11 − y ¯ M 10 , μ 20 = M 20 − x ¯ M 10 , μ 02 = M 02 − y ¯ M 01 , μ 21 = M 21 − 2 x ¯ M 11 − y ¯ M 20 + 2 x ¯ 2 M 01 , μ 12 = M 12 − 2 y ¯ M 11 − x ¯ M 02 + 2 y ¯ 2 M 10 , μ 30 = M 30 − 3 x ¯ M 20 + 2 x ¯ 2 M 10 , μ 03 = M 03 − 3 y ¯ M 02 + 2 y ¯ 2 M 01 . {\displaystyle {\begin{aligned}\mu _{00}&=M_{00},&\mu _{01}&=0,\\\mu _{10}&=0,&\mu _{11}&=M_{11}-{\bar {x}}M_{01}=M_{11}-{\bar {y}}M_{10},\\\mu _{20}&=M_{20}-{\bar {x}}M_{10},&\mu _{02}&=M_{02}-{\bar {y}}M_{01},\\\mu _{21}&=M_{21}-2{\bar {x}}M_{11}-{\bar {y}}M_{20}+2{\bar {x}}^{2}M_{01},&\mu _{12}&=M_{12}-2{\bar {y}}M_{11}-{\bar {x}}M_{02}+2{\bar {y}}^{2}M_{10},\\\mu _{30}&=M_{30}-3{\bar {x}}M_{20}+2{\bar {x}}^{2}M_{10},&\mu _{03}&=M_{03}-3{\bar {y}}M_{02}+2{\bar {y}}^{2}M_{01}.\end{aligned}}} It can be shown that: μ p q = ∑ m p ∑ n q ( p m ) ( q n ) ( − x ¯ ) ( p − m ) ( − y ¯ ) ( q − n ) M m n {\displaystyle \mu _{pq}=\sum _{m}^{p}\sum _{n}^{q}{p \choose m}{q \choose n}(-{\bar {x}})^{(p-m)}(-{\bar {y}})^{(q-n)}M_{mn}} Central moments are translational invariant. === Examples === Information about image orientation can be derived by first using the second order central moments to construct a covariance matrix. μ 20 ′ = μ 20 / μ 00 = M 20 / M 00 − x ¯ 2 μ 02 ′ = μ 02 / μ 00 = M 02 / M 00 − y ¯ 2 μ 11 ′ = μ 11 / μ 00 = M 11 / M 00 − x ¯ y ¯ {\displaystyle {\begin{aligned}\mu '_{20}&=\mu _{20}/\mu _{00}=M_{20}/M_{00}-{\bar {x}}^{2}\\\mu '_{02}&=\mu _{02}/\mu _{00}=M_{02}/M_{00}-{\bar {y}}^{2}\\\mu '_{11}&=\mu _{11}/\mu _{00}=M_{11}/M_{00}-{\bar {x}}{\bar {y}}\end{aligned}}} The covariance matrix of the image I ( x , y ) {\displaystyle I(x,y)} is now cov ⁡ [ I ( x , y ) ] = [ μ 20 ′ μ 11 ′ μ 11 ′ μ 02 ′ ] . {\displaystyle \operatorname {cov} [I(x,y)]={\begin{bmatrix}\mu '_{20}&\mu '_{11}\\\mu '_{11}&\mu '_{02}\end{bmatrix}}.} The eigenvectors of this matrix correspond to the major and minor axes of the image intensity, so the orientation can thus be extracted from the angle of the eigenvector associated with the largest eigenvalue towards the axis closest to this eigenvector. It can be shown that this angle Θ is given by the following formula: Θ = 1 2 arctan ⁡ ( 2 μ 11 ′ μ 20 ′ − μ 02 ′ ) {\displaystyle \Theta ={\frac {1}{2}}\arctan \left({\frac {2\mu '_{11}}{\mu '_{20}-\mu '_{02}}}\right)} The above formula holds as long as: μ 20 ′ − μ 02 ′ ≠ 0 {\displaystyle \mu '_{20}-\mu '_{02}\neq 0} The eigenvalues of the covariance matrix can easily be shown to be λ i = μ 20 ′ + μ 02 ′ 2 ± 4 μ ′ 11 2 + ( μ ′ 20 − μ ′ 02 ) 2 2 , {\displaystyle \lambda _{i}={\frac {\mu '_{20}+\mu '_{02}}{2}}\pm {\frac {\sqrt {4{\mu '}_{11}^{2}+({\mu '}_{20}-{\mu '}_{02})^{2}}}{2}},} and are proportional to the squared length of the eigenvector axes. The relative difference in magnitude of the eigenvalues are thus an indication of the eccentricity of the image, or how elongated it is. The eccentricity is 1 − λ 2 λ 1 . {\displaystyle {\sqrt {1-{\frac {\lambda _{2}}{\lambda _{1}}}}}.} == Moment invariants == Moments are well-known for their application in image analysis, since they can be used to derive invariants with respect to specific transformation classes. The term invariant moments is often abused in this context. However, while moment invariants are invariants that are formed from moments, the only moments that are invariants themselves are the central moments. Note that the invariants detailed below are exactly invariant only in the continuous domain. In a discrete domain, neither scaling nor rotation are well defined: a discrete image transformed in such a way is generally an approximation, and the transformation is not reversible. These invariants therefore are only approximately invariant when describing a shape in a discrete image. === Translation invariants === The central moments μi j of any order are, by construction, invariant with respect to translations. === Scale invariants === Invariants ηi j with respect to both translation and scale can be constructed from central moments by dividing through a properly scaled zero-th central moment: η i j = μ i j μ 00 ( 1 + i + j 2 ) {\displaystyle \eta _{ij}={\frac {\mu _{ij}}{\mu _{00}^{\left(1+{\frac {i+j}{2}}\right)}}}\,\!} where i + j ≥ 2. Note that translational invariance directly follows by only using central moments. === Rotation invariants === As shown in the work of Hu, invariants with respect to translation, scale, and rotation can be constructed: I 1 = η 20 + η 02 {\displaystyle I_{1}=\eta _{20}+\eta _{02}} I 2 = ( η 20 − η 02 ) 2 + 4 η 11 2 {\displaystyle I_{2}=(\eta _{20}-\eta _{02})^{2}+4\eta _{11}^{2}} I 3 = ( η 30 − 3 η 12 ) 2 + ( 3 η 21 − η 03 ) 2 {\displaystyle I_{3}=(\eta _{30}-3\eta _{12})^{2}+(3\eta _{21}-\eta _{03})^{2}} I 4 = ( η 30 + η 12 ) 2 + ( η 21 + η 03 ) 2 {\displaystyle I_{4}=(\eta _{30}+\eta _{12})^{2}+(\eta _{21}+\eta _{03})^{2}} I 5 = ( η 30 − 3 η 12 ) ( η 30 + η 12 ) [ ( η 30 + η 12 ) 2 − 3 ( η 21 + η 03 ) 2 ] + ( 3 η 21 − η 03 ) ( η 21 + η 03 ) [ 3 ( η 30 + η 12 ) 2 − ( η 21 + η 03 ) 2 ] {\displaystyle I_{5}=(\eta _{30}-3\eta _{12})(\eta _{30}+\eta _{12})[(\eta _{30}+\eta _{12})^{2}-3(\eta _{21}+\eta _{03})^{2}]+(3\eta _{21}-\eta _{03})(\eta _{21}+\eta _{03})[3(\eta _{30}+\eta _{12})^{2}-(\eta _{21}+\eta _{03})^{2}]} I 6 = ( η 20 − η 02 ) [ ( η 30 + η 12 ) 2 − ( η 21 + η 03 ) 2 ] + 4 η 11 ( η 30 + η 12 ) ( η 21 + η 03 ) {\displaystyle I_{6}=(\eta _{20}-\eta _{02})[(\eta _{30}+\eta _{12})^{2}-(\eta _{21}+\eta _{03})^{2}]+4\eta _{11}(\eta _{30}+\eta _{12})(\eta _{21}+\eta _{03})} I 7 = ( 3 η 21 − η 03 ) ( η 30 + η 12 ) [ ( η 30 + η 12 ) 2 − 3 ( η 21 + η 03 ) 2 ] − ( η 30 − 3 η 12 ) ( η 21 + η 03 ) [ 3 ( η 30 + η 12 ) 2 − ( η 21 + η 03 ) 2 ] . {\displaystyle I_{7}=(3\eta _{21}-\eta _{03})(\eta _{30}+\eta _{12})[(\eta _{30}+\eta _{12})^{2}-3(\eta _{21}+\eta _{03})^{2}]-(\eta _{30}-3\eta _{12})(\eta _{21}+\eta _{03})[3(\eta _{30}+\eta _{12})^{2}-(\eta _{21}+\eta _{03})^{2}].} These are well-known as Hu moment invariants. The first one, I1, is analogous to the moment of inertia around the image's centroid, where the pixels' intensities are analogous to physical density. The first six, I1 ... I6, are reflection symmetric, i.e. they are unchanged if the image is changed to a mirror image. The last one, I7, is reflection antisymmetric (changes sign under reflection), which enables it to distinguish mirror images of otherwise identical im

Afghan Girls Robotics Team

The Afghan Girls Robotics Team, also known as the Afghan Dreamers, is an all-girl robotics team from Herat, Afghanistan, founded through the Digital Citizen Fund (DCF) in 2017 by Roya Mahboob and Alireza Mehraban. It is made up of girls between ages 12 and 18 and their mentors. Several members of the team were relocated to Qatar and Mexico by humanitarian and tech entrepreneur Sarah Porter following the fall of Kabul in August 2021. A documentary film featuring members of the team, titled Afghan Dreamers, was released by MTV Documentary Films in 2023. == Origins == The Afghan Girls Robotics Team was co-founded in 2017 by Roya Mahboob, who is their coach, mentor and sponsor, and founder of the Digital Citizen Fund (DCF), which is the parent organization for the team. Dean Kamen was planning a 2017 competition in the United States and had recruited Mahboob to form a team from Afghanistan. Out of 150 girls, 12 were selected for the first team. Before parts were sent by Kamen, they trained in the basement of the home of Mahboob's parents, with scrap metal and without safety equipment under the guidance of their coach, Mahboob's brother Alireza Mehraban, who is also a co-founder of the team. == 2017 and 2018 == In 2017, six members of the Afghan Girls Robotics Team traveled to the United States to participate in the international FIRST Global Challenge robotics competition. Their visas were rejected twice after they made two journeys from Herat to Kabul through Taliban-controlled areas, before officials in the United States government intervened to allow them to enter the United States. Customs officials also detained their robotics kits, which left them two weeks to construct their robot, unlike some teams that had more time. They were awarded a Silver medal for Courageous Achievement. One week after they returned home from the competition, the father of team captain Fatemah Qaderyan, Mohammad Asif Qaderyan, was killed in a suicide bombing. After their United States visas expired, the team participated in competitions in Estonia and Istanbul. Three of the 12 members participated in the 2017 Entrepreneurial Challenge at the Robotex festival in Estonia, and won the competition for their solar-powered robot designed to assist farmers. In 2018, the team trained in Canada, continued to travel in the United States for months and participate in competitions. == 2019 == The Afghan Girls Robotics team had aspirations to develop a science and technology school for girls in Afghanistan. Roya Mahboob interfaced with the School of Engineering and Applied Sciences (SEAS), the School of Architecture, and the Whitney and Betty MacMillan Center for International and Area Studies Yale University to design the infrastructure for what they named The Dreamer Institute. == 2020 == In March 2020, the governor of Herat at the time, in response to the COVID-19 pandemic in Afghanistan and a scarcity of ventilators, sought help with the design of low-cost ventilators, and the Afghan Girls Robotics Team was one of six teams contacted by the government. Using a design from Massachusetts Institute of Technology and with guidance from MIT engineers and Douglas Chin, a surgeon in California, the team developed a prototype with Toyota Corolla parts and a chain drive from a Honda motorcycle. UNICEF also supported the team with the acquisition of necessary parts during the three months they spent building the prototype that was completed in July 2020. Their design costs around $500 compared to $50,000 for a ventilator. In December 2020, Minister of Industry and Commerce Nizar Ahmad Ghoryani donated funding and obtained land for a factory to produce the ventilators. Under the direction of their mentor Roya Mahboob, the Afghan Dreamers also designed a UVC Robot for sanitization, and a Spray Robot for disinfection, both of which were approved by the Ministry of Health for production. == 2021 == In early August 2021, Somaya Faruqi, former captain of the team, was quoted by Public Radio International about the future of Afghanistan, stating, "We don’t support any group over another but for us what’s important is that we be able to continue our work. Women in Afghanistan have made a lot of progress over the past two decades and this progress must be respected." On August 17, 2021, the Afghan Girls Robotics Team and their coaches were reported to be attempting to evacuate, but unable to obtain a flight out of Afghanistan, and a lawyer appealed to Canada for assistance regarding the evacuation of the team members. As of August 19, 2021, nine members of the team and their coaches had evacuated to Qatar. The founder of the team, Roya Mahboob, and DCF board member, Elizabeth Schaeffer Brown, were previously in contact with the Qatari government to assist the team members in their evacuation from Afghanistan. By August 25, 2021, some members arrived in Mexico. Saghar, a team member who evacuated to Mexico, said, "We wanted to continue the path that we started to continue to go for our achievements and to go for having our dreams through reality. So that's why we decided to leave Afghanistan and go for somewhere safe" in an interview with The Associated Press. The members who have left Afghanistan participated in an online robotics competition in September and plan to continue their education. A documentary film titled Afghan Dreamers, produced by Beth Murphy and directed by David Greenwald, was in post-production when the team began to evacuate. == 2022 == The Afghan Dreamers were involved in a training program at the Texas A&M University at Qatar’s STEM Hub. == 2023 == The Afghan Girls Robotics Team had a booth at the 5th UN Conference on the Least Developed Countries, where they displayed some of the robots the team had constructed. == Afghan Dreamers documentary == The Afghan Dreamers documentary from MTV Documentary Films premiered in May 2023 on Paramount+. The film was directed by David Greenwald and produced by David Cowan and Beth Murphy. In a review for Screen Daily, Wendy Ide wrote, "This film, with its likeable cast of girl nerds and positive message, should enjoy a warm reception on the festival circuit, and will be of particular interest to events seeking to showcase women's stories from around the world. It also serves as a timely cautionary tale – a case study on just how quickly the rights and the opportunities of women can be curtailed, at the behest of the men in power." == Honors and awards == 2017 Silver medal for Courageous Achievement at the FIRST Global Challenge, science and technology 2017 Benefiting Humanity in AI Award at World Summit AI 2017 Winner, Entrepreneurship Challenge at Robotex in Estonia 2018 Permission to Dream Award, Raw Film Festival 2018 Conrad Innovation Challenge, Raw Film Festival 2018 Rookie All Star – District Championship, Canada 2018 Asia Game Changer Award Honoree 2019 Inspiring in Engineering Award – FIRST Detroit World Championship 2019 Asia Game Changer Award of California 2019 Safety Award – FIRST Global, Dubai 2021 Forbes 30 Under 30 Asia 2022 World Championships, Genoa, Switzerland

Lai–Robbins lower bound

The Lai–Robbins lower bound gives an asymptotic lower bound on the regret that any uniformly good algorithm must incur in the stochastic multi-armed bandit problem. The original result was proved by Tze Leung Lai and Herbert Robbins in 1985 for parametric exponential families. Later work extended the statement to more general classes of distributions. == Multi-armed bandit problem == The multi-armed bandit problem (MAB) is a sequential game in which the player must trade off exploration (to learn) and exploitation (to earn). The player chooses among K {\displaystyle K} actions (arms) with unknown distributions ν = ( ν 1 , … , ν K ) {\displaystyle \nu =(\nu _{1},\dots ,\nu _{K})} . The player is assumed to know a class of distributions D {\displaystyle {\mathcal {D}}} such that for every k {\displaystyle k} one has ν k ∈ D {\displaystyle \nu _{k}\in {\mathcal {D}}} (for example, D {\displaystyle {\mathcal {D}}} may be the family of Gaussian or Bernoulli distributions). At each round t = 1 , … , T {\displaystyle t=1,\dots ,T} the player selects (pulls) an arm a t {\displaystyle a_{t}} and observes a reward X t ∼ ν a t {\displaystyle X_{t}\sim \nu _{a_{t}}} . We denote N a ( t ) := ∑ s = 1 t 1 { a s = a } {\displaystyle N_{a}(t):=\sum _{s=1}^{t}\mathbf {1} _{\{a_{s}=a\}}} the number of times arm a {\displaystyle a} has been pulled in the first t {\displaystyle t} rounds, μ ( ν ) := ( μ 1 , … , μ K ) {\displaystyle \mu (\nu ):=(\mu _{1},\dots ,\mu _{K})} the vector of arm means, where μ k = E X ∼ ν k [ X ] {\displaystyle \mu _{k}=\mathbb {E} _{X\sim \nu _{k}}[X]} , μ ∗ := max a μ a {\displaystyle \mu ^{}:=\max _{a}\mu _{a}} the highest mean Δ a := μ ∗ − μ a ≥ 0 {\displaystyle \Delta _{a}:=\mu ^{}-\mu _{a}\geq 0} the gap of arm a {\displaystyle a} . An arm a {\displaystyle a} with μ a = μ ∗ {\displaystyle \mu _{a}=\mu ^{}} is called an optimal arm; otherwise it is a suboptimal arm. The goal is to minimize the regret at horizon T {\displaystyle T} , defined by R T := ∑ a = 1 K Δ a E [ N a ( T ) ] . {\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\,\mathbb {E} [N_{a}(T)].} Intuitively, the regret is the (expected) total loss compared to always playing an optimal arm: regret = ∑ a ( cost of playing a ) × ( times a is played ) . {\displaystyle {\text{regret}}=\sum _{a}\ ({\text{cost of playing }}a)\times ({\text{times }}a{\text{ is played}}).} An MAB algorithm is a (possibly randomized) policy that, at each round t {\displaystyle t} , choose an arm a_t by using the observations received from previous turns. === Intuitive example === Suppose a farmer must choose, each year, one of K {\displaystyle K} seed varieties to plant. Each variety k {\displaystyle k} has an unknown average yield μ k {\displaystyle \mu _{k}} . If the farmer knew the best variety (with mean μ ∗ {\displaystyle \mu ^{}} ) he would plant it every year; in reality he must try varieties to learn which is best. The cumulative regret after T {\displaystyle T} years measures the total expected loss in yield due to imperfect knowledge. Remarks The model above is the stochastic MAB; there also exist adversarial variants. One may consider a fixed-horizon setting (known T {\displaystyle T} ) or an anytime setting (unknown T {\displaystyle T} ). == Lai–Robbins lower bound == The theorem gives the right amount of time we should pull a suboptimal arm k {\displaystyle k} to distinguish whether we are in the instance with ν k {\displaystyle \nu _{k}} or with ν ~ k {\displaystyle {\tilde {\nu }}_{k}} where ν ~ k {\displaystyle {\tilde {\nu }}_{k}} is such that μ ~ k > μ ∗ {\displaystyle {\tilde {\mu }}_{k}>\mu ^{}} . Knowning a lower bound on the number of pull of every suboptimal arm gives a lower bound on the regret as only suboptimal arms contribute to the regret. Before stating the formal theorem we need to define what is a consistent algorithm. === Consistency (uniformly good algorithms) === Let D {\displaystyle {\mathcal {D}}} be a class of probability distributions and consider K {\displaystyle K} arms with reward distributions ν = ( ν 1 , … , ν K ) ∈ D K {\displaystyle \nu =(\nu _{1},\dots ,\nu _{K})\in {\mathcal {D}}^{K}} . An algorithm is said to be consistent (also called uniformly good) on D K {\displaystyle {\mathcal {D}}^{K}} if, for every instance ν ∈ D K {\displaystyle \nu \in {\mathcal {D}}^{K}} , the expected regret R T ( ν ) {\displaystyle R_{T}(\nu )} grows subpolynomially: ∀ α > 0 , R T ( ν ) = o ( T α ) as T → ∞ {\displaystyle \forall \alpha >0,\qquad R_{T}(\nu )=o(T^{\alpha })\quad {\text{as }}T\to \infty } This assumption excludes algorithms that perform well on some instances but incur linear regret on others. === Formal lower bound === For any suboptimal arm a {\displaystyle a} . For a distribution ν a ∈ D {\displaystyle \nu _{a}\in {\mathcal {D}}} and a threshold x {\displaystyle x} , define K inf ( ν a , x , D ) := inf { KL ⁡ ( ν a , ν ′ ) : ν ′ ∈ D , μ ′ > x } {\displaystyle {\mathcal {K}}_{\inf }(\nu _{a},x,{\mathcal {D}}):=\inf {\Bigl \{}\operatorname {KL} (\nu _{a},\nu '):\nu '\in {\mathcal {D}},\ \mu '>x{\Bigr \}}} where KL ⁡ ( ⋅ , ⋅ ) {\displaystyle \operatorname {KL} (\cdot ,\cdot )} denotes the Kullback-Leibler divergence. Then, for any algorithm consistent on D K {\displaystyle {\mathcal {D}}^{K}} and for every instance ν ∈ D K {\displaystyle \nu \in {\mathcal {D}}^{K}} , every suboptimal arm a {\displaystyle a} satisfies E ν [ N a ( T ) ] ≥ ln ⁡ T K inf ( ν a , μ ∗ , D ) + o ( ln ⁡ T ) {\displaystyle \mathbb {E} _{\nu }[N_{a}(T)]\geq {\frac {\ln T}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{},{\mathcal {D}})}}+o(\ln T)} Consequently, the regret satisfies R T ( ν ) ≥ ( ∑ a : μ a < μ ∗ Δ a K inf ( ν a , μ ∗ , D ) ) ln ⁡ T + o ( ln ⁡ T ) {\displaystyle R_{T}(\nu )\geq \left(\sum _{a:\,\mu _{a}<\mu ^{}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{},{\mathcal {D}})}}\right)\ln T+o(\ln T)} The original 1985 paper established this result for exponential families; later work showed that the bound holds under much weaker assumptions on D {\displaystyle {\mathcal {D}}} . === Intuition === Consistency imposes that, for every ν {\displaystyle \nu } , the number of pulls of an optimal arm must be large. This means that μ ∗ {\displaystyle \mu ^{}} is estimated very accurately. The goal is to determine, for a suboptimal arm k {\displaystyle k} , how many samples are needed to be confident, with the appropriate level of confidence, that μ k < μ ∗ {\displaystyle \mu _{k}<\mu ^{}} . To do so, we use what is called the most confusing instance: an instance close to ν {\displaystyle \nu } such that arm k {\displaystyle k} is optimal. We define it as ν ~ {\displaystyle {\tilde {\nu }}} such that, for all a ≠ k {\displaystyle a\neq k} , ν ~ a = ν a {\displaystyle {\tilde {\nu }}_{a}=\nu _{a}} , and ν ~ k {\displaystyle {\tilde {\nu }}_{k}} is chosen so that μ ~ k > μ ∗ {\displaystyle {\tilde {\mu }}_{k}>\mu ^{}} . The objective is to determine how many samples of arm k {\displaystyle k} are required to distinguish whether we are in the instance with ν k {\displaystyle \nu _{k}} or with ν ~ k {\displaystyle {\tilde {\nu }}_{k}} in terms of KL {\displaystyle \operatorname {KL} } distance. == Algorithms achieving the Lai–Robbins lower bound == Several algorithms are known to achieve the Lai–Robbins asymptotic lower bound under specific assumptions on the reward distribution class D {\displaystyle {\mathcal {D}}} . The following list summarizes a non-exhaustive list of algorithms matching the lower bound. == Extension to other problems == === Structured bandit === A more complexe is structured bandit where we know that the mean of each arm is in a set with some restriction. In this case we can prove a smaller lower bound that use the knowledge of this set. === Best arm identification (BAI) === A similar result has been proved for best arm identification, which is the same game except that, instead of minimizing the regret, the goal is to identify the best arm with probability 1 − δ {\displaystyle 1-\delta } using as few rounds as possible. === Reinforcement Learning (RL) === Similar results have been proved for regret minimization in average-reward reinforcement learning. The order is also ln ⁡ T {\displaystyle \ln T} , with a constant that depends on the problem.

MarkLogic Server

MarkLogic Server is a document-oriented database developed by MarkLogic. It is a NoSQL multi-model database that evolved from an XML database to natively store JSON documents and RDF triples, the data model for semantics. MarkLogic is designed to be a data hub for operational and analytical data. == History == MarkLogic Server was built to address shortcomings with existing search and data products. The product first focused on using XML as the document markup standard and XQuery as the query standard for accessing collections of documents up to hundreds of terabytes in size. Currently the MarkLogic platform is widely used in publishing, government, finance and other sectors. MarkLogic's customers are mostly Global 2000 companies. == Technology == MarkLogic uses documents without upfront schemas to maintain a flexible data model. In addition to having a flexible data model, MarkLogic uses a distributed, scale-out architecture that can handle hundreds of billions of documents and hundreds of terabytes of data. It has received Common Criteria certification, and has high availability and disaster recovery. MarkLogic is designed to run on-premises and within public or private cloud environments like Amazon Web Services. == Features == Indexing MarkLogic indexes the content and structure of documents including words, phrases, relationships, and values in over 200 languages with tokenization, collation, and stemming for core languages. Functionality includes the ability to toggle range indexes, geospatial indexes, the RDF triple index, and reverse indexes on or off based on your data, the kinds of queries that you will run, and your desired performance. Full-text search MarkLogic supports search across its data and metadata using a word or phrase and incorporates Boolean logic, stemming, wildcards, case sensitivity, punctuation sensitivity, diacritic sensitivity, and search term weighting. Data can be searched using JavaScript, XQuery, SPARQL, and SQL. Semantics MarkLogic uses RDF triples to provide semantics for ease of storing metadata and querying. ACID Unlike other NoSQL databases, MarkLogic maintains ACID consistency for transactions. Replication MarkLogic provides high availability with replica sets. Scalability MarkLogic scales horizontally using sharding. MarkLogic can run over multiple servers, balancing the load or replicating data to keep the system up and running in the event of hardware failure. Security MarkLogic has built in security features such as element-level permissions and data redaction. Optic API for Relational Operations An API that lets developers view their data as documents, graphs or rows. Security MarkLogic provides redaction, encryption, and element-level security (allowing for control on read and write rights on parts of a document). == Applications == Banking Big Data Fraud prevention Insurance Claims Management and Underwriting Master data management Recommendation engines == Licensing == MarkLogic is available under various licensing and delivery models, namely a free Developer or an Essential Enterprise license.[3] Licenses are available from MarkLogic or directly from cloud marketplaces such as Amazon Web Services and Microsoft Azure. == Releases == 2001 – Cerisent XQE 1: ACID transactions, Full-text search, XML Storage, XQuery, Role-based security 2004 – Cerisent XQE 2: Scale-out architecture, Enhanced search (stemming, thesaurus, wildcard), Backup and restore 2005 – MarkLogic Server 3: Continuing search improvements, Content Processing Framework (including PDF, Word, Excel, PPT), Failover 2008 – MarkLogic Server 4: Geospatial search, entity extraction, advanced XQuery, performance, scalability enhancements, auditing 2011 – MarkLogic Server 5: Flexible replication / DDIL, real-time indexing, advanced search, improved analytics, concurrency enhancements 2012 – MarkLogic Server 6: REST and Java APIs, App Builder, enhanced UI, improved search 2013 – MarkLogic Server 7: Semantic graph, bitemporal data, tiered storage, improved search, better management 2015 – MarkLogic Server 8: A Native JSON storage, Server-side JavaScript, Bitemporal, Node.js client API, Incremental backup, Flexible replication[16] 2017 – MarkLogic Server 9: Data integration across Relational and Non-Relational data, Advanced Encryption, Element Level Security, Redaction 2019 – MarkLogic Server 10: Enhanced Data Hub, improved SQL, security, analytics performance, cloud support 2022 – MarkLogic Server 11: MarkLogic Ops Director (Monitoring and Administration Improvements), expanded PKI 2025 – MarkLogic Server 12: Generative AI and Native Vector Search, Graph Algorithm Support, Virtual TDEs (relational views on the fly)

AlphaTensor

AlphaTensor is an artificial intelligence system developed by DeepMind for discovering efficient matrix multiplication algorithms using reinforcement learning. Introduced in 2022, the system was based on AlphaZero and formulated the search for matrix multiplication algorithms as a single-player game called TensorGame. AlphaTensor was designed to search for new ways to multiply matrices with fewer scalar multiplication operations. Matrix multiplication is a fundamental operation in linear algebra, numerical analysis, scientific computing, computer graphics, and machine learning. The system discovered thousands of matrix multiplication algorithms, including algorithms that rediscovered known human-designed methods and others that improved on previously known results for particular matrix sizes and mathematical settings. == Background == Matrix multiplication is one of the basic operations in numerical computing. The standard algorithm for multiplying two square matrices has cubic time complexity, while faster algorithms such as the Strassen algorithm reduce the number of multiplication operations by using more complex algebraic decompositions. Finding optimal matrix multiplication algorithms can be difficult because it involves searching through a large space of possible tensor decompositions. AlphaTensor approached this problem by representing algorithm discovery as TensorGame, in which each move corresponds to an operation that reduces a tensor representing matrix multiplication. The goal of the game is to find a low-rank decomposition of the matrix multiplication tensor, corresponding to an efficient multiplication algorithm. == Development == AlphaTensor was developed by DeepMind and described in a paper published in Nature in October 2022. The system built on the reinforcement-learning approach used in AlphaZero, which had previously been applied to games such as Go, chess, and shogi. Unlike those games, TensorGame involved a very large search space, requiring changes to the AlphaZero-style search method and neural network architecture. DeepMind released source code and discovered algorithms associated with the publication through a public GitHub repository. == Results == AlphaTensor discovered matrix multiplication algorithms over both standard arithmetic and finite fields. One widely reported result was a method for multiplying 4 × 4 matrices over the field with two elements using 47 multiplication operations, improving on the 49 operations required by applying Strassen's algorithm recursively in that setting. The system also found algorithms optimized for particular computer hardware, including algorithms designed for graphics processing units and Tensor Processing Units. DeepMind stated that some of the hardware-specific algorithms improved practical execution time compared with commonly used algorithms on the tested hardware. == Significance == AlphaTensor was described as an example of using machine learning not only to apply existing algorithms, but to assist in discovering new ones. The work was connected to broader research in algorithm discovery, automated machine learning, program synthesis, and computational complexity theory, especially the open problem of determining the optimal complexity of matrix multiplication. AlphaTensor later became part of a broader group of Google DeepMind systems for algorithm and mathematical discovery, alongside systems such as AlphaDev and AlphaEvolve.

Action model learning

Action model learning (sometimes abbreviated action learning) is an area of machine learning concerned with the creation and modification of a software agent's knowledge about the effects and preconditions of the actions that can be executed within its environment. This knowledge is usually represented in a logic-based action description language and used as input for automated planners. Learning action models is important when goals change. When an agent acted for a while, it can use its accumulated knowledge about actions in the domain to make better decisions. Thus, learning action models differs from reinforcement learning. It enables reasoning about actions instead of expensive trials in the world. Action model learning is a form of inductive reasoning, where new knowledge is generated based on the agent's observations. The usual motivation for action model learning is the fact that manual specification of action models for planners is often a difficult, time-consuming, and error-prone task (especially in complex environments). == Action models == Given a training set E {\displaystyle E} consisting of examples e = ( s , a , s ′ ) {\displaystyle e=(s,a,s')} , where s , s ′ {\displaystyle s,s'} are observations of a world state from two consecutive time steps t , t ′ {\displaystyle t,t'} and a {\displaystyle a} is an action instance observed in time step t {\displaystyle t} , the goal of action model learning in general is to construct an action model ⟨ D , P ⟩ {\displaystyle \langle D,P\rangle } , where D {\displaystyle D} is a description of domain dynamics in action description formalism like STRIPS, ADL or PDDL and P {\displaystyle P} is a probability function defined over the elements of D {\displaystyle D} . However, many state of the art action learning methods assume determinism and do not induce P {\displaystyle P} . In addition to determinism, individual methods differ in how they deal with other attributes of domain (e.g. partial observability or sensoric noise). == Action learning methods == === State of the art === Recent action learning methods take various approaches and employ a wide variety of tools from different areas of artificial intelligence and computational logic. As an example of a method based on propositional logic, we can mention SLAF (Simultaneous Learning and Filtering) algorithm, which uses agent's observations to construct a long propositional formula over time and subsequently interprets it using a satisfiability (SAT) solver. Another technique, in which learning is converted into a satisfiability problem (weighted MAX-SAT in this case) and SAT solvers are used, is implemented in ARMS (Action-Relation Modeling System). Two mutually similar, fully declarative approaches to action learning were based on logic programming paradigm Answer Set Programming (ASP) and its extension, Reactive ASP. In another example, bottom-up inductive logic programming approach was employed. Several different solutions are not directly logic-based. For example, the action model learning using a perceptron algorithm or the multi level greedy search over the space of possible action models. In the older paper from 1992, the action model learning was studied as an extension of reinforcement learning. Nonetheless, further algorithms can be found that operate under different assumptions: FAMA can work even when some observations are missing, and it produces a general (lifted) planning model. It treats learning an action model like a planning problem, making sure the learned model matches the observations given. NOLAM can learn general action models even from noisy or imperfect data. LOCM focuses only on the order of actions in the data, ignoring any details about the states between those actions. The family of safe action model (SAM) learning methods create models that guarantee any plans made with them will actually work in the real world. There's also an extension called N-SAM that can learn action models with numeric conditions and effects. Additionally, numeric action models like N-SAM can be used to improve reinforcement learning (RL) performance through the RAMP algorithm. === Literature === Most action learning research papers are published in journals and conferences focused on artificial intelligence in general (e.g. Journal of Artificial Intelligence Research (JAIR), Artificial Intelligence, Applied Artificial Intelligence (AAI) or AAAI conferences). Despite mutual relevance of the topics, action model learning is usually not addressed in planning conferences like the International Conference on Automated Planning and Scheduling (ICAPS).

Time Warp Edit Distance

In the data analysis of time series, Time Warp Edit Distance (TWED) is a measure of similarity (or dissimilarity) between pairs of discrete time series, controlling the relative distortion of the time units of the two series using the physical notion of elasticity. In comparison to other distance measures, (e.g. DTW (dynamic time warping) or LCS (longest common subsequence problem)), TWED is a metric. Its computational time complexity is O ( n 2 ) {\displaystyle O(n^{2})} , but can be drastically reduced in some specific situations by using a corridor to reduce the search space. Its memory space complexity can be reduced to O ( n ) {\displaystyle O(n)} . It was first proposed in 2009 by P.-F. Marteau. == Definition == δ λ , ν ( A 1 p , B 1 q ) = M i n { δ λ , ν ( A 1 p − 1 , B 1 q ) + Γ ( a p ′ → Λ ) d e l e t e i n A δ λ , ν ( A 1 p − 1 , B 1 q − 1 ) + Γ ( a p ′ → b q ′ ) m a t c h o r s u b s t i t u t i o n δ λ , ν ( A 1 p , B 1 q − 1 ) + Γ ( Λ → b q ′ ) d e l e t e i n B {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{p},B_{1}^{q})=Min{\begin{cases}\delta _{\lambda ,\nu }(A_{1}^{p-1},B_{1}^{q})+\Gamma (a_{p}^{'}\to \Lambda )&{\rm {delete\ in\ A}}\\\delta _{\lambda ,\nu }(A_{1}^{p-1},B_{1}^{q-1})+\Gamma (a_{p}^{'}\to b_{q}^{'})&{\rm {match\ or\ substitution}}\\\delta _{\lambda ,\nu }(A_{1}^{p},B_{1}^{q-1})+\Gamma (\Lambda \to b_{q}^{'})&{\rm {delete\ in\ B}}\end{cases}}} whereas Γ ( α p ′ → Λ ) = d L P ( a p ′ , a p − 1 ′ ) + ν ⋅ ( t a p − t a p − 1 ) + λ {\displaystyle \Gamma (\alpha _{p}^{'}\to \Lambda )=d_{LP}(a_{p}^{'},a_{p-1}^{'})+\nu \cdot (t_{a_{p}}-t_{a_{p-1}})+\lambda } Γ ( α p ′ → b q ′ ) = d L P ( a p ′ , b q ′ ) + d L P ( a p − 1 ′ , b q − 1 ′ ) + ν ⋅ ( | t a p − t b q | + | t a p − 1 − t b q − 1 | ) {\displaystyle \Gamma (\alpha _{p}^{'}\to b_{q}^{'})=d_{LP}(a_{p}^{'},b_{q}^{'})+d_{LP}(a_{p-1}^{'},b_{q-1}^{'})+\nu \cdot (|t_{a_{p}}-t_{b_{q}}|+|t_{a_{p-1}}-t_{b_{q-1}}|)} Γ ( Λ → b q ′ ) = d L P ( b p ′ , b p − 1 ′ ) + ν ⋅ ( t b q − t b q − 1 ) + λ {\displaystyle \Gamma (\Lambda \to b_{q}^{'})=d_{LP}(b_{p}^{'},b_{p-1}^{'})+\nu \cdot (t_{b_{q}}-t_{b_{q-1}})+\lambda } Whereas the recursion δ λ , ν {\displaystyle \delta _{\lambda ,\nu }} is initialized as: δ λ , ν ( A 1 0 , B 1 0 ) = 0 , {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{0})=0,} δ λ , ν ( A 1 0 , B 1 j ) = ∞ f o r j ≥ 1 {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{j})=\infty \ {\rm {{for\ }j\geq 1}}} δ λ , ν ( A 1 i , B 1 0 ) = ∞ f o r i ≥ 1 {\displaystyle \delta _{\lambda ,\nu }(A_{1}^{i},B_{1}^{0})=\infty \ {\rm {{for\ }i\geq 1}}} with a 0 ′ = b 0 ′ = 0 {\displaystyle a'_{0}=b'_{0}=0} === Implementations === An implementation of the TWED algorithm in C with a Python wrapper is available at TWED is also implemented into the Time Series Subsequence Search Python package (TSSEARCH for short) available at [1]. An R implementation of TWED has been integrated into the TraMineR, a R package for mining, describing and visualizing sequences of states or events, and more generally discrete sequence data. Additionally, cuTWED is a CUDA- accelerated implementation of TWED which uses an improved algorithm due to G. Wright (2020). This method is linear in memory and massively parallelized. cuTWED is written in CUDA C/C++, comes with Python bindings, and also includes Python bindings for Marteau's reference C implementation. ==== Python ==== Backtracking, to find the most cost-efficient path: ==== MATLAB ==== Backtracking, to find the most cost-efficient path: