Social Computing Flashcards

1
Q

Confusion Matrices

A

a more accurate substitute for the basic probability that a user gives the correct answer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Consequences of information asymmetry

A

Leads to buyers making an adverse selection as the market consists of poor-quality items, as explained in The Lemon Problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Moral Hazard

A

Hazards that arise when an individual is incentivised to take greater risks as they are shielded from the negative consequences of their actions.

Such as, failing to uphold an agreement after payment as there is no consequences to their actions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Purpose of Reputation Systems

A

Mitigate moral hazards and address the information asymmetry that leads to adverse selections in the market by quantifying the trust of individuals/entities using the wisdom of the crowd

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Calculate Reputation Value

A

Calculated through averages of user ratings, improved with:
- correction for user bias
- weighted rankings (based on user trustworthiness i.e. past ratings rated helpful by others)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Confidence Values

A

Convey the certainty of the accuracy of a reputation values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Challenges with Reputation Systems

A

Ballot Stuffing
Slander & Self Promotion
Whitewashing
Fear of Retaliation
Individual Bias
Quality Variations
Lack of Incentives

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Ballot Stuffing

A

Multiple ratings from a single user

To tackle, ensure there is some effort-based (or monetary) cost to providing rating

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Slander & Self-promotion

A

Competitors place reviews to damage sales of others

To tackle, require identity authentication and proof of transaction. Allow ratings of helpfulness of ratings. Use trust interference based on a user’s history

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Whitewashing

A

Users change their identity to reset their reputation

To tackle, ensure there is an effort-based cost to changing identity e.g. linking phone number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Fear of Retaliation

A

Users fear retaliation and give overly positive ratings

To tackle, simultaneously disclose buyer and seller ratings e.g. Airbnb. Or prevent seller from rating buyers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Individual Bias

A

Users rate overly positive or negative

To tackle, adjust score based on history

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Quality Variations

A

Sellers sell low-value items to achieve a good reputation value, only to exploit this and sell low quality goods at high value

To tackle, weight ratings based on price and recency

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Lack of Incentives

A

Users may not want to provide ratings

To tackle, provide non-monetary, or monetary, rewards

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Motivations to Participate in Crowdsourcing

A

Financial Rewards
Self-development
Enjoyment
Altruism (Selflessness)
Social Aspects (Recognition, Competition, Validation)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Social Mobilisation

A

Address complex search problems through referral schemes e.g. recursive incentive scheme

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Output-agreement Mechanism

A

Gamification technique
ESP Game for Image Labelling

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Input-agreement Mechanism

A

Gamification technique
TagATune Game

Provide descriptions and guess if listening to same song as peer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Benefit of Gamification

A

Increased engagement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Anchoring Effect

A

Individuals rely heavily on the first piece of information they receive (initial pay) when making subsequent judgments or estimations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Expert Crowdsourcing Attributes

A

Quality is highly important
less workers relied on

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Crowdsourcing Contests

A

Individuals submit solutions and best submission is rewarded
- Workers behave strategically and pick tasks with less competition
- Early success experience is critical for workers to continue contributing
- Only a small amount of workers succeed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Multi-armed Bandit Problem

A

Describes the challenge of maximising rewards when balancing the exploration of new options and the exploitation of the best option known

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

ε-greedy

A

ε-greedy considers a probability of whether to explore or exploit.
ε-greedy(0.05) is 5% chance of EXPLORATION and 95% chance of EXPLOITATION

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Average Quality per Cost
AKA Reward to Cost Ratio
26
ε-first
allocates a percentage of the budget to exploration before repeatedly pulling arm with highest average quality per cost. ε- first(0.1) gives 10% of budget to exploration Best performance
27
Thompson sampling
keeps a prior for each arm and picks an arm by picking the best sample from each prior, it updates each prior using Bates’ theorem. Naturally explores promising arms and exploits as uncertainty drops
28
Plurality Voting
top voted candidate wins. It fails to consider voter preferences beyond first choice
29
Borda count
candidates receive points based on sum of positions in voters’ preferences
30
Condorcet Winner
a winner determined through pair-wise plurality
31
Condorcet Paradox
there are scenarios in which the majority of voters will be dissatisfied i.e. no matter the outcome the majority will prefer another option
32
Condorcet Criterion
satisfied by a voting system which always chooses the Condorcet winner and therefore reflects the collective preferences of the voters Borda count & plurality voting do not satisfy Black's rule & Copeland method satisfy
33
Black's Rule
selects Condorcet winner or uses Borda count as a fallback
34
Copeland Method
selects winner by subtracting pairwise losses from pairwise victories
35
Spearman’s Footrule distance
the sum of displacements between candidates in two rankings
36
Kendall-Tau Distance
the sum of pairwise *disagreements* of candidates in two rankings
37
Finding Optimal rankings
compare all enumerations to voter preferences and sum up the distances Spearman’s Footrule optimal ranking can be solved in polynomial time Kendall-Tau is NP-hard
38
Collective Intelligence
intelligence that emerges from collaboration, collective efforts, or competition of many individuals
39
Social Computing
covers methods for building computational systems that harness collective intelligence
40
Human Computation
outsources computational microtasks, which are difficult for machines to complete, to humans
41
Requirements for a microtask
- Hard for computers, easy for humans - Easily and quickly explainable to non-experts - Fast to complete - Amenable to automatic quality control and aggregation - Robust to some noise
42
MTurk
Amazon Mechanical Turk (MTurk) is a crowdsourcing platform enabling the outsourcing of Human Intelligence Tasks (HITs) to remote workers known as Turkers
43
Solyent
a word processor powered by human computation with the functions of - *Shortn*: Shorten Text - *Crowdproof*: Proofreading & Grammatical Corrections - *The Human Macro*: Issue tasks i.e. find an image to accompany text
44
Find-Fix-Verify pattern
- *Find*: Workers highlighted sections that needed attention e.g. mistakes, text that can be shortened - *Fix*: Other workers proposed improvements for *only one* of the most commonly highlighted sections - *Verify*: Other workers voted on the best improvements
45
Benefits of Find-Fix-Verify
ideal for complex tasks as it - Separation of find and fix avoids lazy users who focus on the easiest fixes - Highly parallelisable as a document can be split into chunks and distributed among workers - Verification ensures quality - Each stage has independent decisions - Small tasks decrease the likelihood of errors
46
TurKit
TurKit is a framework for facilitating development of applications using Mechanical Turk. Its Crash-and-Rerun feature ensures progress is cached when a crash occurs and work resumes from the last successful checkpoint
47
Human Computation Quality Control Methods
Majority Voting Weighted Voting: Assigns a higher weight to users who tend to agree more with others Weighted Voting with Prior
48
How to get prior for Weighted Voting with Prior
use ground truths to identify each user’s probability of choosing the correct answer. Helps to deal with uncertainty of the accuracy of users’ answers. Prior Knowledge comes from - Previous Interactions - Reputation System - Gold Standards (True Labels)
49
Trust
A subjective probability by which an individual expects another individual performs a given action on which its welfare depends
50
Reputation
Considers the collective opinion of multiple individuals about a single individual; an aggregation of personal experience
51
Experimental Design
Orchestration of experiments for analysis using proper scientific approach to tune a system for an optimal design
52
A/B Split Testing
Compares two versions of content to determine which is better
53
A/B Split Testing Advantages
- Easy to test, implement and analyse - Flexible factor changes
54
A/B Split Testing Disadvantages
- Impractical to test all possible combinations to capture interdependence between factors so unlikely to find optimal solution - Not possible to determine which factors contribute most as too many factors change at once - Inefficient - Will not find optimal
55
Multivariate Testing
Simultaneously tests multiple factors: - One Factor At a Time - Full Factorial Design - Fractional Factorial Design
56
One Factor At a Time (OFAT)
Changes only *one factor* at a time from the *base treatment* and analyses the outcome
57
One Factor At a Time Advantages
Frequently Used
58
One Factor At a Time Disadvantages
- Significant number of trials required per treatment to obtain statistical significance - Unbalanced, values have different numbers of occurrences (bias towards base treatment values) - Limited number of treatments when changing one factor
59
Full Factorial Design
Considers all possible combinations of factor values Num Treatments = Num Factors ^ Num Options per Factor
60
Interaction Effects
The impact of a factor is dependant on a second factor e.g. - Best page content depends on best page layout
61
Main Effects
Individual factors calculated by average outcome over all other varied factors
62
Full Factorial Design Advantages
- Number of trials to achieve statistical significance is less than OFAT - Balanced, each values occur the same number of times - Can capture interation effects
63
Full Factorial Design Disadvantages
- Requires significant number of recipes - Number of treatments increases exponentially with factors - Number of trials increases as treatments increaes - Impractical to test all combinations
64
Fractional Factorial Design
Considers a subset of all possible combinations of factor values to reduce the number of treatments required
65
Latin Squares
Control *two* sources of variation simultaneously in a practical way. - They do not eliminate all confounding of variables but can eliminate some bias from interaction effects by ensuring each value is tested equally as often with different combinations of other factors
66
Latin Squares Advantages
- Requires less recipes (m^2) than Full Fractional Design (m^3) with same benefits - Interaction effects can cancel out
67
Latin Squares Disadvantages
- Can only measure main effects - Requires same number of trials as Full Fractional Design - Does not necessarily produce the best recipe - Limited to 3 factors
68
Online Auction
Dynamic pricing based on competition acting as a price discovery mechanism
69
English Auction
Auctioneer progressively increases the bid price until no further bids are made
70
Dutch Auction
Price starts high and gradually lowers until a bidder accepts the price at which point the item is sold
71
Sealed-bid First Price Auction
Each bidder submits a single bid in a sealed envelope and the item is allocated to to the highest bid at the price bid
72
Sealed-bid Second Price Auction (Vickrey Auction)
Each bidder submits a single bid in a sealed envelope and the item is allocated to the highest bidder at the price of the second-highest bid
73
Private Value
A bidder's willingness to pay for an item, independent of what others believe the item is worth
74
Utility
The satisfaction for bidder *i* winning the auction is u*i* = v*i* - p*i* v*i* is private value p*i* is payment if v*i* = p*i* then the bidder is indifferent to winning or losing as the utility gained from winning is 0 and there is 0 utility on a loss
75
Dominant Strategy
Provides the best payoff regardless of the strategies of other players
76
Best Strategies
Maximise payoff while considering strategies of other players
77
English Auction Dominant Strategy
Bid the smallest amount (the bid increment) and stop when your private value is reached
78
First-Price Sealed-Bid Auction Best Strategy
SHADE BID Bidders will speculate about the bids of others and the probability of the highest bid. Calculate the utility gained given the probabilities of each outcome There is a 40% chance the highest bid (except you) is £150 - If you bid £151 and win, u = 0.40(£300 - £151) = £59.60 There is a 40% chance the highest bid is £210 - If you bid £211 and win, u= 0.80(£300-£211) = £71.20 There is a 20% chance the highest bid is £240 - If you bid £241 and win u = 1.00(£300-£241) = £59 The *best* strategy to maximise utility is to bid There is no dominant strategy
79
Vickrey Auction Dominant Strategy
Bid your private value v*i* - If the highest bid (excluding yours) is $>v_i$ then - By bidding less than $v_i$, you always lose and gain $0$ utility - By bidding more than $v_i$, you might win but always gain negative utility (overpaying) - If the highest bid (excluding yours) is $ 0$
80
Strategic Equivalence of Auctions
English Auctions and Vickrey Auctions are Strategically Equivalent Dutch Auctions and First-Price Sealed-Bid Auctions are Strategically Equivalent
81
Vickrey vs English
Vickrey is better It avoids wasteful effort of counter speculation but still ensures the bidder with the highest private value receives the item (efficiency)
82
Revenue Equivalence Theorem
All four auction protocols produce the same revenue provided that - Bidders are rational - Bidders are risk neutral - Private value assumption holds - Bidders are symmetric, with the same beliefs about the probability of bids made by others
83
Winner's Curse
the winning bid exceeds the intrinsic value of the item
84
Bidder Collusion
2 or more bidders from bidding rings to manipulate the auction
85
Corruption
an auctioneer misuses their position - They may lie about submitted bids - Revealing all bids after an auction provides transparency
86
Sniping
Last minute bids. Occurs when closing time is fixed - Prevents being outbid by other - Solved with flexible deadline and sealed-bid auctions
87
Risk of Low Profit
Solved with a reserve price
88
Organic Search
Unbiased search where results are based on a ranking algorithm
89
Sponsored Search
Paid and biased search where ranking is based on auction mechanism
90
Pay-per-Impression
Advertiser pays per million impressions (when ad is displayed)
91
Per-per-Click
Advertiser pays when ad is clicked
92
Pay-per-Transaction
Advertiser pays when an actual purchase is made. Attribution challenges
93
Slot Allocation
sorting advertisements in ascending order according to bid * quality score
94
GSP
Generalised Second-Price Auction - Pay the smallest amount you could have bid and still retain the same position A1: 10 * 0.6 = 6 A2: 7 * 0.9 = 6.3 A3: 5 * 0.4 = 2 Order: A2, A1, A3 A2 Pays: A1 Bid * A1 Quality / A2 Quality = £6.67 A1 Pays: A3 Bid * A3 Quality / A1 Quality = £3.33
95
GSP Review
Payment is never more than bid. Bidders might prefer lowest spots to increase their utility. Auction does not fully capture preferences, bid is for one slot and not each slot
96
True Positive
A recommended item is relevant to a user
97
False Positive
A recommended item is not relevant to a user
98
True Negative
An irrelevant item is not recommended to a user
99
False Negative
A relevant item is not recommended to a user
100
Precision
A measure of exactness Precision = TP / (TP + FP) Good Recommendations / All Recommendations
101
Recall
A measure of completeness How many recommendations did you recall Recall = TP / (TP + FN) Good Recommendations / All Good Items (Even those not recommended)
102
Accuracy
The accuracy of all classifications i.e. true positives and true negatives Accuracy = tp + tn / (tp + tn + fp + fn) Correct Classifications / All Classifications
103
Crowdsourcing Study Takeaways
- Financial rewards ***decrease*** intrinsic motivation - Positive verbal feedback ***increases*** intrinsic motivation - Performance drops when financial incentive is lowest - Financial rewards can increase speed of work but no quality as workers always aim for minimum acceptable quality - Anchoring effect can be harnessed - Payment method affects factors
104
Content-based Recommender Systems Advantages
- No community required
105
Content-based Recommender Systems Disadvantages
- Content-descriptions required - Cold start issue for new users - No surprising suggestions
106
Knowledge-based Recommender Systems Advantages
- Deterministic recommendations - Guaranteed quality - No cold-start issue - Can resemble sales dialogue
107
Knowledge-based Recommender Systems Disadvantages
- Knowledge engineering effort required - Fundamentally static - Cannot react to short-term trends
108
Collaborative Filtering Recommender Systems Advantages
- No knowledge engineering effort required - Can produce surprising recommendations
109
Collaborative Filtering Recommender Systems DIsadvantages
- Requires feedback through ratings - Cold start issue for new users and items - Sparsity problems - No integration of other knowledge sources
110
Crowdsourcing
obtains services, ideas, or content from a large group of people through an open call rather than from the traditional employee or supplier relationship
111
Content-based Recommender System Steps
- Identify Features (Title, Genre, Keywords) - Clean Features (Remove Stop-words, Stemming, Phrase Extraction, TF-IDF) - Find Similarities - Produce Reccomendations
112
Dice's Similarity Coefficient
Compares number of shared elements to total number of elements in both sets D(X, Y) = 2 x |X ∩ Y| / (|X| + |Y|) Fails to consider element frequency
113
Jaccard's Similarity Coefficient
J(X, Y) = |X ∩ Y| / |X ∪ Y| Fails to consider element frequency
114
Cosine Similarity Coefficient
Measures angle between two vectors