Cristóbal Valenzuela (born 1989) is a Chilean-born technologist, software developer, and CEO of Runway. In 2018, Valenzuela co-founded the AI research company Runway in New York City with Anastasis Germanidis and Alejandro Matamala. == Education == Valenzuela graduated from Adolfo Ibáñez University (AIU), a research private university in Chile. From there, Valenzuela obtained a bachelor's degree in economics and business management, along with a master's degree in arts in design in 2012. In 2018, he graduated with a media arts degree from ITP NYU's Tisch School of the Arts. == Career and recognition == One of Valenzuela's first jobs was as a teaching and research assistant at the Adolfo Ibáñez University School of Design, and later an adjunct professor in the same department. In 2018, he became a researcher at NYU's Tisch School of the Arts ITP program, where he worked with Daniel Shiffman. He contributes to open-source software projects, including ml5.js, an open-source machine learning software. He co-founded Runway with two colleagues from ITP, Anastasis Germanidis, and Alejandro Matamala. The goal of Runway is to create new tools for human imagination using generative AI. In recent years, Valenzuela's work has been sponsored by Google and the Processing Foundation and his projects have been exhibited throughout Latin America and the US, including the Santiago Museum of Contemporary Art, Lollapalooza, NYC Media Lab, New Latin Wave, Inter-American Development Bank, Stanford University and New York University. In September 2023, Valenzuela was named as one of the TIME 100 Most Influential People in AI (TIME100 AI).
DoorDash
DoorDash, Inc. is an American company operating online food ordering and food delivery. It trades under the symbol DASH. With a 56% market share, DoorDash is the largest food delivery platform in the United States. It also has a 60% market share in the convenience delivery category. As of December 31, 2020, the platform was used by 450,000 merchants, 20 million consumers, and had over one million delivery couriers. Founded by Tony Xu, Andy Fang, Stanley Tang and Evan Moore, DoorDash made its debut on the Fortune 500 list in 2024, ranking No. 443. DoorDash has been sued for or held legally liable for withholding tips, reducing tip transparency, antitrust price manipulation, listing restaurants without permission, misclassifying workers, withholding sick time, and illegally selling personal data. As of April 2026, DoorDash operates in the United States (including Puerto Rico), Canada, Australia, and New Zealand. Through its subsidiaries Deliveroo and Wolt, the company also operates across Europe, as well as in Azerbaijan, Georgia, Israel, Kazakhstan, Kuwait, and the United Arab Emirates. == History == In January 2013, Stanford University students Tony Xu, Stanley Tang, Andy Fang and Evan Moore launched PaloAltoDelivery.com in Palo Alto, California. In the summer of 2013, it received US$120,000 in seed money from Y Combinator in exchange for a 7% stake. It incorporated as DoorDash in June 2013. DoorDash's first partnership with a fast food burger restaurant chain was in April 2016, when it partnered with CKE Restaurants, parent company of Carl's Jr. and Hardee's, for food delivery. In December 2017, DoorDash announced its partnership with Wendy's for delivery from its restaurants. In December 2018, DoorDash overtook Uber Eats to hold the second position in total US food delivery sales, behind GrubHub. By March 2019, it had exceeded GrubHub in total sales, at 27.6% of the on-demand delivery market. By early 2019, DoorDash was the largest food delivery provider in the U.S., as measured by consumer spending. In October 2019, DoorDash opened its first ghost kitchen, DoorDash Kitchen, in Redwood City, California, with four restaurants operating at the location. By June 2020, DoorDash had raised more than $2.5 billion over several financing rounds from investors including Y Combinator, Charles River Ventures, SV Angel, Khosla Ventures, Sequoia Capital, SoftBank Group, GIC, and Kleiner Perkins. DoorDash announced a partnership with KFC in September 2020, followed by Taco Bell in October 2020. In November 2020, DoorDash announced the opening of its first physical restaurant location, partnering up with Bay Area restaurant Burma Bites to offer delivery and pick-up orders. In December 2020, it became a public company via an initial public offering, raising $3.37 billion. In November 2021, DoorDash acquired Finland's Wolt for €7bn. In August 2022, DoorDash announced it would end its partnership with Walmart in September, ending the companies' cooperation agreement from 2018. In November 2022, DoorDash announced plans to lay off 1,250 corporate employees, or about six percent of its workforce, to rein in expenses. In June 2023, DoorDash announced it would give its drivers the option of earning an hourly minimum wage instead of being paid per delivery. However, drivers are only paid hourly when on an active delivery. In September 2023, the company transferred its stock listing from the New York Stock Exchange to the Nasdaq. On December 18, 2023, DoorDash was added to the Nasdaq-100 index. In March 2025, DoorDash announced a partnership with Klarna, a Buy Now, Pay Later (BNPL) service, letting customers schedule small payments over a set period of time. DoorDash received widespread criticism from this decision, including internet mockery, given concerns about the increase of household debt in America. In 2025, DoorDash acquired the UK-based delivery service Deliveroo for $3.88 billion. The combined company operates in 40 countries and serves 50 million users monthly. In September 2025, DoorDash and Ace Hardware (the largest hardware cooperative) announced their partnership to offer delivery for home use products from over 4,000 Ace locations. == Lawsuits against DoorDash == === 2017 class-action lawsuit for misclassifying workers === In 2017, a class-action lawsuit was filed against DoorDash for allegedly misclassifying delivery drivers in California and Massachusetts as independent contractors. In 2022, a tentative settlement was reached in which DoorDash would pay $100 million total, with $61 million going to over 900,000 drivers, paying out just over $130 per driver, and $28 million for the lawyers. Gizmodo criticized the settlement, noting that the $413 million that DoorDash CEO Tony Xu received the previous year was one of the largest CEO compensation packages of all time. === 2019 data breach lawsuit === On May 4, 2019, DoorDash confirmed 4.9 million customers, delivery workers and merchants had sensitive information stolen via a data breach. Those who joined the platform after April 5, 2018, were unaffected by the breach. A class-action lawsuit for the breach was filed against DoorDash in October 2019. === Withholding of tips and subsequent class-action lawsuits === In July 2019, the company's tipping policy was criticized by The New York Times, and later The Verge and Vox and Gothamist. Drivers receive a guaranteed minimum per order that is paid by DoorDash by default. When a customer added a tip, instead of going directly to the driver, it first went to the company to cover the guaranteed minimum. Drivers then only directly received the part of the tip that exceeded the guaranteed minimum per order. In January 2020, it was reported that DoorDash had lied about skimming tips from its drivers, causing them to earn an average of $1.45 an hour after expenses, and that after the company had allegedly overhauled its tipping system, DoorDash was still manipulating per-delivery payouts at the expense of drivers. A DoorDash customer filed a class action lawsuit against the company for its "materially false and misleading" tipping policy. The case was referred to arbitration in August 2020. Under pressure, the company revised its policy. The company settled a lawsuit with District of Columbia Attorney General Karl Racine for $2.5 million, with funds going to deliverers, the government, and to charity. ==== 2021 driver strike for tip transparency ==== In July 2021, DoorDash drivers went on strike to protest lack of tip transparency and to ask for higher pay. At the time of the strike, and, as of June 2022, DoorDash did not allow drivers to see the full tip amounts prior to accepting a delivery in the app. If customers tip over a set amount for the order total, Doordash hides a portion of the tip until the delivery is complete. The strike occurred after DoorDash rewrote its code to cut off access to Para, a third-party app that drivers had been using to see the full tip amounts. ==== 2025 class-action lawsuit settlement ==== In 2025, DoorDash agreed to pay around $17 million for "misleading both consumers and delivery workers" with tips being docked from drivers' pay instead of directly going to drivers. === 2020 antitrust litigation === In April 2020, in the case of Davitashvili v. GrubHub Inc. DoorDash, Grubhub, Postmates, and Uber Eats were accused of monopolistic power by only listing restaurants on its apps if the restaurant owners signed contracts which include clauses that require prices be the same for dine-in customers as for customers receiving delivery. The plaintiffs stated that this arrangement increases the cost for dine-in customers, as they are required to subsidize the cost of delivery; and that the apps charge "exorbitant" fees, which range from 13% to 40% of revenue, while the average restaurant's profit ranges from 3% to 9% of revenue. The lawsuit seeks treble damages, including for overcharges, since April 14, 2016, for dine-in and delivery customers in the United States at restaurants using the defendants’ delivery apps. Although several preliminary documents in the case have now been filed, a trial date has not yet been set. === Litigation for illegal unauthorized restaurant listing === In May 2021, DoorDash was criticized for unauthorized listings of restaurants who had not given permission to appear on the app. The company was sued by Lona's Lil Eats in St. Louis, with the lawsuit claiming that DoorDash had listed them without permission, then prevented any orders to the restaurant from going through and redirecting customers to other restaurants instead, because Lona's was "too far away," when in reality it had not paid DoorDash a fee for listing. This aspect of DoorDash's business practice is illegal in California. === 2021 lawsuit by the city of Chicago === In August 2021, the city of Chicago sued DoorDash and GrubHub. According to Chicago mayor Lori Lightfoot, the companies broke the law by using "unfair and deceptive t
Multi-surface method
The multi-surface method (MSM) is a form of decision making using the concept of piecewise-linear separability of datasets to categorize data. == Introduction == Two datasets are linearly separable if their convex hulls do not intersect. The method may be formulated as a feedforward neural network with weights that are trained via linear programming. Comparisons between neural networks trained with the MSM versus backpropagation show MSM is better able to classify data. The decision problem associated linear program for the MSM is NP-complete. == Mathematical formulation == Given two finite disjoint point sets A , B ∈ R n {\displaystyle {\mathcal {A,B}}\in \mathbb {R} ^{n}} , find a discriminant, f : R n → R {\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} } such that f ( A ) > 0 , f ( B ) ≤ 0 {\displaystyle f({\mathcal {A}})>0,f({\mathcal {B}})\leq 0} . If the intersection of convex hulls of the two sets is the empty set, then it is possible to use a single linear program to obtain a linear discriminant of the form, f ( x ) = c x + γ {\displaystyle f(x)=cx+\gamma } . Usually, in real applications, the sets' convex hulls do intersect, and a (often non-convex) piecewise-linear discriminant can be used, through the use of several linear programs.
Sigmoid function
A sigmoid function is any mathematical function whose graph has a characteristic S-shaped or sigmoid curve. A common example of a sigmoid function is the logistic function. Other sigmoid functions are given in the Examples section. In some fields, most notably in the context of artificial neural networks, the term "sigmoid function" is used as a synonym for "logistic function". Special cases of sigmoid functions include the Gompertz curve (used in modeling systems that saturate at large values of x) and the ogee curve (used in the spillway of some dams). Sigmoid functions have domain of all real numbers, with return (response) value commonly monotonically increasing but could be decreasing. Sigmoid functions most often show a return value (y axis) in the range 0 to 1. Another commonly used range is from −1 to 1. There is also the Heaviside step function, which instantaneously transitions between 0 and 1. A wide variety of sigmoid functions including the logistic and hyperbolic tangent functions have been used as the activation function of artificial neurons. Sigmoid curves are also common in statistics as cumulative distribution functions (which go from 0 to 1), such as the integrals of the logistic density, the normal density, and Student's t probability density functions. The logistic sigmoid function is invertible, and its inverse is the logit function. == Theory == In mathematics, a unitary sigmoid function is a bounded sigmoid-type function normalized to the unit range, typically with lower and upper asymptotes at 0 and 1. The theory proposed by Grebenc distinguishes three kinds of unitary sigmoid functions according to their asymptotic behavior and the presence or absence of oscillation near the asymptotes. A general form of a unitary sigmoid function is y = A S ( f ( x ) ) + B , {\displaystyle y=A\,S(f(x))+B,} where S {\displaystyle S} is an increasing sigmoid function, f ( x ) {\displaystyle f(x)} is a transformation of the independent variable, and A {\displaystyle A} and B {\displaystyle B} are constants controlling scaling and translation. === Classification === ==== 1st kind ==== A unitary sigmoid function of the first kind is a bounded increasing function that approaches its lower and upper asymptotes monotonically, without oscillation. This class includes many of the standard sigmoid functions used in statistics, biomathematics, and engineering, such as the logistic function and related generalizations. ==== 2nd kind ==== A unitary sigmoid function of the second kind is a bounded increasing function that oscillates near the upper asymptote while preserving an overall sigmoid transition. ==== 3rd kind ==== A unitary sigmoid function of the third kind is a bounded increasing function that oscillates near both the lower and upper asymptotes. These functions retain the global shape of a sigmoid curve but exhibit oscillatory behavior in the vicinity of both limiting states. === Taxonomy === The tables below show the taxonomy of unitary sigmoid functions of all three kinds. Table 1. Taxonomy matrix with examples of sigmoid functions of the 1st kind Table 2. Taxonomy matrix with examples of sigmoid functions of the 2nd kind on the unbounded interval Table 3. Taxonomy matrix with examples of sigmoid functions of the 3rd kind === Construction methods === The same theory presents a list of 30 methods for constructing sigmoid functions.. These include algebraic transformations, integration and convolution methods, constructions from bell-shaped functions, solutions of ordinary and partial differential equations, recursive schemes, stochastic differential equations, feedback systems, and chaotic systems. M0: Construction method for sigmoid functions not evident or intuitive M1: Inverse of singularity functions M2: Sigmoid functions of embedded positive functions M3: Rising a sigmoid function to the power M4: Exponentiating a sigmoid function M5: Symmetric sigmoid functions derived from asymmetric ones M6: Sigmoid functions of the reciprocal independent variable M7: Embedding a sigmoid function into other function M8: Sum of sigmoid functions M9: Multiplication of sigmoid functions M10: Integral of the product of an increasing and a decreasing function M11: Derivation from lambda (bell-shaped) functions M12: Integration of lambda (bell-shaped) function M13: Integration of the sum of lambda (bell-shaped) functions M14: Integration of the product of two lambda (bell-shaped) functions M15: Integration of the difference of two shifted sigmoid functions M16: Integration of the product of two shifted sigmoid functions M17: Convolution of sigmoid functions M18: Integration of the product of lambda and sigmoid function M19: Solutions of ordinary differential equations M20: Solutions of partial differential equation (PDE) M21: Solutions of functional differential equation (FDE) M22: Sum of a sigmoid function and some derivatives M23: Combination of sigmoid functions, its derivative and integral M24: Filtering sigmoid functions M25: Special cases of Gauss hypergeometric functions M26: Feedback closed-loop systems M27: Recursive functions M28: Recursive time-delayed feed-forward loops M29: Solutions of stochastic differential equation M30: Chaotic sigmoid functions Consult reference for more details. == Definition == A sigmoid function is a bounded, differentiable, real function that is defined for all real input values and has a positive derivative at each point. == Properties == In general, a sigmoid function is monotonic, and has a first derivative which is bell shaped. Conversely, the integral of any continuous, non-negative, bell-shaped function (with one local maximum and no local minimum, unless degenerate) will be sigmoidal. Thus the cumulative distribution functions for many common probability distributions are sigmoidal. One such example is the error function, which is related to the cumulative distribution function of a normal distribution; another is the arctan function, which is related to the cumulative distribution function of a Cauchy distribution. A sigmoid function is constrained by a pair of horizontal asymptotes as x → ± ∞ {\displaystyle x\rightarrow \pm \infty } . A sigmoid function is convex for values less than a particular point, and it is concave for values greater than that point: in many of the examples here, that point is 0. == Examples == Logistic function f ( x ) = 1 1 + e − x {\displaystyle f(x)={\frac {1}{1+e^{-x}}}} Hyperbolic tangent (shifted and scaled version of the logistic function, above) f ( x ) = tanh x = e x − e − x e x + e − x {\displaystyle f(x)=\tanh x={\frac {e^{x}-e^{-x}}{e^{x}+e^{-x}}}} Arctangent function f ( x ) = arctan x {\displaystyle f(x)=\arctan x} Gudermannian function f ( x ) = gd ( x ) = ∫ 0 x d t cosh t = 2 arctan ( tanh ( x 2 ) ) {\displaystyle f(x)=\operatorname {gd} (x)=\int _{0}^{x}{\frac {dt}{\cosh t}}=2\arctan \left(\tanh \left({\frac {x}{2}}\right)\right)} Error function f ( x ) = erf ( x ) = 2 π ∫ 0 x e − t 2 d t {\displaystyle f(x)=\operatorname {erf} (x)={\frac {2}{\sqrt {\pi }}}\int _{0}^{x}e^{-t^{2}}\,dt} Generalised logistic function f ( x ) = ( 1 + e − x ) − α , α > 0 {\displaystyle f(x)=\left(1+e^{-x}\right)^{-\alpha },\quad \alpha >0} Smoothstep function f ( x ) = { ( ∫ 0 1 ( 1 − u 2 ) N d u ) − 1 ∫ 0 x ( 1 − u 2 ) N d u , | x | ≤ 1 sgn ( x ) | x | ≥ 1 N ∈ Z ≥ 1 {\displaystyle f(x)={\begin{cases}{\displaystyle \left(\int _{0}^{1}\left(1-u^{2}\right)^{N}du\right)^{-1}\int _{0}^{x}\left(1-u^{2}\right)^{N}\ du},&|x|\leq 1\\\\\operatorname {sgn}(x)&|x|\geq 1\\\end{cases}}\quad N\in \mathbb {Z} \geq 1} Some algebraic functions, for example f ( x ) = x 1 + x 2 {\displaystyle f(x)={\frac {x}{\sqrt {1+x^{2}}}}} and in a more general form f ( x ) = x ( 1 + | x | k ) 1 / k {\displaystyle f(x)={\frac {x}{\left(1+|x|^{k}\right)^{1/k}}}} Up to shifts and scaling, many sigmoids are special cases of f ( x ) = φ ( φ ( x , β ) , α ) , {\displaystyle f(x)=\varphi (\varphi (x,\beta ),\alpha ),} where φ ( x , λ ) = { ( 1 − λ x ) 1 / λ λ ≠ 0 e − x λ = 0 {\displaystyle \varphi (x,\lambda )={\begin{cases}(1-\lambda x)^{1/\lambda }&\lambda \neq 0\\e^{-x}&\lambda =0\\\end{cases}}} is the inverse of the negative Box–Cox transformation, and α < 1 {\displaystyle \alpha <1} and β < 1 {\displaystyle \beta <1} are shape parameters. Smooth transition function normalized to (−1,1): f ( x ) = { 2 1 + e − 2 m x 1 − x 2 − 1 , | x | < 1 sgn ( x ) | x | ≥ 1 = { tanh ( m x 1 − x 2 ) , | x | < 1 sgn ( x ) | x | ≥ 1 {\displaystyle {\begin{aligned}f(x)&={\begin{cases}{\displaystyle {\frac {2}{1+e^{-2m{\frac {x}{1-x^{2}}}}}}-1},&|x|<1\\\\\operatorname {sgn}(x)&|x|\geq 1\\\end{cases}}\\&={\begin{cases}{\displaystyle \tanh \left(m{\frac {x}{1-x^{2}}}\right)},&|x|<1\\\\\operatorname {sgn}(x)&|x|\geq 1\\\end{cases}}\end{aligned}}} using the hyperbolic tangent mentioned above. Here, m {\displaystyle m} is a free parameter encoding the slope at x = 0 {\displaystyle x=0} , which must be great
Generalized iterative scaling
In statistics, generalized iterative scaling (GIS) and improved iterative scaling (IIS) are two early algorithms used to fit log-linear models, notably multinomial logistic regression (MaxEnt) classifiers and extensions of it such as MaxEnt Markov models and conditional random fields. These algorithms have been largely surpassed by gradient-based methods such as L-BFGS and coordinate descent algorithms.
Abdul Majid Bhurgri Institute of Language Engineering
Abdul Majid Bhurgri Institute of Language Engineering (Sindhi: عبدالماجد ڀرڳڙي انسٽيٽيوٽ آف لئنگئيج انجنيئرنگ) is an autonomous body under the administrative control of the Culture, Tourism and Antiquities Department, Government of Sindh established for bringing Sindhi language at par with national and international languages in all computational process and Natural language processing. == Establishment == In recognition to services of Abdul-Majid Bhurgri, who is the founder of Sindhi computing, Government of Sindh has established the institute after his name. The institute was primarily initiated on the concept given by a language engineer and linguist Amar Fayaz Buriro in briefing to the Minister, Culture, Tourism and Antiquities, Government of Sindh, Syed Sardar Ali Shah on 21 February 2017 on celebration of International Mother Language Day in Sindhi Language Authority, Hyderabad, Sindh. After the presentation and concept given by Amar Fayaz Buriro, the minister Syed Sardar Ali Shah had announced the Institute. Then, Government of Sindh added the development scheme in the Budget of fiscal year 2017-2018. == Projects == The Institute has developed several projects aimed at advancing the Sindhi language and promoting linguistic research. Notable initiatives include the AMBILE Hamiz Ali Sindhi Optical character recognition, which allows for the accurate digitization of Sindhi text, and the ongoing Sindhi WordNet System, a project to build a comprehensive lexical database for Natural language processing. The institute has also created the Font, which integrates symbols from the Indus script, Khudabadi script, and modern Perso-Arabic Script Code for Information Interchange into a single resource for researchers]. Additionally, institute has developed online converter tools that automatically transliterate between the Arabic-Perso script and Devanagari script, improving linguistic accessibility. Another key project is Bhittaipedia, a digital platform dedicated to the preservation and dissemination of the poetry of Shah Abdul Latif Bhittai, one of Sindh's most renowned poet. == Location == The institute is established behind Sindh Museum and Sindhi Language Authority, N-5 National Highway, Qasimabad, Hyderabad, Sindh.
LPBoost
Linear Programming Boosting (LPBoost) is a supervised classifier from the boosting family of classifiers. LPBoost maximizes a margin between training samples of different classes, and thus also belongs to the class of margin classifier algorithms. Consider a classification function f : X → { − 1 , 1 } , {\displaystyle f:{\mathcal {X}}\to \{-1,1\},} which classifies samples from a space X {\displaystyle {\mathcal {X}}} into one of two classes, labelled 1 and -1, respectively. LPBoost is an algorithm for learning such a classification function, given a set of training examples with known class labels. LPBoost is a machine learning technique especially suited for joint classification and feature selection in structured domains. == LPBoost overview == As in all boosting classifiers, the final classification function is of the form f ( x ) = ∑ j = 1 J α j h j ( x ) , {\displaystyle f({\boldsymbol {x}})=\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}}),} where α j {\displaystyle \alpha _{j}} are non-negative weightings for weak classifiers h j : X → { − 1 , 1 } {\displaystyle h_{j}:{\mathcal {X}}\to \{-1,1\}} . Each individual weak classifier h j {\displaystyle h_{j}} may be just a little bit better than random, but the resulting linear combination of many weak classifiers can perform very well. LPBoost constructs f {\displaystyle f} by starting with an empty set of weak classifiers. Iteratively, a single weak classifier to add to the set of considered weak classifiers is selected, added and all the weights α {\displaystyle {\boldsymbol {\alpha }}} for the current set of weak classifiers are adjusted. This is repeated until no weak classifiers to add remain. The property that all classifier weights are adjusted in each iteration is known as totally-corrective property. Early boosting methods, such as AdaBoost do not have this property and converge slower. == Linear program == More generally, let H = { h ( ⋅ ; ω ) | ω ∈ Ω } {\displaystyle {\mathcal {H}}=\{h(\cdot ;\omega )|\omega \in \Omega \}} be the possibly infinite set of weak classifiers, also termed hypotheses. One way to write down the problem LPBoost solves is as a linear program with infinitely many variables. The primal linear program of LPBoost, optimizing over the non-negative weight vector α {\displaystyle {\boldsymbol {\alpha }}} , the non-negative vector ξ {\displaystyle {\boldsymbol {\xi }}} of slack variables and the margin ρ {\displaystyle \rho } is the following. min α , ξ , ρ − ρ + D ∑ n = 1 ℓ ξ n sb.t. ∑ ω ∈ Ω y n α ω h ( x n ; ω ) + ξ n ≥ ρ , n = 1 , … , ℓ , ∑ ω ∈ Ω α ω = 1 , ξ n ≥ 0 , n = 1 , … , ℓ , α ω ≥ 0 , ω ∈ Ω , ρ ∈ R . {\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {\alpha }},{\boldsymbol {\xi }},\rho }{\min }}&-\rho +D\sum _{n=1}^{\ell }\xi _{n}\\{\textrm {sb.t.}}&\sum _{\omega \in \Omega }y_{n}\alpha _{\omega }h({\boldsymbol {x}}_{n};\omega )+\xi _{n}\geq \rho ,\qquad n=1,\dots ,\ell ,\\&\sum _{\omega \in \Omega }\alpha _{\omega }=1,\\&\xi _{n}\geq 0,\qquad n=1,\dots ,\ell ,\\&\alpha _{\omega }\geq 0,\qquad \omega \in \Omega ,\\&\rho \in {\mathbb {R} }.\end{array}}} Note the effects of slack variables ξ ≥ 0 {\displaystyle {\boldsymbol {\xi }}\geq 0} : their one-norm is penalized in the objective function by a constant factor D {\displaystyle D} , which—if small enough—always leads to a primal feasible linear program. Here we adopted the notation of a parameter space Ω {\displaystyle \Omega } , such that for a choice ω ∈ Ω {\displaystyle \omega \in \Omega } the weak classifier h ( ⋅ ; ω ) : X → { − 1 , 1 } {\displaystyle h(\cdot ;\omega ):{\mathcal {X}}\to \{-1,1\}} is uniquely defined. When the above linear program was first written down in early publications about boosting methods it was disregarded as intractable due to the large number of variables α {\displaystyle {\boldsymbol {\alpha }}} . Only later it was discovered that such linear programs can indeed be solved efficiently using the classic technique of column generation. === Column generation for LPBoost === In a linear program a column corresponds to a primal variable. Column generation is a technique to solve large linear programs. It typically works in a restricted problem, dealing only with a subset of variables. By generating primal variables iteratively and on-demand, eventually the original unrestricted problem with all variables is recovered. By cleverly choosing the columns to generate the problem can be solved such that while still guaranteeing the obtained solution to be optimal for the original full problem, only a small fraction of columns has to be created. ==== LPBoost dual problem ==== Columns in the primal linear program corresponds to rows in the dual linear program. The equivalent dual linear program of LPBoost is the following linear program. max λ , γ γ sb.t. ∑ n = 1 ℓ y n h ( x n ; ω ) λ n + γ ≤ 0 , ω ∈ Ω , 0 ≤ λ n ≤ D , n = 1 , … , ℓ , ∑ n = 1 ℓ λ n = 1 , γ ∈ R . {\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {\lambda }},\gamma }{\max }}&\gamma \\{\textrm {sb.t.}}&\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}+\gamma \leq 0,\qquad \omega \in \Omega ,\\&0\leq \lambda _{n}\leq D,\qquad n=1,\dots ,\ell ,\\&\sum _{n=1}^{\ell }\lambda _{n}=1,\\&\gamma \in \mathbb {R} .\end{array}}} For linear programs the optimal value of the primal and dual problem are equal. For the above primal and dual problems, the optimal value is equal to the negative 'soft margin'. The soft margin is the size of the margin separating positive from negative training instances minus positive slack variables that carry penalties for margin-violating samples. Thus, the soft margin may be positive although not all samples are linearly separated by the classification function. The latter is called the 'hard margin' or 'realized margin'. ==== Convergence criterion ==== Consider a subset of the satisfied constraints in the dual problem. For any finite subset we can solve the linear program and thus satisfy all constraints. If we could prove that of all the constraints which we did not add to the dual problem no single constraint is violated, we would have proven that solving our restricted problem is equivalent to solving the original problem. More formally, let γ ∗ {\displaystyle \gamma ^{}} be the optimal objective function value for any restricted instance. Then, we can formulate a search problem for the 'most violated constraint' in the original problem space, namely finding ω ∗ ∈ Ω {\displaystyle \omega ^{}\in \Omega } as ω ∗ = argmax ω ∈ Ω ∑ n = 1 ℓ y n h ( x n ; ω ) λ n . {\displaystyle \omega ^{}={\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}.} That is, we search the space H {\displaystyle {\mathcal {H}}} for a single decision stump h ( ⋅ ; ω ∗ ) {\displaystyle h(\cdot ;\omega ^{})} maximizing the left hand side of the dual constraint. If the constraint cannot be violated by any choice of decision stump, none of the corresponding constraint can be active in the original problem and the restricted problem is equivalent. ==== Penalization constant ==== D {\displaystyle D} The positive value of penalization constant D {\displaystyle D} has to be found using model selection techniques. However, if we choose D = 1 ℓ ν {\displaystyle D={\frac {1}{\ell \nu }}} , where ℓ {\displaystyle \ell } is the number of training samples and 0 < ν < 1 {\displaystyle 0<\nu <1} , then the new parameter ν {\displaystyle \nu } has the following properties. ν {\displaystyle \nu } is an upper bound on the fraction of training errors; that is, if k {\displaystyle k} denotes the number of misclassified training samples, then k ℓ ≤ ν {\displaystyle {\frac {k}{\ell }}\leq \nu } . ν {\displaystyle \nu } is a lower bound on the fraction of training samples outside or on the margin. == Algorithm == Input: Training set X = { x 1 , … , x ℓ } {\displaystyle X=\{{\boldsymbol {x}}_{1},\dots ,{\boldsymbol {x}}_{\ell }\}} , x i ∈ X {\displaystyle {\boldsymbol {x}}_{i}\in {\mathcal {X}}} Training labels Y = { y 1 , … , y ℓ } {\displaystyle Y=\{y_{1},\dots ,y_{\ell }\}} , y i ∈ { − 1 , 1 } {\displaystyle y_{i}\in \{-1,1\}} Convergence threshold θ ≥ 0 {\displaystyle \theta \geq 0} Output: Classification function f : X → { − 1 , 1 } {\displaystyle f:{\mathcal {X}}\to \{-1,1\}} Initialization Weights, uniform λ n ← 1 ℓ , n = 1 , … , ℓ {\displaystyle \lambda _{n}\leftarrow {\frac {1}{\ell }},\quad n=1,\dots ,\ell } Edge γ ← 0 {\displaystyle \gamma \leftarrow 0} Hypothesis count J ← 1 {\displaystyle J\leftarrow 1} Iterate h ^ ← argmax ω ∈ Ω ∑ n = 1 ℓ y n h ( x n ; ω ) λ n {\displaystyle {\hat {h}}\leftarrow {\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}} if ∑ n = 1 ℓ y n h ^ ( x n ) λ n + γ ≤ θ {\displaystyle \sum _{n=1}^{\ell }y_{n}{\hat {h}}({\boldsymbol {x}}_{n})\lambda _{n}+\gamma \leq \theta } then break h J ← h ^ {\displaystyle h_{J}\leftarrow {\hat {h}}} J