Building Web Reputation Systems- P6


lượt xem

Building Web Reputation Systems- P6

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Building Web Reputation Systems- P6:Today’s Web is the product of over a billion hands and minds. Around the clock and around the globe, people are pumping out contributions small and large: full-length features on Vimeo, video shorts on YouTube, comments on Blogger, discussions on Yahoo! Groups, and tagged-and-titled bookmarks. User-generated content and robust crowd participation have become the hallmarks of Web 2.0.

Chủ đề:

Nội dung Text: Building Web Reputation Systems- P6

  1. model is activated by a specific input arriving as a message to the model. Input gets the ball rolling. Based on the requirements of custom reputation processes, there can be many different forms of input, but a few basic input patterns provide the common basic structure. Typical inputs. Normally, every message to a reputation process must contain several items: the source, the target, and an input value. Often, the contextual claim name and other values, such as a timestamp and a reputation process ID, also are required for the reputation system to initialize, calculate, and store the required state. Reputation statements as input. Our diagramming convention shows reputation statements as inputs. That’s not always strictly accurate—it’s just shorthand for the common method in which the application creates a reputation statement and passes a message containing the statement’s context, source, claim, and target to the model. Don’t con- fuse this notational convention with the case when a reputation statement is the target of an input message, which is always represented as a embedded miniature version of the target reputation statement. See “Reputation Targets: What (or Who) Is the Focus of a Claim?” on page 25. Periodic inputs. Sometimes reputation models are activated on the basis of an input that’s not reputation based, such as a timer that will perform an external data transform. At present, this grammar provides no explicit mechanism for reputation models to spon- taneously wake up and begin executing, and this has an effect on mechanisms such as those detailed in “Freshness and decay” on page 63. So far, in our experience, spon- taneous reputation model activation is not necessary and keeping this constraint out has simplified high-performance implementations. However, there is no particular universal requirement for this limitation. Output Many reputation models terminate without explicitly returning a value to the applica- tion at all. Instead, they store the output asynchronously in reputation statements. The application then retrieves the results as reputation statements as they are needed— always getting the best possible result, even if it was generated as the result of some other user on some other server in another country. Return values. Simple reputation environments, in which all the model is implemented serially and executed in-line with the actual input actions, are usually implemented using on request-reply semantics: the reputation model runs for exactly one input at a time and runs until it terminates by returning a copy of the roll-up value that it calcu- lated. Large-scale, asynchronous reputation frameworks, such as the one described in Appendix A, don’t return results in this way. Instead, they terminate silently and some- times send signals (see the next paragraph). Signals: Breaking out of the reputation framework. Sometimes a reputation model needs to no- tify the application environment that something significant has happened and special handling is required. To accomplish this, the process sends a signal: a message that 56 | Chapter 3: Building Blocks and Reputation Tips
  2. breaks out of the reputation framework. The mechanism of signaling is specific to each framework implementation, but in our diagramming grammar, signaling is always rep- resented by an arrow leaving the box. Logging. A reputation logging process provides a specialized form of output: it records a copy of the current score or message into an external store, typically using an asyn- chronous write. This action is usually the result of an evaluator deciding that a signif- icant event requires special output. For example, if a user karma score has reached a new threshold, an evaluator may decide that the hosting application should send the user a congratulatory message. Practitioner’s Tips: Reputation Is Tricky When you begin designing a reputation model and system using our graphical gram- mar, it may be tempting to take elements of the grammar and just plug them together in the simplest possible combinations to create an Amazon-like rating and review sys- tem, or a Digg-like voting model, or even a points-based karma incentive model as on StackOverflow. In practice—“in the wild,” where people with myriad personal incen- tives interact with them both as sources of reputation and as consumers—the imple- mentation of reputation systems is fraught with peril. In this section, we describe several pitfalls to avoid in designing reputation models. The Power and Costs of Normalization We make much of normalization in this book. Indeed, in almost all of the reputation models we describe, calculations are performed on numbers from 0.0 to 1.0, even when normalization and denormalization might seem to be extraneous steps. Here are the reasons that normalization of claim values is an important, powerful tool for reputation: Normalized values are easy to understand Normalized claim values are always in a fixed, well-understood range. When ap- plications read your claim values from the reputation database, they know that 0.5 means the middle of the range. Without normalization, claim values are ambigu- ous. A claim value of 5 could mean 5 out of 5 stars, 5 on a 10-point scale, 5 thumbs up, 5 votes out of 50, or 5 points. Normalized values are portable (messages and data sharing) Probably the most compelling reason to normalize the claim values in your repu- tation statements and messages is that normalized data is portable across various display contexts (see Chapter 7) and can reuse any of the roll-up process code in your reputation framework that accepts and outputs normalized values. Other applications will not require special understanding of your claim values to interpret them. Practitioner’s Tips: Reputation Is Tricky | 57
  3. Normalized values are easy to transform (denormalize) The most common representation of the average of scalar inputs is a percentage, and this denormalization is accomplished trivially by multiplying the normalized value by 100. Any normalized score may be transformed into a scalar value by using a table or, if the conversion is linear, by performing a simple multiplication. For example, converting to a 5-star rating system could be as simple as multiplying the rating by 0.20 to get the normalized score. To get the stars back, just multiply by 5.0. Normalization also allows the values of any claim type, such as thumbs-up (1.0)/ thumbs-down (0.0), to be denormalized as a different claim type, such as a per- centage (0%–100%) or turned into a 3-point scale of thumbs-up (0.66–1.0), thumbs-down (0.0–0.33), or thumb-to-side (0.33–0.66). Using a normalized score allows this conversion to take place at display time without committing the con- verted value to the database. Also, the exact same values can be denormalized by different applications with completely different needs. As with all things, the power of normalization comes with some costs: Combining normalized scalar values introduces bias Using different normalized numbers in large reputation systems can cause unex- pected biases when the original claim types were scalar values with slightly different ranges. Averaging normalized maximum 4-star ratings (25% each) with maximum 5-star ratings (20% each) leads to rounding errors that cause the scores to clump up if the average is denormalized back to 5 stars. See Table 3-1. Table 3-1. An example of ugly side effects when normalizing/denormalizing across different scales Scale 1 stars 2 stars 3 stars 4 stars 5 stars normalized normalized normalized normalized normalized 4 stars 0–25 26–50 51–75 76–100 N/A 5 stars 0–20 21–40 41–60 61–80 81–100 Mean range/ 0–22 / 23–45 / 46–67 / 68–90 / 78–100 / denormalized ★☆☆☆☆ ★★☆☆☆ ★★★☆☆ ★★★★☆ ★★★★★ Liquidity: You Won’t Get Enough Input When is 4.0 greater than 5.0? When enough people say it is! —F. Randall Farmer, Yahoo! Community Analyst, 2007 Consider the following problem with simple averages: it is mathematically unreason- able to compare two similar targets with averages made from significantly different numbers of inputs. For the first target, suppose that there are only three ratings 58 | Chapter 3: Building Blocks and Reputation Tips
  4. averaging 4.667 stars, which after rounding displays as ★★★★★, and you compare that average score to a target with a much greater number of inputs, say 500, averaging 4.4523 stars, which after rounding displays as only ★★★★☆. The second target, the one with the lower average, better reflects the true consensus of the inputs, since there just isn’t enough information on the first target to be sure of anything. Most simple- average displays with too few inputs shift the burden of evaluating the reputation to users by displaying the number of inputs alongside the simple average, usually in pa- rentheses, like this: ★★★★☆ (142). But pawning off the interpretation of averages on users doesn’t help when you’re rank- ing targets on the basis of averages—a lone ★★★★★ rating on a brand-new item will put the item at the top of any ranked results it appears in. This effect is inappropriate and should be compensated for. We need a way to adjust the ranking of an entity based on the quantity of ratings. Ideally, an application performs these calculations on the fly so that no additional storage is required. We provide the following solution: a high-performance liquidity compensation algo- rithm to offset variability in very small sample sizes. It’s used on Yahoo! sites to which many new targets are added daily, with the result that, often, very few ratings are applied to each one. RankMean r = SimpleMean m - AdjustmentFactor a + LiquidityWeight l * Adjustment Factor a LiquidityWeight l = min(max((NumRatings n - LiquidityFloor f) / LiquidityCeiling c, 0), 1) * 2 or r = m - a + min(max((n - f) / c, 0.00), 1.00) * 2.00 * a This formula produces a curve like that in Figure 3-14. Though a more mathematically continuous curve might seem appropriate, this linear approximation can be done with simple nonrecursive calculations and requires no knowledge of previous individual inputs. The following are suggested initial values for a, c, and f (assuming normalized inputs): AdjustmentFactor a = 0.10 This constant is the fractional amount to remove from the score before adding back in effects based on input volume. For many applications, such as 5-star ratings, it should be within the range of integer rounding error—in this example, if the AdjustmentFactor is set much higher than 10%, a lot of 4-star entities will be ranked before 5-star ones. If it’s set too much lower, it might not have the desired effect. Practitioner’s Tips: Reputation Is Tricky | 59
  5. Figure 3-14. The effects of the liquidity compensation algorithm. LiquidityFloor f = 10 This constant is the threshold for which we consider the number of inputs required to have a positive effect on the rank. In an ideal environment, this number is be- tween 5 and 10, and our experience with large systems indicates that it should never be set lower than 3. Higher numbers help mitigate abuse and get better rep- resentation in consensus of opinion. LiquidityCeiling c = 60 This constant is the threshold beyond which additional inputs will not get a weighting bonus. In short, we trust the average to be representative of the optimum score. This number must not be lower than 30, which in statistics is the minimum required for a t-score. Note that the t-score cutoff is 30 for data that is assumed to be unmanipulated (read: random). We encourage you to consider other values for a, c, and f, especially if you have any data on the characteristics of your sources and their inputs. Bias, Freshness, and Decay When you’re computing reputation values from user-generated ratings, several com- mon psychological and chronological issues will likely represent themselves in your data. Often, data will be biased because of the cultural mores of an audience or simply because of the way the application gathers and shares reputations; for example, an application may favor the display of items that were previously highly rated. Data may also be stale because the nature of the target being evaluated is no longer relevant. For example, because of advances in technology, the ratings for the features of a specific model of digital camera, such as the number of pixels in each image, may be irrelevant within a few months. Numerous solutions and workarounds exist for these problems, 60 | Chapter 3: Building Blocks and Reputation Tips
  6. one of which is to implement a method to decay old contributions to your reputations. Read on for details of these problems and what you can do about them. Ratings bias effects Figure 3-15 shows the graphs of 5-star ratings from nine different Yahoo! sites with all the volume numbers redacted. We don’t need them, since we want to talk only about the shapes of the curves. Figure 3-15. Some real ratings distributions on Yahoo! sites. Only one of these distributions suggests a healthy, useful spread of ratings within a community. Can you spot it? Eight of these graphs have what is known to reputation system aficionados as J-curves— where the far right point (5 stars) has the very highest count, 4 stars the next highest, and 1 star a little more than the rest. Generally, a J-curve is considered less than ideal for several reasons. The average aggregate scores, which are all clumped together be- tween 4.5 and 4.7 and therefore all display as 4 or 5 stars, are not so useful in visual sorting of options. Also, a J-curve begs the question: why use a 5-point scale at all? Practitioner’s Tips: Reputation Is Tricky | 61
  7. Wouldn’t you get the same effect with a simpler thumbs-up, thumbs-down scale, or maybe even just a super-simple favorite pattern? The outlier among the graphs is for Yahoo! Autos Custom (now shut down), where users rated car profile pages created by other users. That graph has a W-curve: lots of 1-, 3-, and 5-star ratings and a healthy share of 4- and 2-star ratings, too. It was a healthy distribution and suggested that a 5-point scale was good for the community. But why were Yahoo! Autos Custom’s ratings so very different from Yahoo! Shopping, Local, Movies, and Travel? Most likely, the biggest difference was that Autos Custom users were rating one an- other’s content. The other sites had users evaluating static, unchanging, or feed-based content in which they didn’t have a vested interest. In fact, if you look at the curves for Shopping and Local, they are practically identical, and have the flattest J-hook, giving the lowest share of 1-star ratings. This similarity was a direct result of the overwhelming use pattern for those sites. Users come to find a great place to eat or the best vacuum to buy. When they search, the results with the highest ratings appear first. If a user has experienced that place or thing, he may well also rate it—if it’s easy to do so—and most likely will give it 5 stars (see “First-mover effects” on page 63). If the user sees an object that isn’t rated but that he likes, he may also rate and/or review it, usually giving it 5 stars so that others can share his discovery—otherwise, why bother? People don’t think that it’s worth the bother to seek out and create Internet ratings for mediocre places or things. The curves, then, are the direct result of a product design intersecting with users’ goals. This pattern—“I’m looking for good things, so I’ll help others find good things”—is a prevalent form of ratings bias. An even stronger example happens when users are asked to rate episodes of TV shows. They rate every episode 4.5 stars plus or minus .5 star because only the fans bother to rate the episodes, and no fan is ever going to rate an episode below a 3. Look at any popular current TV show on Yahoo! TV or Television Without Pity. Our closer look at how Yahoo! Autos Custom ratings worked and how users were evaluating the content showed why 1-star ratings were given out so often: users gave feedback to other users to get them to change their behavior. Specifically, you would get one star if you (1) didn’t upload a picture of your ride, or (2) uploaded a dealer stock photo of your ride. The site is Autos Custom, after all! Users reserved 5-star ratings for the best of the best. Ratings of 2 through 4 stars were actually used to evaluate the quality and completeness of the car’s profile. Unlike all the sites graphed here, the 5- star scale truly represented a broad sentiment, and people worked to improve their scores. One ratings curve isn’t shown here: the U-curve, in which 1 star and 5 stars are dis- proportionately selected. Some highly controversial objects on Amazon are targets of this rating curve. Yahoo’s now-defunct personal music service also saw this kind of curve when new music was introduced to established users: 1 star came to mean “Never play this song again” and 5 meant “More like this one, please.” If you’re seeing 62 | Chapter 3: Building Blocks and Reputation Tips
  8. U-curves, consider that users may be telling you something other than what you wanted to measure (or that you might need a different rating scale). First-mover effects When an application handles quantitative measures based on user input, whether it’s ratings or measuring participation by counting the number of contributions to a site, several issues arise—all resulting from bootstrapping of communities—that we group together under the term first-mover effects: Early behavior modeling and early ratings bias The first people to contribute to a site have a disproportionate effect on the char- acter and future contributions of others. After all, this is social media, and people usually try to fit into any new environment. For example, if the tone of comments is negative, new contributors will also tend to be negative, which will also lead to bias in any user-generated ratings. See “Ratings bias effects” on page 61. When an operator introduces user-generated content and associated reputation systems, it is important to take explicit steps to model behavior for the earliest users in order to set the pattern for those who follow. Discouraging new contributors Take special care with systems that contain leaderboards (see “Leaderboard rank- ing” on page 189) when they’re used either for content or for users. Items displayed on leaderboards tend to stay on the leaderboards, because the more people who see those items and click, rate, and comment on them, the more who will follow suit, creating a self-sustaining feedback loop. This loop not only keeps newer items and users from breaking into the leader- boards, it discourages new users from even making the effort to participate by giving the impression that they are too late to influence the result in any significant way. Though this phenomenon applies to all reputation scores, even for digital cameras, it’s particularly acute in the case of simple point-based karma systems, which give active users ever more points for activity so that leaders, over years of feverish activity, amass millions of points, making it mathematically impossible for new users to ever catch up. Freshness and decay As the previous section showed, time leaches value from reputation, but there’s also the simple problem of ratings becoming stale over time as their target reputable entities change or become unfashionable. Businesses change ownership, technology becomes obsolete, cultural mores shift. The key insight to dealing with this problem is to remember the expression, “What did you do for me this week?” When you’re considering how your reputation system will display reputation and use it indirectly to modify the experience of users, remember to Practitioner’s Tips: Reputation Is Tricky | 63
  9. account for time value. A common method for compensating for time in reputation values is to apply a decay function: subtract value from the older reputations as time goes on, at a rate that is appropriate to the context. For example, digital camera ratings for resolution should probably lose half their weight every year, whereas restaurant reviews should only lose 10% of their value in the same interval. Here are some specific algorithms for decaying a reputation score over time: Linear aggregate decay Every score in the corpus is decreased by a fixed percentage per unit time elapsed, whenever it is recalculated. This is high performance, but scarcely updated repu- tations will have disproportionately high values. To compensate, a timer input can perform the decay process at regular intervals. Dynamic decay recalculation Every time a score is added to the aggregate, recalculate the value of every contri- buting score. This method provides a smoother curve, but it tends to become computationally expensive O(n2) over time. Window-based decay recalculation The Yahoo! Spammer IP reputation system has used a time-window-based decay calculation: fixed time or a fixed-size window of previous contributing claim values is kept with the reputation for dynamic recalculation when needed. New values push old values out of the window, and the aggregate reputation is recalculated from those that remain. This method produces a score with the most recent infor- mation available, but the information for low-liquidity aggregates may still be old. Time-limited recalculation This is the de facto method that most engineers use to present any information in an application: use all of the ratings in a time range from the database and compute the score just in time. This is the most costly method, because it involves always hitting the database to recalculate an aggregate reputation (say, for a ranked list of hotels), when 99% of the time the resulting value is exactly the same as it was in the previous iteration. This method also may throw away still contextually valid reputation. Performance and reliability are usually best served with the alternate approaches described previously. Implementer’s Notes The massive-scale Yahoo! Reputation Platform, detailed in Appendix A, implemented the reputation building blocks, such as the accumulator, sum, and even rolling average, in both the reputation model execution engine and in the database layer. This division of labor provided important performance improvements because the read-modify-write logic for stored reputation values are kept as close to the data store as possible. For small systems, it may be reasonable to keep the entire reputation system in memory at once, thus avoiding this complication. But be careful. If your site is as successful as you 64 | Chapter 3: Building Blocks and Reputation Tips
  10. hope it might someday be, making an all-memory-based design may well come back to bite you, hard. Making Buildings from Blocks In this chapter, we extended the grammar by defining various reputation building blocks out of which hundreds of currently deployed reputation systems are built. We also shared tips about a few surprises we’ve encountered that emerge when these pro- cesses interact with real human beings. In Chapter 4, we combine and customize these blocks to describe full-fledged reputa- tion models and systems that are available on the Web today. We look at a selection of common patterns, including voting, points, and karma. We also review complex reputations, such as those at eBay and Flickr, in considerable detail. Diagramming these currently operational examples demonstrates the expressiveness of the grammar, and the lessons learned from their challenges provide important experiences to consider when designing new models. Making Buildings from Blocks | 65
  11. CHAPTER 4 Common Reputation Models Now we’re going to start putting our simple reputation building blocks from Chap- ter 3 to work. Let’s look at some actual reputation models to understand how the claims, inputs, and processes described in the last chapter can be combined to model a target entity’s reputation. In this chapter, we name and describe a number of simple and broadly deployed rep- utation models, such as vote to promote, simple ratings, and points. You probably have some degree of familiarity with these patterns by simple virtue of being an active online participant. You see them all over the place; they’re the bread and butter of today’s social web. Later in this chapter, we show you how to combine these simple models and expand upon them to make real-world models. Understanding how these simple models combine to form more complete ones will help you identify them when you see them in the wild. All of this will become important later in the book, as you start to design and architect your own tailored reputation models. Simple Models At their very simplest, some of the models we present next are really no more than fancified reputation primitives: counters, accumulators, and the like. Notice, however, that just because these models are simple doesn’t mean that they’re not useful. Varia- tions on the favorites-and-flags, voting, ratings-and-reviews, and karma models are abundant on the Web, and the operators of many sites find that, at least in the begin- ning, these simple models suit their needs perfectly. 67
  12. Favorites and Flags The favorites-and-flags model excels at identifying outliers in a collection of entities. The outliers may be exceptional either for their perceived quality or for their lack of same. The general idea is this: give your community controls for identifying or calling attention to items of exceptional quality (or exceptionally low quality). These controls may take the form of explicit votes for a reputable entity, or they may be more subtle implicit indicators of quality (such as the ability to bookmark content or send a link to it to a friend). A count of the number of times these controls are accessed forms the initial input into the system; the model uses that count to tabulate the entities’ reputations. In its simplest form, a favorites-and-flags model can be implemented as a simple counter (Figure 4-1). When you start to combine them into more complex models, you’ll prob- ably need the additional flexibility of a reversible counter. Figure 4-1. Favorites, flags, or send-to-a-friend models can be built with a Simple Counter process— count ’em up and keep score. The favorites-and-flags model has three variants: vote to promote, favorites, and report abuse. Vote to promote The vote-to-promote model, a variant of the favorites-and-flags model, has been popu- larized by crowd-sourced news sites such as Digg, Reddit, and Yahoo! Buzz. In a vote- to-promote system, a user promotes a particular content item in a community pool of submissions. This promotion takes the form of a vote for that item, and items with more votes rise in the rankings to be displayed with more prominence. Vote to promote differs from this-or-that voting (see the section “This-or-That Vot- ing” on page 69) primarily in the degree of boundedness around the user’s options. Vote to promote enacts an opinion on a reputable object within a large, potentially unbounded set (sites like StumbleUpon, for instance, have the entire Web as its can- didate pool of potential objects). 68 | Chapter 4: Common Reputation Models
  13. Favorites Counting the number of times that members of your community bookmark a content item can be a powerful method for tabulating content reputation. This method provides a primary value (see the sidebar “Provide a Primary Value” on page 132) to the user: bookmarking an item gives the user persistent access to it, and the ability to save, store, or retrieve it later. And, of course, it also provides a secondary value to the reputation system. Report abuse Unfortunately, there are many motivations in user-generated content applications for users to abuse the system. So it follows that reputation systems play a significant role in monitoring and flagging bad content. This is not that far removed from bookmarking the good stuff. The most basic type of reputation model for abuse moderation involves keeping track of the number of times the community has flagged something as abusive. Craigslist uses this mechanism, and sets a custom threshold for each item listed based on a per-user, per-category, and even per-city basis—though the value and the formu- lation are always kept secret from the users. Typically, once a certain threshold is reached, either the application or human agents (staff) will act upon the content accordingly, or some piece of application logic will determine the proper automated outcome: remove the “offending” item, properly cat- egorize it (for instance, add an “adult content” disclaimer to it), or add it to a prioritized queue for human agent intervention. If your application is at a scale where automated responses to abuse reports are necessary, you’ll probably want to consider tracking repu- tations for abuse reporters themselves. See “Who watches the watch- ers?” on page 209 for more. This-or-That Voting If you give your users options for expressing their opinion about something, you are giving them a vote. A very common use of the voting model (which we’ve referenced throughout this book) is to allow community members to vote on the usefulness, ac- curacy, or appeal of something. To differentiate from more open-ended voting schemes like vote to promote, it may help to think of these types of actions as “this-or-that” voting: choosing from the most attractive option within a bounded set of possibilities (see Figure 4-2). It’s often more convenient to store that reputation statement back as a part of the reputable entity that it applies to, making it easier, for example, to fetch and display a “Was this review helpful?” score (see Figure 2-7 in Chapter 2). Simple Models | 69
  14. Figure 4-2. Those “Helpful Review” scores that you see are often nothing more than a Simple Ratio. Ratings When an application offers users the ability to express an explicit opinion about the quality of something, it typically employs a ratings model (Figure 4-3). There are a number of different scalar-value ratings: stars, bars, “HotOrNot,” or a 10-point scale. (We discuss how to choose from among the various types of ratings inputs in the section “Determining Inputs” on page 131.) In the ratings model, ratings are gathered from multiple individual users and rolled up as a community average score for that target. Figure 4-3. Individual ratings contribute to a community average. Reviews Some ratings are most effective when they travel together. More complex reputable entities frequently require more nuanced reputation models, and the ratings-and- review model, shown in Figure 4-4, allows users to express a variety of reactions to a target. Although each rated facet could be stored and evaluated as its own specific reputation, semantically that wouldn’t make much sense; it’s the review in its entirety that is the primary unit of interest. In the reviews model, a user gives a target a series of ratings and provides one or more freeform text opinions. Each individual facet of a review feeds into a community average. 70 | Chapter 4: Common Reputation Models
Đồng bộ tài khoản