Babak Hodjat (Persian: بابک حجت; born November 1, 1967) is a British computer scientist, entrepreneur, and writer. He was the co-founder and CEO of Sentient Technologies and now holds the position of Chief Technology Officer AI at Cognizant. He is a specialist in the field of artificial intelligence and machine learning. In 1998 Hodjat co-founded Dejima Inc and served as CEO and CTO, his patented work on artificial intelligence led to the technology used by Apple for their digital assistant Siri. == Biography == === Early life === Babak Hodjat was born on November 1, 1967, in Wimbledon. His father was a retired university professor in entomology who worked at the British Museum. As a child, he did not like insects and would wander off to the nearby science museum, where he would spend long hours in front of a computer they had on display. He attended middle school in the United States. He studied at the Sharif University of Technology from 1986 to 1995, and received his Master of Science degree in software engineering. In 1994, together with another computer department student Hormoz Shahrzad presented their research titled Introducing a dynamic problem solving scheme based on a learning algorithm in artificial life environments at the first IEEE Conference on Computational Intelligence held at Orlando. Hodjat received a PhD in machine intelligence from Kyushu University in 2003 During his time there, he published several works on adaptive agent oriented software architecture and natural language user interfaces. === Career in science and business === Hodjat moved to Silicon Valley, California in 1998 and founded Dejima Inc. (named after the historic Japanese Dejima artificial island). The firm was based on a patented adaptive agent-oriented software engineering platform developed by Hodjat, Christopher Savoie and Makoto Amamiya. Hodjat served as the CTO and as the CEO for 9 months from October 2000. By 2000 the company had offices in San Jose, London and Tokyo. In 2002, the company developed a voice control Natural Interaction Platform (NPI) in collaboration with the Stanford University's research group Archimedes Project. During these years Hodjat continued his research on agent oriented software architecture and natural language user interfaces. In July 2003, Dejima got funding from SRI International within the Cognitive Assistant that Learns and Organizes (CALO) project of DARPA and worked on a Perceptive Assistant that Learns (PAL) initiative. Hodjat was the primary inventor of the firm's agent-oriented technology applied to intelligent interfaces for mobile and enterprise computing – a technology that eventually led to Siri. In April 2004, Dejima was acquired by Sybase iAnywhere. Hodjat served as senior director of engineering at Sybase iAnywhere from 2004 to 2008, where he developed AvantGo Platform, mBusiness Anywhere, and Answers Anywhere. In 2006, he co-founded MobileVerbs Inc., a mobile marketing service company, which was acquired by iLoop Mobile in February 2010. In 2007, he teamed with Antoine Blondeau (former CEO of Dejima) and Adam Cheyer (Dejima's vice president and Chief Architect of the CALO project) to establish Genetic Finance Holding Ltd. (where he began as CTO). In 2014 the firm became Sentient Technologies. Hodjat was joined by his long-time research fellow Hormoz Shahrzad who became principal scientist, while Hodjat held the position of chief scientist. In the following years Hodjat has worked on developing massively distributed computing technology and improving machine-learning technique known as evolutionary algorithms. One area that gained special attention from the press was applying Sentient Technologies algorithms to a stock market trading through specially created Sentient Investment Management hedge fund. Following the management change within Sentient Technologies, Hodjat became the company's CEO in February 2017. He continues his business and educational projects (he was on the jury of IBM Watson AI XPRIZE and the Merit Awards committee for the ISAL Award). == Writing == Hodjat is the author of multiple books such as The Konar and the Apple: Fun, Beauty, and Dread--From Ahwaz to California and the science fiction novel "The Narrator" (January 2022; ISBN 978-1-7354860-1-7)(March 2023; ISBN 978-1-7354860-0-0). == Selected publications == Hodjat, B.; Shahrzad, H. (1994). "Introducing a dynamic problem solving scheme based on a learning algorithm in artificial life environments". IEEE International Joint Conference on neural networks (IJCNN-94). Vol. 4. IEEE International Joint Conference on neural networks. pp. 2333–2338. doi:10.1109/ICNN.1994.374583. ISBN 978-0-7803-1901-1. S2CID 60497133. Hodjat, B.; Savoie, C.J.; Amamiya, M. (2006) [1998]. "An adaptive agent oriented software architecture". PRICAI'98: Topics in Artificial Intelligence. Springer. pp. 33–46. arXiv:cs/9812014. doi:10.1007/BFb0095256. ISBN 978-3-540-49461-4. S2CID 5317786. Hodjat, B.; Amamiya, M. (2000-05-25). "Applying the Adaptive Agent Oriented Software Architecture to the Parsing of Context Sensitive Grammars". IEICE Transactions on Information and Systems. E83-D (5): 1142–1152. ISSN 0916-8532. Retrieved 2017-12-14. Hodjat, Babak; Hodjat, Siamak; Treadgold, Nick; Jonsson, Ing-Marie (2006). "CRUSE: a context reactive natural language mobile interface". Proceedings of the 2nd annual international workshop on Wireless internet. WICON. doi:10.1145/1234161.1234181. ISBN 978-1-59593-510-6. S2CID 2388254. O'Reilly, Una-May; Wagy, Mark; Hodjat, Babak (2013). "Chapter 6: EC-Star: A Massive-Scale, Hub and Spoke, Distributed Genetic Programming System". In Riolo, R.; Vladislavleva, E.; Ritchie, M.; Moore, J.H. (eds.). Genetic Programming Theory and Practice X. Springer-Verlag New York. pp. 73–85. doi:10.1007/978-1-4614-6846-2. ISBN 978-1-4614-6845-5. S2CID 39650969. Retrieved 2017-12-14. Hodjat, Babak; Hemberg, Erik; Shahrzad, Hormoz; O'Reilly, Una-May (2014). "Chapter 4: Maintenance of a Long Running Distributed Genetic Programming System for Solving Problems Requiring Big Data". In Riolo, Rick; Moore, Jason H.; Kotanchek, Mark (eds.). Genetic Programming Theory and Practice XI. Springer-Verlag New York. pp. 65–83. doi:10.1007/978-1-4939-0375-7. ISBN 978-1-4939-0374-0. S2CID 28843739. Retrieved 2017-12-14. Shahrzad, Hormoz; Hodjat, Babak; Miikkulainen, Risto (2016). "Estimating the Advantage of Age-Layering in Evolutionary Algorithms". Proceedings of the Genetic and Evolutionary Computation Conference 2016. Genetic and Evolutionary Computation Conference. pp. 693–699. doi:10.1145/2908812.2908911. ISBN 978-1-4503-4206-3. S2CID 215516530. == Patents == Babak Hodjat holds 21 patents in the fields of agent-oriented programming, natural language decision engines, distributed evolutionary algorithms for asset management and trading and data mining.
Unfold (app)
Unfold is a mobile application that allows users to create social media content using a variety of templates and other tools. It was founded in 2018 by Alfonso Cobo and Andy McCune. It enables users to add photos, video, and text with a variety of tools. In 2019, Unfold was acquired by Squarespace. == History == In January 2017, Alfonso Cobo was studying at Parsons School of Design when he realized there was no software or app that could create a portfolio of his work on an iPad. Cobo created an app called Portfolio, a basic version of a portfolio layout app, and the first one to exist for iPad. He launched it in 2017. After launching the first version of Portfolio, Cobo realized the more popular market and use case was on mobile. Around that time, Instagram was launching Stories. As a result, Cobo pivoted the app away from portfolios and instead focused on an app to showcase one's stories. Cobo later contacted Andy McCune, founder of social media account Earth, to collaborate with Unfold. Unfold also partnered with various companies to create custom templates. These include Equinox, Tommy Hilfiger, NARS, Billboard Music Awards, and Product Red. Unfold also launched a collection of Product Red templates to help eliminate HIV/AIDS in several African countries. In 2019, Squarespace acquired Unfold. The Unfold app has been downloaded over 60 million times and has been used to create over 1 billion Instagram stories. == Features == With Unfold, users can utilize hundreds of templates to make social content for social media platforms such as Instagram, Snapchat, and Facebook. The free app offers users basic templates and standard fonts, filters, and stickers, and there are also premium templates available for a monthly subscription. With Unfold+ and Unfold Pro (previously Unfold for Brands), users can access premium templates and tools, as well as upload custom brand assets and fonts. In 2020, Unfold launched Bio Sites, which allows users to link to multiple sites and platforms.
Two-phase commit protocol
In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC, tupac) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction. This protocol (a specialised type of consensus protocol) achieves its goal even in many cases of temporary system failure (involving either process, network node, communication, etc. failures), and is thus widely used. However, it is not resilient to all possible failure configurations, and in rare cases, manual intervention is needed to remedy an outcome. To accommodate recovery from failure (automatic in most cases) the protocol's participants use logging of the protocol's states. Log records, which are typically slow to generate but survive failures, are used by the protocol's recovery procedures. Many protocol variants exist that primarily differ in logging strategies and recovery mechanisms. Though usually intended to be used infrequently, recovery procedures compose a substantial portion of the protocol, due to many possible failure scenarios to be considered and supported by the protocol. In a "normal execution" of any single distributed transaction (i.e., when no failure occurs, which is typically the most frequent situation), the protocol consists of two phases: The commit-request phase (or voting phase), in which a coordinator process attempts to prepare all the transaction's participating processes (named participants, cohorts, or workers) to take the necessary steps for either committing or aborting the transaction and to vote, either "Yes": commit (if the transaction participant's local portion execution has ended properly), or "No": abort (if a problem has been detected with the local portion), and The commit phase, in which, based on voting of the participants, the coordinator decides whether to commit (only if all have voted "Yes") or abort the transaction (otherwise), and notifies the result to all the participants. The participants then follow with the needed actions (commit or abort) with their local transactional resources (also called recoverable resources; e.g., database data) and their respective portions in the transaction's other output (if applicable). The two-phase commit (2PC) protocol should not be confused with the two-phase locking (2PL) protocol, a concurrency control protocol. == Assumptions == The protocol works in the following manner: one node is a designated coordinator, which is the master site, and the rest of the nodes in the network are designated the participants. The protocol assumes that: there is stable storage at each node with a write-ahead log, no node crashes forever, the data in the write-ahead log is never lost or corrupted in a crash, and any two nodes can communicate with each other. The last assumption is not too restrictive, as network communication can typically be rerouted. The first two assumptions are much stronger; if a node is totally destroyed then data can be lost. The protocol is initiated by the coordinator after the last step of the transaction has been reached. The participants then respond with an agreement message or an abort message depending on whether the transaction has been processed successfully at the participant. == Basic algorithm == === Commit request (or voting) phase === The coordinator sends a query to commit message to all participants and waits until it has received a reply from all participants. The participants execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their redo log. Each participant replies with: either an agreement message (participant votes Yes to commit), if the participant's actions succeeded; or an abort message (participant votes No to commit), if the participant experiences a failure that will make it impossible to commit. === Commit (or completion) phase === ==== Success ==== If the coordinator received an agreement message from all participants during the commit-request phase: The coordinator sends a commit message to all the participants. Each participant completes the operation, and releases all the locks and resources held during the transaction. Each participant sends an acknowledgement to the coordinator. The coordinator completes the transaction when all acknowledgements have been received. ==== Failure ==== If any participant votes No during the commit-request phase (or the coordinator's timeout expires): The coordinator sends a rollback message to all the participants. Each participant undoes the transaction using the undo log, and releases the resources and locks held during the transaction. Each participant sends an acknowledgement to the coordinator. The coordinator undoes the transaction when all acknowledgements have been received. ==== Message flow ==== Coordinator Participant QUERY TO COMMIT --------------------------------> VOTE YES/NO prepare/abort <------------------------------- commit/abort COMMIT/ROLLBACK --------------------------------> ACKNOWLEDGEMENT commit/abort <-------------------------------- end An next to the record type means that the record is forced to stable storage. == Disadvantages == The greatest disadvantage of the two-phase commit protocol is that it is a blocking protocol. If the coordinator fails permanently, some participants will never resolve their transactions: After a participant has sent an agreement message as a response to the commit-request message from the coordinator, it will block until a commit or rollback is received. A two-phase commit protocol cannot dependably recover from a failure of both the coordinator and a cohort member during the commit phase. If only the coordinator had failed, and no cohort members had received a commit message, it could safely be inferred that no commit had happened. If, however, both the coordinator and a cohort member failed, it is possible that the failed cohort member was the first to be notified, and had actually done the commit. Even if a new coordinator is selected, it cannot confidently proceed with the operation until it has received an agreement from all cohort members, and hence must block until all cohort members respond. == Implementing the two-phase commit protocol == === Common architecture === In many cases the 2PC protocol is distributed in a computer network. It is easily distributed by implementing multiple dedicated 2PC components similar to each other, typically named transaction managers (TMs; also referred to as 2PC agents or Transaction Processing Monitors), that carry out the protocol's execution for each transaction (e.g., The Open Group's X/Open XA). The databases involved with a distributed transaction, the participants, both the coordinator and participants, register to close TMs (typically residing on respective same network nodes as the participants) for terminating that transaction using 2PC. Each distributed transaction has an ad hoc set of TMs, the TMs to which the transaction participants register. A leader, the coordinator TM, exists for each transaction to coordinate 2PC for it, typically the TM of the coordinator database. However, the coordinator role can be transferred to another TM for performance or reliability reasons. Rather than exchanging 2PC messages among themselves, the participants exchange the messages with their respective TMs. The relevant TMs communicate among themselves to execute the 2PC protocol schema above, "representing" the respective participants, for terminating that transaction. With this architecture the protocol is fully distributed (does not need any central processing component or data structure), and scales up with number of network nodes (network size) effectively. This common architecture is also effective for the distribution of other atomic commitment protocols besides 2PC, since all such protocols use the same voting mechanism and outcome propagation to protocol participants. === Protocol optimizations === Database research has been done on ways to get most of the benefits of the two-phase commit protocol while reducing costs by protocol optimizations and protocol operations saving under certain system's behavior assumptions. ==== Presumed abort and presumed commit ==== Presumed abort or Presumed commit are common such optimizations. An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. This means that it does not matter if aborts are logged at all, and such logging can be saved under this assumption. Typical
Lion algorithm
Lion algorithm (LA) is one among the bio-inspired (or) nature-inspired optimization algorithms (or) that are mainly based on meta-heuristic principles. It was first introduced by B. R. Rajakumar in 2012 in the name, Lion’s Algorithm. It was further extended in 2014 to solve the system identification problem. This version was referred as LA, which has been applied by many researchers for their optimization problems. == Inspiration from lion’s social behaviour == Lions form a social system called a "pride", which consists of 1–3 pair of lions. A pride of lions shares a common area known as territory in which a dominant lion is called as territorial lion. The territorial lion safeguards its territory from outside attackers, especially nomadic lions. This process is called territorial defense. It protects the cubs till they become sexually matured. The maturity period is about 2–4 years. The pride undergoes survival fights to protect its territory and the cubs from nomadic lions. Upon getting defeated by the nomadic lions, the dominating nomadic lion takes the role of territorial lion by killing or driving out the cubs of the pride. The lioness of the pride give birth to cubs though the new territorial lion. When the cubs of the pride mature and considered to be stronger than the territorial lion, they take over the pride. This process is called territorial take-over. If territorial take-over happens, either the old territorial lion, which is considered to be laggard, is driven out or it leaves the pride. The stronger lions and lioness form the new pride and give birth to their own cubs == Terminology == In the LA, the terms that are associated with lion’s social system are mapped to the terminology of optimization problems. Few of such notable terms are related here. Lion: A potential solution to be generated or determined as optimal (or) near-optimal solution of the problem. The lion can be a territorial lion and lioness, cubs and nomadic lions that represent the solution based on the processing steps of the LA. Territorial lion: The strongest solution of the pride that tends to meet the objective function. Nomadic lion: A random solution, sometimes termed as nomad, to facilitate the exploration principle Laggard lion: Poor solutions that are failed in the survival fight. Pride: A pool of potential solutions i.e. a lion, lioness and their cubs, that are potential solutions of the search problem. Fertility evaluation: A process of evaluating whether the territorial lion and lioness are able to provide potential solutions in the future generations i.e. It ensures that the lion or lioness converge at every generation. Survival fight: It is a greedy selection process, which is often carried out between the pride and nomadic lion. == Algorithm == The steps involved in LA are given below: Pride Generation: Generate X m a l e {\displaystyle X^{male}} , X f e m a l e {\displaystyle X^{female}} and X 1 n o m a d {\displaystyle X_{1}^{nomad}} Determine f ( X m a l e ) {\displaystyle f(X^{male})} , f ( X f e m a l e ) {\displaystyle f(X^{female})} , f ( X 1 n o m a d ) {\displaystyle f(X_{1}^{nomad})} Initialize f r e f {\displaystyle f^{ref}} as f ( X m a l e ) {\displaystyle f(X^{male})} and N g {\displaystyle N_{g}} as 0 Memorize X m a l e {\displaystyle X^{male}} and X f e m a l e {\displaystyle X^{female}} Apply Fertility evaluation Process Generation of cubpool by mating Gender clustering: Define X c u b m a l e {\displaystyle X_{cub}^{male}} and X c u b f e m a l e {\displaystyle X_{cub}^{female}} Initialize a g e c u b {\displaystyle age_{cub}} as zero Apply Cub growth function Territorial defense: If X m a l e {\displaystyle X^{male}} (or pride) fails in the survival fight i.e. X 1 n o m a d {\displaystyle X_{1}^{nomad}} defeats the pride, go to step 4, else continue Increase a g e c u b {\displaystyle age_{cub}} by 1 and check whether cub attains maturity i.e., if a g e c u b > a g e m a x {\displaystyle age_{cub}>age_{max}} , go to Step 9, else continue Territorial takeover: If X c u b m a l e {\displaystyle X_{cub}^{male}} and X c u b f e m a l e {\displaystyle X_{cub}^{female}} are found to be closer to optimal solution, update X m a l e {\displaystyle X^{male}} and X f e m a l e {\displaystyle X^{female}} Increment N g {\displaystyle N_{g}} by 1 Repeat from Step 5, if termination criterion is not violated, else return X m a l e {\displaystyle X^{male}} as the near-optimal solution == Variants == The LA has been further taken forward to adopt in different problem areas. According to the characteristics of the problem area, significant amendment has been done in the processes and the models used in the LA. Accordingly, diverse variants have been developed by the researchers. They can be broadly grouped as hybrid LAs and non-hybrid LAs. Hybrid LAs are the LAs that are amended by the principle of other meta-heuristics, whereas the Non-hybrid LAs take any scientific amendment inside its operation that are felt to be essential to attend the respective problem area. == Applications == LA is applied in diverse engineering applications that range from network security, text mining, image processing, electrical systems, data mining and many more. Few of the notable applications are discussed here. Networking applications: In WSN, LA is used to solve the cluster head selection problem by determining optimal cluster head. Route discovery problem in both the VANET and MANET are also addressed by the LA in the literature. It is also used to detect attacks in advanced networking scenarios such as Software-Defined Networks (SDN) Power Systems: LA has attended generation rescheduling problem in a deregulated environment, optimal localization and sizing of FACTS devices for power quality enhancement and load-frequency controlling problem Cloud computing: LA is used in optimal container-resource allocation problem in cloud environment and cloud security
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.
Language technology
Language technology, often called human language technology (HLT), studies methods of how computer programs or electronic devices can analyze, produce, modify or respond to human texts and speech. Working with language technology often requires broad knowledge not only about linguistics but also about computer science. It consists of natural language processing (NLP) and computational linguistics (CL) on the one hand, many application oriented aspects of these, and more low-level aspects such as encoding and speech technology on the other hand. Note that these elementary aspects are normally not considered to be within the scope of related terms such as natural language processing and (applied) computational linguistics, which are otherwise near-synonyms. As an example, for many of the world's lesser known languages, the foundation of language technology is providing communities with fonts and keyboard setups so their languages can be written on computers or mobile devices. Other tools also are part of modern language technology and include machine translation, speech recognition, text processing and natural language processing. Large scale AI models have recently advanced the field and enhanced the ability of machines to interpret complex human context.
Penril
Penril DataComm Networks, Inc. was a computer telecommunications hardware company that made some acquisitions and was eventually split into two parts: one was acquired by Bay Networks and the other was a newly formed company named Access Beyond. The focus of both company's products was end-to-end data transfer. By the mid-1990s, with the popularization of the internet, this was no longer of wide interest. == History == Penril, whose earnings reports and other financials were followed by The New York Times in the 1990s, made several acquisitions but also grew internally. Following its Datability acquisition it renamed itself Penril Datability Networks. By the time the 1968-founded Penril was acquired by Bay their name was Penril DataComm Networks. The company, which as of 1985 "had made 14 acquisitions in 12 years," also had done extensive work regarding quality control, and leveraged their product line by what The Washington Post called clever packaging: "software, cables, instructions and telephone support" sold to those less technically skilled as "Network in a Box." == Datability == Datability Software Systems Inc. was the initial name of what by 1991 became 'Datability, Inc.', "a manufacturer of hardware that links computer networks." The 1977-founded firm began as a software consulting company, especially in the area of databases. To speed up project development they built a program generator, which they marketed as Control 10/20 (targeted at users of Digital Equipment Corporation's DECsystem-10 and DECSYSTEM-20). After trying their hand at time-sharing they built hardware to enhance bridging these computers to DEC's VAX product line. In particular they focused on Digital's LAT protocol, selling "boxes" that reimplemented the protocol, at a lower price than DEC's. They later expanded into other areas of telecommunications hardware The firm relocated to a larger manufacturing plant in 1991 and was acquired by Penril in 1993. == Access Beyond == Access Beyond was initially housed by Penril, from which it was spun off. A securities analyst noted that Access began operations with no debt. They subsequently merged with Hayes Corporation. Some of the funds brought to the merger came from a sale by Penril of two of its divisions, each bringing about $4 million. == Ron Howard == Ron Howard, founder of Datability, became part of Penril when the latter acquired the former, and was CEO of Access Beyond when it was spun off by Penril. Access merged with Hayes Microcomputer Products and was renamed Hayes Corp, at which time Howard became executive VP of business development and corporate vice chairman of Hayes. == People == In the matter of hiring immigrants, in an industry where recent arrivals came from a culture of six day work weeks, and subcontracting was then common, these assembly line workers at Penril comprised about 25%, compared to double in other firms. Placement was overseen by government agencies. == Controversy == Penril had a joint development agreement, beginning in 1990, with a Standard Microsystems Corporation (SMSC) subsidiary. A dispute arose, and the matter was brought to court. Penril was awarded $3.5 million in 1996.