{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/3386"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/3386","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Algorithms for Mixture Models","abstract":"Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\\em any} algorithm which guarantees accurate reconstruction. Second for the case of \\emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy.","abstract_html":"Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\\em any} algorithm which guarantees accurate reconstruction. Second for the case of \\emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy.","abstract_has_math":false,"creators":["Sandler, Mark Moiseevich"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006-07-28T20:54:45Z","date_published":"2006-07-28T20:54:45Z","updated_at":"2026-11-19T03:16:49Z","subjects":["Mixture Models","Collaborative Filtering","Theoretical Computer Science"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475857"],"render_values":[{"text":"6475857","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/3386","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/3386","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F3386","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Sandler, Mark Moiseevich"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-07-28T20:54:45Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-07-28T20:54:45Z"]},{"key":"dc:date.issued","label":"Date","values":["2006-07-28T20:54:45Z"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mixture Models","Collaborative Filtering","Theoretical Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475857"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/3386"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"0f536bec-8bd2-48eb-99cb-047f12884eb0\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Algorithms for Mixture Models</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2006-07-28T20:54:45Z</PublicationDate> <Authors> <Author> <DisplayName>Sandler, Mark Moiseevich</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Mixture Models</Keyword> <Keyword>Collaborative Filtering</Keyword> <Keyword>Theoretical Computer Science</Keyword> <Abstract>Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\\em any} algorithm which guarantees accurate reconstruction. Second for the case of \\emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Sandler, Mark Moiseevich"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\\em any} algorithm which guarantees accurate reconstruction. Second for the case of \\emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["2113545 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms for Mixture Models"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"0f536bec-8bd2-48eb-99cb-047f12884eb0\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Algorithms for Mixture Models</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2006-07-28T20:54:45Z</PublicationDate> <Authors> <Author> <DisplayName>Sandler, Mark Moiseevich</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Mixture Models</Keyword> <Keyword>Collaborative Filtering</Keyword> <Keyword>Theoretical Computer Science</Keyword> <Abstract>Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\\em any} algorithm which guarantees accurate reconstruction. Second for the case of \\emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Sandler, Mark Moiseevich"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Sandler, Mark Moiseevich"],"dc:date.accessioned":["2006-07-28T20:54:45Z"],"dc:date.available":["2006-07-28T20:54:45Z"],"dc:date.issued":["2006-07-28T20:54:45Z"],"dc:description.abstract":["Mixture models form one of the most fundamental classes of generative models for clustered data. Specific application examples include text classification problems, image segmentation and motion detection, collaborative filtering and many others. However, quite surprisingly, very little had been known about algorithms which have provable performance guarantees within the framework of mixture models. This is the topic we study in this work. Our contribution is twofold. First, for the canonical problem of separating mixtures of continuous distributions in the high-dimensional Euclidean space, we provide the first algorithm that can learn distributions with heavy tails, including those with infinite variance and expectation. We formulate necessary conditions and provide an algorithm which guarantees that the underlying mixture model can be learned by observing only polynomially many samples. We also show that for many classes of distributions, our separation conditions are necessary for {\\em any} algorithm which guarantees accurate reconstruction. Second for the case of \\emph{discrete mixture models} we give an efficient polynomial time algorithm with provable performance guarantees. Recasting of our algorithm for the text classification problem immediately results in a very fast unsupervised learning method, with an excellent classification accuracy."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.extent":["2113545 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6475857"],"dc:identifier.uri":["https://hdl.handle.net/1813/3386"],"dc:language.iso":["en_US"],"dc:subject":["Mixture Models","Collaborative Filtering","Theoretical Computer Science"],"dc:title":["Algorithms for Mixture Models"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:16:49Z"}