显示标签为“analysis”的博文。显示所有博文
显示标签为“analysis”的博文。显示所有博文

2014年6月11日星期三

MCMC算法简介

Other interesting/ ML MAP Bayesian: https://engineering.purdue.edu/kak/Tutorials/
Gibbs Motif finding: http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/gibbs.pdf

原文链接:百度贴吧  http://tieba.baidu.com/p/1681867134

       前天一个应用数学专业的朋友问我一个问题。这种类型的问题在工程上叫做求解反问题(inverse problem)。这种问题在他们看来是非常麻烦的。但是作为一个学统计的人而言,这种问题是再常见不过的了。也许是不同学科对问题的理解不同吧。我这里就引用这个例子介绍一下统计学的基本思想以及MCMC算法。
原始问题是这样的,有一个正问题,背景似乎是研究岩石断层什么的:

       幻灯片中的等式成立(由相关物理知识决定),称为forward problem。其中theta和phi是可以控制的量,称为输入。左侧的量称为输出,因此是输入量的函数。问题是:有颜色的参数是未知的。
       我们需要通过一组输入和输出的数据来估计参数,这样的问题称为反问题。从统计学角度上看,这个问题属于参数估计问题。
----------------------------------------
1、统计学/贝叶斯统计
我们首先要用统计语言重新描述这个问题:
       假设我们有n次试验,对应于theta和phi的不同组合。我们将第i次试验表述为

       其中epsilon_i是第i次实验的随机误差。
       假定epsilon_i服从独立同分布的正态分布。不妨假设正态分布的均值为0,因为如果不为0均值也可以被截距项A吸收掉。设正态分布方差为sigma^2,未知。
       统计学中的一个核心概念称为似然函数(likelihood function),它是观测到的量的概率分布。这里我们观测到R,所以就要写出R的联合概率分布。注意到R_i也是独立的正态分布,因此联合概率密度为

       由于概率密度要满足积分为1的正则性条件。因此统计上常常省略密度前面的常数项,然后用正比于表示所缺常数由正则性条件确定。
       然后我们这里应用贝叶斯统计的观点,认为参数也是有一定分布的。这是因为在样本量有限的情况下参数没办法准确确定,因此用一个分布来描述是合理的。假设我们给所有参数赋予无信息先验,根据贝叶斯公式,就得到后验密度

       贝叶斯统计认为参数的一切信息都包含在后验分布当中。于是我们只要研究这个后验密度函数就可以了。
       然而不幸的是,这个后验密度有5维,而且还不知道前面的归一化常数,因此没办法直观把握。于是贝叶斯统计中有了一个重要的边缘化的思想:考虑每个参数的边缘分布,即将其他参数积分掉。尽管贝叶斯统计历史悠久,这个边缘化思想却是近30年来随着Markov Chain Monte Carlo (MCMC)的兴起才开始出现的。
       简单地说,就是通过计算形如:

的式子求出每个参数的边缘分布,然后统计推断就结束了。
________________________________
*边缘分布(对除theta外其他变量的积分,从而消除其他变量影响)
       在介绍MCMC算法之前。我们先讲一下计算这个边缘分布的难点。第一个难点是归一化常数不知道,第二个则是高维数值积分本身的困难。
       因为这两个困难,目前认为最有效的算法是Monte Carlo算法。算法的基本思想是,产生服从后验分布的样本,设想如果我们能够产生服从P(A,B_1,B_2,\phi,\sigma^2|R)的样本,那么它的第一维就服从P(A|R),依此类推。如果我能产生N个样本,N足够大,我们就可以用样本的边缘分布近似总体的边缘分布,也就是说,取出样本的第一维,就可以得到A的近似后验分布。因此问题转化为了已知密度函数(缺归一化常数)的抽样问题。
_______________________________
2、MCMC算法
       MCMC不是一个算法,而是一类算法的总称。从数学上讲,算法的思想是产生一个Markov Chain,以目标分布为平稳分布。根据Markov Chain的理论,一个Markov Chain从任意初值出发,都会收敛到其平稳分布(如果存在)。注意这个收敛是依分布的。换句话说,如果我模拟了一条这样的马尔科夫链,去除掉前面一部分样本之后,就可以认为后面的样本来自于平稳分布。这样上面所述的抽样问题就解决了。
       MCMC与传统的独立抽样的关键区别在于:抽样的结果是相关的。理论上这对最终结果没有影响(数学上称为遍历理论)。然而实际上仍然有一系列的问题。其中最主要的是收敛诊断问题。和传统算法不同,MCMC的结果无法直接看出是否收敛。因此有的人认为使用MCMC需要慎重。但是根据我的经验,MCMC的表现基本还是可以相信的。
       2.1、Metropolis算法
       史上第一个MCMC算法诞生于1942年,现在称为Metropolis算法。
       这个算法首先要求一个状态空间上的对称转移函数。即设x,y是状态空间上任意两点,则从x转移到y的概率和从y转移到x的概率相等。
       Metropolis算法描述如下:
设x是上一次的状态,通过对称转移函数得到新状态x',然后抽取随机变量U服从(0,1)上的均与分布,如果
1)U<=q(x')/q(x),则markov chain转移到x';
2)U>q(x')/q(x),则markov chain保持不变,仍为x,
其中q是抽样的目标的分布。
容易证明这样构造的markov chain以q为平稳分布。
       这个算法有一个推广,称为Hasting's Generalization。如果转移函数不是对称的,只需要将q(x')/q(x)改为{q(x')p(x'->x)}/{q(x)p(x->x')},其中p(x'->x)是从x'转移到x的概率。
       2.2、Gibbs抽样
       Metropolis是一个包打天下的算法。但是和其他一切适用范围广的算法一样,这个算法收敛是很慢的。统计中最常见的MCMC算法称为Gibbs抽样,它可以看做是一种特殊的Metropolis算法。
       Metropolis算法的主要问题,是算法效率严重依赖于转移函数的选取。如果选得不好,算法表现会很差。Gibbs抽样则不存在这样的问题,但是它要求被抽样的函数具有一定的形式。Gibbs抽样主要针对高维抽样问题。这种问题如果直接用Metropolis会变得很难。Gibbs抽样的想法是:既然n维抽样很难,我们就把他化成n个一维的抽样。
      这里为了简单起见,我们举一个二维的例子,更高的维度可以直接推广:
设目标分布为q(x,y),我们取初值(x_0,y_0),Gibbs抽样一次迭代为
1)抽取x_1服从q(x|y_0),
2)抽取y_1服从q(y|x_1),
这样就得到了(x_1,y_1)。一直重复下去就得到需要的链。
       很显然这个算法要求两个条件分布q(x|y)和q(y|x)具有简单的形式,否则这两个一维抽样也是不可以实现的。当然如果一维抽样不能直接实现,还可以通过嵌入Metropolis算法,用一个接受/拒绝的过程代替直接从条件分布中抽样。
和Metropolis算法相比Gibbs抽样少了拒绝的步骤,这是一般情况下Gibbs抽样效果更好的原因。
——————————————
       在介绍了两种基本算法之后,我们回到原来的问题。由于这个问题是多维的,我们首先考虑Gibbs抽样。
 I、让我们来看看每个参数的条件分布是什么:
       1、首先,A在给定B_1,B_2,phi,sigma^2下的分布是什么呢?
        答案是正态分布,因为分布的形式为exp{-“A的二次函数”},这是正态分布的核(回顾一下我们看分布的时候是不关心前面的常数系数的,所以看到这样的函数形式,就可以确定它是正态分布了)。事实上,(A,B_1,B_2)这个三维向量在给定phi和sigma^2的条件下服从联合正态分布(核的形式为exp{-“A,B_1,B_2的二次型”})。经过配方(由矩阵运算可以迅速得到),可以算出这个正态分布的均值和协方差矩阵。
       2、然后,sigma^2在给定A,B_1,B_2,phi下是什么分布呢?
       我们注意到如果把sigma^2换成1/sigma^2就具有gamma分布的形式。所以这个分布被称为inverse gamma分布。
       3、最后我们来看phi在给定A,B_1,B_2,sigma^2下的分布。
       这里补充一下:原始物理问题有个约束条件,phi取值于0°到45°之间。非常不幸的是,phi的分布不属于任何已知的分布类型。因此对于phi的抽样我们只能借助metropolis算法来实现了。
当然这里要怎么选取转移函数也是一个可以讨论的问题。但是我考虑到phi的取值范围比较小,就使用一种最笨的抽样方式来解决了。
       我使用独立的[0°,45°]的均匀分布作为转移。也就是说,不管上一次的结果是什么,下一次的新值都从这个均匀分布中独立的产生。这个转移函数显然是对称的。然后用metropolis定义的概率进行接受或拒绝就行了。这个转移函数的缺点是不能利用上次成功的经验,但是优点是两个点之间相关性会减小(如果接受)。由于这个问题本身的困难程度不大,只要抽样的次数足够多(如抽10W次),就可以比较精确得得到后验分布了。
    II、再讲一下抽样完毕以后如何做分析:
       首先要砍掉前面没有达到平稳的点,称为burn-in。对于这种简单问题砍掉5000个点已经绰绰有余了。然后对于剩下的点,一维维的画直方图,或者做密度估计,都可以。一维问题总是很容易处理的,通过画图你一定会对你感兴趣的参数获得认识了。
END
--------------------------讨论-------------------
     1、请问 怎么证明这个算法的正确性 比如说 他的不可约 平稳分布和极限分布是否相同等等
       一个Markov chain收敛条件是不可约、非周期、正常返。这三个条件是容易成立的(只要模型可识别)。至于极限分布是不是想要的分布,只要验证目标分布是这个迭代算法的不动点就行了。对于大多数的问题这种验证都是平凡的,因此在统计文献中一般都省略此步骤。
      2、在运用了MCMC后,你文中最后得到的结果应该是待估计参数的边缘后验分布吧,但实际运用中需要估计参数的确切值,这个确切的值是多少?比如A1的值估计出来为多少?
       贝叶斯统计认为,参数的所有信息都包含在后验分布当中。同时,通过有限的样本是无法准确估计参数的,因此用后验分布来表示参数的不确定性。
       如果需要点估计,可以根据实际情况选取后验均值或众数(posterior mode)。但是这样的方法会忽略参数的不确定性。因此我建议在后续计算中选用可以保留这种不确定性的方法。最近应用数学中有个很火的领域叫uncertainty quantification,与此相关。
................
—————MCMC资源————原文链接:http://asc.2dark.org/node/18
google:MCMC tutorial
David MacKay's book(electronic version availiable):
http://www.inference.phy.cam.ac.uk/mackay/itila/

2014年4月29日星期二

Lecture about Big Data

Business sas
what we need?
statistics, data mining, forecasting, text analyzing, optimization, visualize

Who owns data?
companies own data, but not using it. dark data
earned paid open

How to analysis?
traditional : database -> analysis
in database 
in memory

What to do?
invest in and nurture the concept of  data analytic

What's the value?
help improve business
machine learning helps retrieve info

Hal Varian 

Technology
nell: never ending learning language
watson: 机器学习能力的一种体现,对自然语言的理解能力和联想能力

data visualization helps understanding
power of the plane

THE WORLD'S TOP 10 MOST INNOVATIVE COMPANIES IN BIG DATA





2014年4月19日星期六

Reading IBM annual report 2013

Ref: http://www.ibm.com/annualreport/2013/chairmans-letter.html

What will we make of this moment—as businesses, as individuals, as societies?

What will we make with a planet generating unprecedented amounts of data? What will we create from—and with—global networks of consumers, workers, citizens, students, patients? How will we make use of powerful business and technology services available on demand? How will we engage with an emerging global culture, defined not by age or geography, but by people determined to change the practices of business and society?

Dear IBM Investor:
What will we make of this moment—as businesses, as individuals, as societies?

What will we make with a planet generating unprecedented amounts of data? What will we create from—and with—global networks of consumers, workers, citizens, students, patients? How will we make use of powerful business and technology services available on demand? How will we engage with an emerging global culture, defined not by age or geography, but by people determined to change the practices of business and society?
Virginia M. Rometty
Chairman, President and Chief Executive Officer
To capture the potential of this moment, IBM is executing a bold agenda. It is reshaping your company, and we believe it will reshape our industry. In this letter I will describe the actions we have taken and are taking, and the changed company that is emerging from this transformation. I believe that if you understand our strategy, you will share our confidence in IBM’s prospects—for the near term, for this decade and beyond.
Let’s start with the phenomenon of our age—data.

A planet of data

Today, every discussion about changes in technology, business and society must begin with data. In its exponentially increasing volume, velocity and variety, data is becoming a new natural resource. It promises to be for the 21st century what steam power was for the 18th, electricity for the 19th and hydrocarbons for the 20th. This is what we mean by enterprises, institutions and our planet becoming smarter.
Thanks to a proliferation of devices and the infusion of technology into all things and processes, the world is generating more than 2.5 billion gigabytes of data every day, and 80 percent of it is “unstructured”—everything from images, video and audio to social media and a blizzard of impulses from embedded sensors and distributed devices.
This is the driver of IBM’s first strategic imperative:
To make markets by transforming industries and professions with data. 

 
The market for data and analytics is estimated at $187 billion by 2015. To capture this growth potential, we have built the world’s broadest and deepest capabilities in Big Data and analytics—both technology and expertise. We have invested more than $24 billion, including $17 billion of gross spend on more than 30 acquisitions. We have 15,000 consultants and 400 mathematicians. Two-thirds of IBM Research’s work is now devoted to data, analytics and cognitive computing. IBM has earned 4,000 analytics patents. We have an ecosystem of 6,000 industry partners and 1,000 university partnerships around the world developing new, analytics-related curricula.

IBM provides the full array of capabilities our clients need to extract the value of Big Data. They can mine multiple structured and unstructured data sets across their business. They can apply a range of analytics—from descriptive to predictive to prescriptive. And importantly, they can capture the time value of data. This matters, because the battle for competitive advantage in this new world can be lost or won in fractions of a second.
(sounds like quant investment)

Our data and analytics portfolio today is the deepest in the industry. It includes decision management, content analytics, planning and forecasting, discovery and exploration, business intelligence, predictive analytics, data and content management, stream computing, data warehousing, information integration and governance.
“Traditional computing systems, which only do what they are programmed to do, simply cannot keep up with Big Data in constant motion.”
This portfolio provides the basis for the next major era in computing—cognitive systems. Traditional computing systems, which only do what they are programmed to do, simply cannot keep up with Big Data in constant motion. For that, we need a new paradigm. These new systems are not programmed; rather, they learn, from the vast quantities of information they ingest, from their own experiences, and from their interactions with people. 

IBM launched this era three years ago, when our Watson system defeated the two all-time champions on the quiz show Jeopardy! Watson has since matured from a research grand challenge into a multifaceted business platform, enabled globally via the cloud. Earlier this year we launched the IBM Watson Group. It will comprise 2,000 professionals, a $1 billion investment and an ecosystem of partners and developers that we expect to scale rapidly. In the process, we believe Watson will change the nature of computing, as it is already beginning to change the practice of healthcare, retail, travel, banking and more.
Taken together, our investments in data and analytics are driving significant growth, with 40,000 service engagements to date, growing by double digits. In 2013 our business analytics revenue rose 9 percent—led by Global Business Services and Software. This is already a nearly $16 billion business for us, and we have raised our expectations for it.

An IT industry remade by cloud

At the same time that industries and professions are being remade by data, the information technology infrastructure of the world is being transformed by the emergence of cloud computing—that is, the delivery of IT and business processes as digital services. It is estimated that by 2016, more than one-fourth of the world’s applications will be available in the cloud, and 85 percent of new software is now being built for cloud.
This is driving IBM’s second strategic imperative:
To remake the enterprise IT infrastructure for the era of cloud.

As important as cloud is, its economic significance is often misunderstood. That lies less in the technology, which is relatively straightforward, than in the new business models cloud will enable for enterprises and institutions. This is creating a market that is expected to reach $250 billion by 2015.
“Cloud’s long-term significance lies less in its technology than in the new business models it will enable for enterprises and institutions.”
IBM today is the leader in enterprise cloud, a position we have enhanced through investments of $7 billion on 15 acquisitions, most notably SoftLayer in 2013. We provide the full spectrum of cloud delivery models—infrastructure as a service, platform as a service, software as a service and business process as a service. IBM’s cloud capabilities are built on 1,500 cloud patents and supported by thousands of cloud experts. Eighty percent of Fortune 500 companies use IBM’s cloud capabilities.
Our cloud foundation at the infrastructure level is SoftLayer, the market’s premier public and private cloud environment, with “bare metal” dedicated servers that provide unmatched compute power, deployed in real time, with hundreds of configuration options. Our public cloud processes 5.5 million client transactions every day.
In terms of technology, security, flexibility and pricing, IBM surpasses all our major competitors. And our rapidly growing roster of 30,000 client engagements—including companies like Honda, Sun Life Stadium, US Open Tennis and hundreds of top online games with a user base exceeding 100 million—is a testament to that.
These companies and a growing number of others understand that their customer-facing applications—which they deploy on public clouds for reasons of cost, accessibility and speed—must be integrated with their core enterprise systems—such as finance, inventory, manufacturing and human resources. This is why one analyst predicts that by 2017, nearly 50 percent of large enterprises will use hybrid cloud environments that are part public, part private and integrated with back-end systems.
It is also why a new class of “cloud middleware services” is emerging to manage these complex environments. Last month we announced several capabilities that will connect enterprise data and applications to the cloud. IBM’s entire enterprise software portfolio is becoming available to developers in an open, composable business environment to build applications with flexibility and scalability. A “cloud first” approach is being implemented in IBM software development labs globally.
For line-of-business users looking to drive innovation—including heads of finance, marketing, human resources, procurement and other functions—we offer an unmatched array of more than 100 software-as-a-service (SaaS) offerings. IBM’s SaaS offerings today support 24 of the top 25 companies in the Fortune 500. Going forward, companies will continue to unlock the value of these business applications. For example, nearly 70 percent of organizations are currently using or planning to use composable business services.
Finally, enterprises will want—and need—to manage their data in the cloud with the same rigor as if it were on-premises. Companies will do this in order to ensure auditability, visibility, change control, access control and data loss protection. Indeed, data management will arguably be the single most important design point for enterprise cloud environments, driven not only by security and cost, but also by regulation.
To meet growing demand for greater speed, and legal requirements for compliance and data residency, IBM is aggressively expanding its global cloud footprint. We currently have 25 data centers globally, and the new $1.2 billion investment announced in January will see the opening of 15 more, in the US, the UK, Australia, Brazil, Canada, China, France, Germany, India, Japan and Mexico.
The impact of our cloud investments shows up clearly in our results. IBM’s cloud business grew 69 percent in 2013, delivering $4.4 billion of revenue. As we actively embrace cloud in order to deliver “IBM as a Service” to our clients, we expect to see significant benefits in client experience, revenue growth and enterprise productivity.

Engagement in a world of empowered individuals

The phenomena of data and cloud are changing the arena of global business and society. At the same time, proliferating mobile technology and the spread of social business are empowering people with knowledge, enriching them through networks and changing their expectations.
This leads to IBM’s third strategic imperative:
To enable “systems of engagement” for enterprises.

Complementing traditional back-office systems of record, enterprises are now taking a systematic approach to engagement with all of their constituencies—customers, employees, partners, investors and citizens. Indeed, 57 percent of companies now expect to devote more than a quarter of their IT spending to these new systems of engagement by 2016, nearly twice the level of 12 months ago.
“Enterprises are now taking a systematic approach to engagement with all of their constituencies—customers, employees, partners, investors and citizens.”
They are doing so because the way their customers and their own workers expect to engage is undergoing profound change. Seventy percent of people who contact a company via social media today expect a response within five minutes. Nearly 80 percent of adult smartphone users keep their phones with them an average of 22 hours a day. This is why we launched IBM MobileFirst in 2013, and why we have made eight acquisitions to advance our mobile initiatives. We have 3,000 mobile experts, and have been awarded hundreds of patents in mobile and wireless technologies.
When these individuals use their mobile devices to engage with a company, they expect personalized service. Indeed, 80 percent of people are willing to trade their information for a customized offering.
The good news is that this is increasingly possible, thanks to social business and data analytics. But it’s not that simple. One only needs to follow the news to see rapidly rising concerns—legitimate concerns—about data security and institutional trust. Two-thirds of US adults say they would not return to a business that lost their confidential information. And the economic stakes are enormous. One analyst estimates that by 2016, there could be an additional $1 trillion of growth in global online retail—if the industry can enhance trust.
We have strengthened our already clear leadership in enterprise-class social business and in security. Our acquisitions in social include Kenexa, which helps companies use behavioral science not just to connect with people, but to understand and build lasting engagement with them. And we have made a dozen acquisitions in security, building a capability of more than 6,000 security experts, 3,000 patents and 25 labs worldwide.
Finally, IBM is leading by example in building modern enterprise systems of engagement and learning. Our social platform, Connections, has 300,000 IBM users and 200,000 communities. There are more than 30,000 IBMers active on Client Collaboration Hubs for our top 300 accounts. Last year, hundreds of thousands of IBMers worldwide shaped the practices that define how we work. And they are enhancing their skills daily through a massive open online learning system called THINK Academy.
In 2013, we achieved year-over-year growth of 69 percent in mobile, 19 percent in security and 45 percent in social business.

Our performance in 2013

You can learn more about the IBM Strategy here. This is the context in terms of which to understand our performance in 2013.
By many measures, it was a successful year for IBM. Our diluted operating earnings per share in 2013 were $16.28, a new record. This marked 11 straight years of operating EPS growth. We grew operating net income by 2 percent, to $18 billion.
Generating Higher Value at IBM: Learn how we manage our business for the long term.
In 2013 we invested $3.1 billion for 10 acquisitions. We invested $3.8 billion in net capital expenditures. We invested $6.2 billion in R&D, while earning the most US patents for the 21st straight year.
While making all these investments in IBM’s future capabilities, we were able to return $17.9 billion to you in 2013—approximately $13.9 billion through gross share repurchases and $4.1 billion through dividends. Last year’s dividend increase was 12 percent, marking the 18th year in a row in which we have raised our dividend, and the 98th consecutive year in which we have paid one.
However, we must acknowledge that while 2013 was an important year of transformation, our performance did not meet our expectations. Our operating pre-tax income was down 8 percent. Our revenue in 2013, at $99.8 billion, was down 5 percent as reported and 2 percent at constant currency.
So, while we continue to remix to higher value, we must also address those parts of our business that are holding us back. We have two specific challenges, and we are taking steps to address both.
The first involves shifting the IBM hardware business for new realities and opportunities. We are accelerating the move of our Systems product portfolio—in particular, Power and storage—to growth opportunities and to Linux, following the lead of our successful mainframe business. The modern demands of Big Data, cloud and mobile require enterprise-strength computing, and no other company can match IBM’s ongoing capabilities and commitment to developing those essential technologies.
We also announced, in January, an agreement to sell much of our Intel-based x86 server business to Lenovo. This divestiture is consistent with our continuing strategy of exiting lower-margin businesses, such as PCs, hard-disk drives and retail store solutions. But let me be clear—we are not exiting hardware. IBM will remain a leader in high-performance and high-end systems, storage and cognitive computing, and we will continue to invest in R&D for advanced semiconductor technology.
The second challenge involves the world’s growth markets. While IBM’s growth in Latin America and Middle East and Africa was strong, enterprise spending slowed in other key growth markets. We are intensifying focus on new growth opportunities. Overall, the opportunity in the world’s growth markets remains attractive.

On being essential

As we have learned throughout our history, the key to success is getting the big things right, innovating and investing accordingly, and challenging our organization, operations and especially our culture to adapt.
The IBM Strategy - We are making a new future for our clients, our industry and our company. Learn how.
When you do all those things, you do more than stay abreast of change. You lead it. You invent entirely new capabilities—such as cognitive computing and Watson. You translate these innovations into sustainable economic value—such as building cloud infrastructure that is enterprise-class and societally robust. And you make yourself a laboratory for the future—of work, of engagement, of the modern enterprise.
The progress we are making on these strategic imperatives is highly encouraging. No company in our industry is positioned as strongly as 103-year-old IBM for the world now taking shape. We are confident in our vision, our strategy and our prospects.
Every generation of IBMers has the opportunity—and, I believe, the responsibility—to invent a new IBM. This is our time. We are working to make this not just a successful business, but an essential institution for our clients and the world in a new era.
I am deeply proud of the global IBM team for bringing us here, and I am grateful to you, our shareholders, for your unwavering support. I hope you share our excitement about your company’s path and the shared opportunity we have, together, to build a brighter future on a smarter planet.
Signature of Virginia M. Rometty
Virginia M. Rometty
Chairman, President and Chief Executive Officer