Mailing-List: contact dev-help@mahout.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@mahout.apache.org
Received-SPF: pass (nike.apache.org: domain of dlieu.7@gmail.com designates
 209.85.220.170 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <812FA692-53B6-4669-9EE2-7F9C648BC7FB@gmail.com>
References: <loom.20111205T045620-880@post.gmane.org>
	<CAPud8ToFnKYDGTAz9bHnwu+mf2Gjwsz9skLZ5zO2N3FPp3gkLQ@mail.gmail.com>
	<CAJkvnmy-MsFsjQpD64DQ+PF1izRSymhus3=W3XYj1cQ9-3p0gw@mail.gmail.com>
	<CAPud8ToEmk0yUkoHp-8rrSGA7VpV0h=eo6dUBz4CMGATQuHYtA@mail.gmail.com>
	<CAJwFCa3+isegijAbNTUVAXHJ31eg3RbiR5Rt68ui0dfOSnGtCg@mail.gmail.com>
	<CAPud8TrstH5wpp3F5NEFbzNe09ph+OATPnc24eV_hzBhs_RE1A@mail.gmail.com>
	<812FA692-53B6-4669-9EE2-7F9C648BC7FB@gmail.com>
Date: Mon, 5 Dec 2011 14:05:29 -0800
Message-ID: 
 <CAPud8TqwC=tpX7WUzGqEqhBJB36bqcMOP3Rb0eWEcvdJiD-uRQ@mail.gmail.com>
Subject: Re: When is PCA expected to be fully implemented into Mahout?
From: Dmitriy Lyubimov <dlieu.7@gmail.com>
To: dev@mahout.apache.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

what i usually do for small products is to accumulate them in the map
without combiners and then send them to reducers to combine there.
Using combiners creates local sort for something you don't really want
to do unless you can't keep it in memory .

you also have a choice to force one reducer to ensure one product. Or
(what i do) build a loader that just goes all vectors and reduce them
on the fly whenever it is needed.

MR is fundamentally too often not so cool when it comes to linear
algebra operations. This is a major deficiency as far as i see it.
Because it forces to sort output which already have inner structure
that one can capitalize on.

Simple example: suppose you want to deinterlace a TV signal. So you
have two fields, one for odd lines, and another for even lines. So
naturally, what you do is just create a simple mering algorithm that
reads lines from each of inputs intermittently and outputs one single
deinterlaced frame. O(n).

now, mapreduce way to deal with it is to shuffle and sort all lines by
their line No and then output total order (O(n*logN)

so dealing with large blocks is like deinterlacing. you sort it but
you absolutely don't have to because you already have structure in the
output (even if blocks are not fitting in the memory). so hence.


On Mon, Dec 5, 2011 at 1:02 PM, Raphael Cendrillon
<cendrillon1978@gmail.com> wrote:
> Thanks for clarifying. I think we're all on the same page on this, althou=
gh using different terms. I'll package up the job I currently have for this=
 and submit a patch.
>
> By the way, currently I have the rows being added at the combiner, and th=
en the results of the combiners added in a single reducer. Do you think thi=
s is sufficient, or should multiple reducers be used (per column) to furthe=
r spread the load?
>
> On Dec 5, 2011, at 11:38 AM, Dmitriy Lyubimov <dlieu.7@gmail.com> wrote:
>
>> ok column-wise mean. (the mean of all rows).
>>
>> On Mon, Dec 5, 2011 at 11:00 AM, Ted Dunning <ted.dunning@gmail.com> wro=
te:
>>> Row-wise mean usually means that a mean of each row is computed.
>>>
>>> I think that most PCA users would want column-wise means for subtractio=
n.
>>>
>>> On Mon, Dec 5, 2011 at 10:58 AM, Dmitriy Lyubimov <dlieu.7@gmail.com> w=
rote:
>>>
>>>> We probably need =A0row wise mean computation job anyway as a separate=
 mr
>>>> step. Wanna take a stab?
>>>> On Dec 5, 2011 10:34 AM, "Raphael Cendrillon" <cendrillon1978@gmail.co=
m>
>>>> wrote:
>>>>
>>>>> Given that this request seems to come up frequently, would it be wort=
h
>>>>> putting this approach under mahout-examples? =A0Initially it could us=
e the
>>>>> brute force approach together with SSVD, and updated later once suppo=
rt
>>>> is
>>>>> ready for mean-subtraction within SSVD.
>>>>>
>>>>> I could put something together if there's interest.
>>>>>
>>>>> On Mon, Dec 5, 2011 at 9:40 AM, Dmitriy Lyubimov <dlieu.7@gmail.com>
>>>>> wrote:
>>>>>
>>>>>> I am working on the addtions to ssvd algorithms and the mods to curr=
ent
>>>>>> solver will probably emerge in a matter of a month, my schedule
>>>>> permitting.
>>>>>>
>>>>>> However, a brute force approach is already possible. If your input i=
s
>>>> of
>>>>>> moderate size, or if it is already dense, you could compute median a=
nd
>>>>>> substract it yourself very easily and then shove it into ssvd solver
>>>>> while
>>>>>> requesting to produce either u or v depending if subtract column wis=
e
>>>> or
>>>>>> row wise mean.
>>>>>>
>>>>>> The only problem with brute force approach is that it would densify
>>>>>> originally sparse input. Depending on your problem and # of machine
>>>> nodes
>>>>>> you can spare, it may or may not be a problem.
>>>>>> On Dec 4, 2011 7:59 PM, "magicalo" <magica1980@yahoo.com> wrote:
>>>>>>
>>>>>>> Hello,
>>>>>>>
>>>>>>> Is there an expected release date for the PCA algorithm as part of
>>>>>> Mahout?
>>>>>>> Tx!
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>